[WIL] 항해99 week3 (05/23 - 05/29)

 

들어가며

벌써 항해 3주차인데 알고리즘 주차는 2주차...? 항해 시작한 지는 얼마 안된거 같은데 알고리즘 주차 시작한 지는 한달이 훌쩍 넘은 것 같다. 그만큼 열심히 보낸 일주일이라는 말이겠지!

 

이번주 WIL도 여느때와 같이 지난 일주일 간 배운 내용을 간단히 복습하고, 회고록을 작성해보고자 한다!

 

---

 

트리 / 이진 트리

나무를 뒤집어 둔 모양으로 생긴 트리. 그래프와 비슷하게 생겼지만 차이점은 분명히 존재한다.

트리는 순환 구조를 갖지 않는 그래프라는 점과 단방향 그래프라는 점, 단 하나의 부모 노드만 갖는다는 점이 그래프와 다르다.

 

이진 트리는 각 노드가 최대 두개의 자식을 가진다는 특징이 있는 트리의 일종이다.

 

[TIL] 05/23 항해99 13일차 - 트리, 이진 트리, 문제풀이

[TIL] 05/23 항해99 13일차 - 트리, 이진 트리, 문제풀이

 

 

이진 탐색 트리

이진 탐색 트리는 이진 탐색과 연결리스트의 아이디어를 결합한 자료구조의 일종이다. 평균적으로 O(log n)의 시간 복잡도를 갖는다.

 

이진 탐색 트리의 특징은 부모 노드가 왼쪽 자식 노드보다 크고, 오른쪽 자식 노드 보다 작다는 것과 모든 서브 트리가 이와 같은 규칙으로 이루어져있어야 한다는 점이다.

 

[TIL] 05/24 항해99 14일차 - 이진탐색트리, 문제풀이

[TIL] 05/24 항해99 14일차 - 이진탐색트리, 문제풀이

 

 

힙

힙은 최소값과 최대값을 빠르게 찾기 위해 고안된 완전 이진트리이다. 

 

부모가 항상 자식보다 작거나(최소힙) 크다(최대힙)라는 특징만 존재할 뿐 반드시 정렬된 자료라는 보장이 되어있지는 않다. 

 

[TIL] 05/25 항해99 15일차 - 힙, 문제풀이

[TIL] 05/25 항해99 15일차 - 힙, 문제풀이

 

 

 

이진 탐색

이진 탐색은 정렬된 자료를 중앙값을 기준으로 절반씩 줄여나가면서 빠른 속도로 목표값을 찾기위한 알고리즘이다.

정렬되지 않은 배열은 사용할 수 없다. 

 

[TIL] 05/28 항해99 18일차 - 이진탐색

[TIL] 05/28 항해99 18일차 - 이진탐색

 

 

+ 

궁금한 점 - 정렬되어있지 않는 배열에서 최대값을 찾을 때, 힙과 이진탐색 중 어떤게 더 빠를까?

 

항해99 수강생 윤교님의 도움을 받아 테스트를 진행해보았다!

해당 테스트는 파이썬에서 제공하는 모듈을 이용해서 진행했으므로 직접 구현했을 때의 시간은 지금이랑 다를 수 있음!

 

 

테스트 코드 by 윤교님

import copy
import heapq
import random
import bisect
import time

sample1 = random.sample(range(1,10000001),10000000)
sample2 = copy.deepcopy(sample1)
print(f"최대값 : {max(sample1)}")


def test_heap2(lst):
    print(heapq.nlargest(1,lst)) # 리스트를 힙으로 바꾼 후 최대값 반환


def test_bs(lst):
    lst.sort() # O(n log n)
    idx = bisect.bisect_left(lst,10000000) # O(log n)

    if idx < len(lst) and lst[idx] == 10000000:
        print(lst[idx])
    else:
        print(-1)


start_time1 = time.process_time()
test_heap2(sample1)
end_time1 = time.process_time()
print(f"작동시간_heap : {end_time1 - start_time1}")

start_time2 = time.process_time()
test_bs(sample2)
end_time2 = time.process_time()
print(f"작동시간_bs : {end_time2 - start_time2}")

 

테스트 결과

최대값 : 10000000
[10000000]
작동시간_heap : 1.371295
10000000
작동시간_bs : 6.015103

 

 

여러 번의 테스트 결과 생각보다 큰 차이를 보인다. 사실 생각해보면 당연한 결과일 수 있겠다.

heapq.nlargest(1, lst)의 정확한 시간복잡도는 찾지 못했지만 해당 모듈은 리스트를 힙으로 변환한 후 가장 큰 값을 찾는 과정을 수행하기 때문에 아마 heapify()의 O(n)과 얼추 비슷하지 않을까 한다. 

 

이진 탐색의 경우에는 '정렬되지 않은 배열' 이라는 가정이 있으므로 정렬 과정을 거쳐야하는데, 파이썬의 sort()는 O(n log n)의 시간 복잡도를 가지므로 힙보다는 느린 속도를 낸다!

 

 

그럼 이미 정렬되어있는 배열에서는 어떨까?

 

테스트 결과

최대값 : 10000000
[10000000]
작동시간_heap : 0.19232099999999974
10000000
작동시간_bs : 0.0

 

 

예상과 같이 정렬된 배열에서는 이진 탐색이 빠르다. 당연하게도 여기서 최대값이 아니라 중간값을 찾는 연산을 수행했을 때에도 이진 탐색이 압도적으로 빠른 결과를 리턴한다.

 

결론 - 정렬된 배열에서는 이진 탐색을, 정렬되지 않은 배열에서 최대/최소값을 찾을 때는 힙을 쓰자.

테스트에 도움주신 윤교님 감사합니다!!

 

 

 

 

회고록

알고싶은 것도 하고싶은 것도 많은데 체력이 따라주지 않는 한 주였다. 알고리즘도 잘하고 싶고, cs지식도 많이 가져가고 싶은데 몸은 한개라서 무언가를 자꾸 미뤄야한다는게 마음에 들지 않았다. 의욕이 모든 걸 해결해주는 건 아니더라.

 

 

내 일주일 간의 감정변화를 그림으로 그리면 어린왕자에서 나오는 코끼리 그림이 나오지 않을까

생텍쥐페리의 어린왕자에 나오는 보아뱀 그림

 

 

이런 무지막지한 감정 변화에도 한가지 스스로를 칭찬해주고 싶은 부분은 그럼에도 불구하고 TIL은 꾸준히 썼다는 점이다. 이젠 집착 수준으로 안쓰면 자다가도 일어나서 쓰는 수준인데, 왜 이렇게까지 열심히 써? 하는 물음이 생기기도 한다.

 

가장 큰 이유는 면접에서 좋은 점수를 따기 위함이라고 할 수 있겠다. 꾸준함은 언제나 좋은 평가를 받기 마련이고, 내가 어떤 상황에 부딪히더라도 한가지를 버리지 않았다는 점은 그 사람의 성실함을 표현할 수 있는 지표라고 생각한다. 만약 같은 능력치를 가진 두 사람이 면접을 보러왔을 때 눈으로 보고 판단할 수 있는 무언가가 있는 사람이 선택될 확률이 높지 않을까?

 

두번째 이유는 이렇게라도 해야 나태해지지 않아서이다. 알고리즘 주차가 시작된 이후로 포기하고 싶은 순간들이 종종 있었는데, TIL은 써야지! 하는 생각 하나로 책상 앞에 앉아있었다. 덕분에 구현은 못해도 개념은 머리에 확실히 집어넣을 수 있었다. 알고리즘 공부를 시작한 지 고작 2주차인데 이 정도면 장족의 발전이지. 나 7개월차 애기 백엔드 취준생, 그래도 전공생분들이랑 대화 정도는 나눌 수 있는 단계까지 올라왔다고 당당하게 말할 수 있다.

 

 

다시 코끼리의 머리까지 의욕을 끌어올려서 다음 한 주도 화이팅하자!!

 

 

 

---

오늘의 한마디 by 아영님 - 오늘 일찍 잔다고 내일 일찍 일어나지는 않는다.