[20.12.30] 모각코 수요 스터디

[bluelion2]

❤ 수요 살롱

📅 12월 30일

☕ 장소 : 서울대입구역

⏱️ 시간 : 수요일 저녁 8시 ~ 10시

🙏 참석하실 분은 밑에 이슈 등록해주세요~!

[ds2lvg]

참석

[wacilpong]

12월으 마지막 공부 참여

[bluelion2]

오늘은 칼퇴하고 참석해야지

[ds2lvg]

할일

단방향 Linked List 기능 구현

• 중복값 삭제
• 뒤부터 세기

• 중간노드 삭제

[wacilpong]

할일

• 회사 업무중... 9시까지 하고 아래 공부할 예정
• 모던자바스크립트 deep dive 슬슬 읽기
• 알고리즘 산책 유클리드부터 보기

[ds2lvg]

회고

• 단방향 Linked List 중복값 삭제 메서드 구현
  • Buffer를 만들지 않고 runner 포인터를 만들어서 중복데이터는 다다음 포인터랑 연결해서 중복을 제거 할 수 도 있다.
• memoirsOf2020

[wacilpong]

회고

• 유클리드는 최소한의 단계로 최대한 다양하게 응용될 수 있는 결과를 이끄는 증명을 선호했다.
• 최대공측도(최대공약수) 구하는 유클리드 호제법

  명제: 두 개의 서로 다른 양이 있을 때 더 작은 양을 더 큰 양에서 빼는 작업을 반복한 후에 남는 양이 그전 양을 측정할 수 없으면 두 양은 통분 불가능하다
  

  • 피타고라스 학파의 "최대공측도를 계산하는 절차가 영원히 종료되지 않으면 두 수 사이에는 최대공측도가 존재하지 않는다"는 결과와 같다.
  • 측도는 어떤 선분 P,V가 있을 때 V를 유한 번 이어서 P를 표현할 수 있으면 선분 V를 선분 P의 측도라고 부른다.
  • 공측도는 선분 P의 측도이면서 동시에 선분 V의 측도인 경우이다.
  • 최대공측도는 공측도는 여러 개 있을 수 있는데, 그중 가장 큰 공측도이다.
  • 이는 추후 최대공약수와 같다.
  • 위 명제에 따라 계속해서 큰 쪽에서 작은 쪽을 빼는 방법이다.
  • a와 b는 무한하지 않기 때문에 나눈 나머지를 재귀적으로 비교할 수 있다.
  • 이는 a와 b에 대해서 a <= nb를 만족하는 자연수 n이 존재한다는 아르키메데스의 공리로 증명된다.

    integer gcd(integer a, integer b) {
        while (b != interger(0)) {
            a = a % b;
            std::swap(a, b);
        }
    
        return a;
    }

  • 순환이 돌 때마다 최대공약수는 항상 같아야 한다.
  • 따라서 gcd(a0, b0) = gcd(b0, r1) = gcd(r1, r2) = ... = gcd(rn-1, rn)
  • rn-1과 rn의 나머지는 종료 조건에 따라 0이므로 gcd(a0, b0) = ... = gcd(rn, 0) = rn;
  • 자바스크립트로 재귀적 순환으로 구현할 경우 다음과 같다.

      function gcd(a, b){
          const r = a % b;
    
          if (r > 0) {
            return gcd(b, r);
          }
    
          return b;
      }