알고리즘 주차 시작 (WEEK01 - WEEK03)
이번 주 부터 3주 동안 팀원들과 함께 다양한 알고리즘 문제를 유형별로 풀게 된다. 단기간 내에 알고리즘 문제 해결 능력을 향상시키는 것이 이번 프로그램의 주요 목표같은데, 매주 목요일에는 1주일간 풀이했던 유형을 중점으로 평가를 보게 된다.
학습 내용
수학
이번 주에는 기본적인 수학 개념을 정리하고, 문제 해결에 어떻게 활용할 수 있는지 배웠습니다. 특히 소수찾는 문제에서 벌써부터 고비인가? 싶기도했다..
이분 탐색
중간값과 비교하여 탐색 범위를 반으로 줄여나가는 방식
시간복잡도 - O(log N)
재귀
하노이 탑에서 처음으로 답을 봤다.. 하노이는 풀때마다 답을 보는 것 같은데 이번에는 좀 제대로 이해하려고 팀원들에게 오랫동안 설명을 들었다.
def hanoi(n, start, mid, end):
if n == 1:
print(f"{start} -> {end}")
return
hanoi(n-1, start, end, mid)
print(f"{start} -> {end}")
hanoi(n-1, mid, start, end)처음에는 하노이 탑 문제가 굉장히 어려웠지만, 재귀의 대표적인 문제인만큼 이해하는데 좀 오래 걸리고 넘어갔던 것 같다.
정렬
정렬 알고리즘은 버블 정렬, 선택 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등 다양한 종류가 있습니다. 각 알고리즘의 시간 복잡도를 비교해 보면, 병합 정렬과 퀵 정렬이 O(N log N)으로 가장 효율적이라는 것을 알 수 있었습니다.
특히 병합 정렬은 안정 정렬이면서도 최악의 경우에도 시간 복잡도가 O(N log N)으로 보장된다는 점이 인상 깊었습니다. 반면 퀵 정렬은 불안정 정렬이고 최악의 경우 O(N^2)의 시간 복잡도를 가지지만, 평균적으로는 가장 빠른 정렬 알고리즘 중 하나라는 점도 흥미로웠습니다.
파이썬에서는 sorted() 함수와 리스트의 sort() 메서드를 통해 간편하게 정렬을 수행할 수 있습니다.
sort()는 tim sort라는 알고리즘을 사용하는데, 병합 정렬과 삽입 정렬을 적절히 조합하여 최적화한 방식이라고 한다!
느낀 점
컴공과로 전과한 이후로 한 순간도 알고리즘에 대해 자신감이 있었던 적이 없던 것 같다.. 초반에는 잘 풀리다가도 조금 어려워지면 금방 포기해버리곤 했었는데, 하지만 취업을 준비하면서 코딩 테스트의 중요성을 깨달았고, 이번 기회에 꼭 알고리즘 실력을 키우고 싶다는 생각이 들었다.
이번주차에는 특히 재귀 문제들에서 어려움을 느꼈지만, 팀원들을 귀찮게한 결과 어느정도 방향성은 잡을 수 있게 되었습니다.(특히 하노이탑하면서 팀원들의 시간을 많이 앗아가버렸다.) 나도 이후에는 좀 내공을 쌓아서 많이 알려주는 입장이 되고싶다는 생각도 했다.
꾸준히 공부해서 solved.ac 골드 상위권을 노리면서...
