✏️ 2022-11-10 Today I Learn

[알고리즘] 정렬

1-1. 병합정렬

인자가 쪼개지지 않을때까지 쪼갠뒤, 병합하면서 정렬하는 기법.
분할-정복(Divide-Conquer) 기법을 사용하는 대표적인 방법 중 하나.
분할의 시간복잡도는 $O(logN)$
병합의 시간복잡도는 $O(N)$
따라서, 병합정렬은 $O(NlogN)$ 의 시간복잡도를 가진다.
병합정렬의 과정

[5] [3]
[2] [1]
[3, 5] [1, 2]
[6] [8]
[7] [4]
[6, 8] [4, 7]
[1, 2, 3, 5] [4, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8]

[Python] 파이썬 딕셔너리의 주소값 체이닝

파이썬 딕셔너리 주소참조 기능 이용하여 enqueue 구현 중, 초기에 생성된 0x103148a30주소를 가진 next에 계속 tail로 오는 값들이 이어지는 것으로 보임.

{'data': 3, 'next': <__main__.Node object at 0x103148a30>}
<__main__.Node object at 0x103148a30>
{'data': 3, 'next': <__main__.Node object at 0x103148a30>}
<__main__.Node object at 0x1032e08b0>
{'data': 3, 'next': <__main__.Node object at 0x103148a30>}
<__main__.Node object at 0x1032eed60>

[Python] 딕셔너리 내부 구현

파이썬 딕셔너리는 해시테이블과 비슷하게 동작한다.
내부적으로 배열을 사용하며, Key값을 내장된 함수로 인덱스로 변환하여, 인덱스에 값을 저장하도록 구현되어 있다고 한다.

[알고리즘] 해시테이블에서 충돌을 해결하는 방법

링크드리스트나 튜플을 이용하여 옆으로 이어나가는 식으로 충돌을 해결한다.
개방주소법(Open Addressing)을 이용하여, 배열의 남는 공간에 값을 저장한다.

[알고리즘] 해시테이블의 시간복잡도와 공간복잡도

$O(1)$ 의 시간복잡도를 보장한다.
많은 메모리를 차지하여, 공간복잡도 측면에서는 좋지 않다.

[알고리즘] 트리 관련 용어

sibling : 동일레벨의 노드
이진트리 : 자식의 갯수가 최대 2개인 트리
완전이진트리 : 자식의 갯수가 최대 2개이며, 노드의 삽입이 최하단 왼쪽부터 차례대로 채워지는 트리

[알고리즘] 완전이진트리를 배열로 표현하는법

인덱스로 부모와 자식의 관계를 표현하는것이 가능하다.

     3
  4    5
6  7  8  9    [None, 3, 4, 5, 6, 7, 8, 9]

위의 트리에서 아래의 규칙을 따른다.

현재 인덱스 * 2 왼쪽자식의 인덱스
현재 인덱스 * 2 + 1 오른쪽자식의 인덱스
현재 인덱스 // 부모의 인덱스

[알고리즘] 완전이진트리의 높이

각 레벨 별 최대노드 갯수는 $2^k$ 개이다. 이걸 이용하여, 현재 트리의 레벨을 구할 수 있다. 높이가 h이고, 완전꽉찬이진트리에 대한 노드 수를 구하기 위한 식은 $N = 2^(h+1)-1$ 이다. 따라서, $h = log(N+1) -1$ 이기 때문에, 노드의 수에 상관없이, 트리의 높이는 $O(logN)$ 의 높이를 가진다.

[알고리즘] 최대힙에서 노드의 삽입과 삭제

노드의 삽입 트리의 높이 만큼의 시간복잡도를 가진다. 최대힙은 완전이진트리에서 구현되므로, 완전이진트리의 높이인 $logN$ 만큼의 시간복잡도를 가진다.
- 가장 마지막에 넣은 뒤, 부모와 값을 비교해주면서 올라가며 적절한 위치를 찾는다.
노드의 삭제 트리의 높이 만큼의 시간복잡도를 가진다. 최대힙은 완전이진트리에서 구현되므로, 완전이진트리의 높이인 $logN$ 만큼의 시간복잡도를 가진다.
- 가장 첫번째 인자를 삭제하고, 마지막인자를 첫번째로 옮긴 뒤, 해당 노드를 아래로 내리며 적절한 위치를 찾는다.
- 매 단계에서 가장 중요한것은 왼쪽, 오른쪽, 자신 중에서 가장 큰 값을 찾는 것이다.

[회고] 221110

오늘은 하루종일 인강듣고 알고리즘 문제풀고의 반복이었다. 문제를 하나씩 깨나가는 과정이 재미있게 다가왔다. 팀원 중 한 분이 함수의 return의 동작에 대해 혼란스러워 하며, 도움을 요청하였다. 팀원들 모두가 공부를 멈추고 도와드리기 시작했다. print으로 출력되는 것과 값이 return되는 것의 차이점부터 시작하여, 함수를 사용하는 이유까지 설명드렸다.

나는 이 분이 겪는 어려움이 이해가 갔던게, 처음 c언어를 배울때 stadio 어쩌고 적혀있는 것 부터 시작해서, return 적혀있는 것 까지 하나하나 뭔뜻인지 알고싶어했고, 하지만 그 당시에는 그걸 어떻게 검색해야하는지 어떻게 동작하는지 알지못했다. 그 이후에도 return의 용도에 대해 긴가민가하다가, 이런 정의를 보았고, 그 이후로 이해가 확실히 빨라졌다.

return을 만나는 순간, 함수는 중단되며, 해당 함수가 호출된 곳으로 이동한다. 반환된 값이 있다면, 호출된 곳에 반환된 값을 넣어준다.

지금은 당연한 작동방식이지만, 그 때는 당연하지 않았다. 따라서, 이 팀원에게 이 문구를 알려드렸고, 그 이후로 "아하"하시며, 스스로 함수의 호출순서를 읊어가시며 이해하셨다는 시그널을 보내주셨다. 다른 팀원들도 디버깅툴과 여러 레퍼런스를 전달드리며, 이해를 도왔다. '팀'이 개인이 겪는 어려움을 해결 한 것 이다. 다들 열과 성을 다해 설명을 해드렸기에, 그 분이 이해하시자마자 모두들 기뻐하는 반응을 보여주셨다.

어떤 유튜브영상을 보다가, 수학강사 정승제님이 은퇴한 운동선수들에게 사칙연산을 가르치는 영상을 보았다. 정승제님은 중학교과정이상만 가르쳤기때문에, 사칙연산은 '당연히'이렇게 동작하는 것 이라고 생각하셨는데, 운동선수들은 이 '당연한'것에 대해 이해하지 못했다. 정승제님은 사칙연산을 가르치는 경험이 없었기에 처음에는 답답해도 하시고, 어떻게 강의를 시작하셔야 할지 갈피를 잡지 못하셨다.

오늘 내 느낌이 그랬다. 과거에 어려움을 겪었던 경험이 있었지만, 어느순간 return은 나에게 있어 당연하게 동작하는 것이 되어버렸기에, 처음엔 어디부터 어떻게 설명드려야 할 지 갈피를 잡지 못했다. 당연히 '이걸 왜 이해를 못하지?'라는 답답함이 밀려왔으나, 과거의 경험이 떠오르고 나서는 '이해 못할 수 있지'의 포용적인 태도로 변했다.

프로그래밍엔 '당연한 것'은 없다. 모두 0과 1의 조합으로 컴퓨터에 신호를 보내 동작하는 것이고, 내부의 동작은 우리눈으로 정확하게 확인 할 수 없다.

그렇기에 더더욱 익숙한 것도 당연히 여기지 않으며, 탐구하는 자세가 필요하다. 오늘의 일을 계기로 조금 더 익숙해지는 것을 경계하여, 어떤 현상을 바라보는 시야가 좁아지지 않도록 노력해야겠다는 생각을 했다.

[다짐]

익숙해지는 것을 경계하기
상대방의 의견에 온전히 동의하고 말 멈추기
할말이 있어도 적절한 시기엔 참기