[정글] 둘째주. 알고리즘에 미쳐보기
도대체 하루에 몇 문제를 푸는 거지?
불면증이 있었다. 누워있어도 생각이 꼬리를 물고 이어져 잠이 올때까지 오랜 시간이 걸리곤 했는데, 요즘에는 생활이 단순해져서 그런지 바로 잠이 든다. 하루 종일 문제를 풀다 보니 기분 좋은 성취감이 생겨서 잠이 잘 오는 것 같다 :)
같이 푸는 것이 훨씬 더 쉽고 기억에 오래 남는다
이번주는 알고리즘을 풀었다. 쉽지 않았다. 하지만 예전에 혼자서 공부할 때보다 훨씬 재미있었다. 그리고 혼자 풀 때는 골드 레벨 이상의 문제를 아예 손대지 않거나 너무 오랜 시간 붙잡고 있곤 했는데, 여기에서는 과제에 난이도 높은 문제가 많아서 쉬운 것만 편식하듯 풀지 않고 다양한 난이도를 시도해볼 수 있었다. 그리고 동료들과 모여 시간을 재며 푸니까 너무 오래 붙잡게 되지도 않는다. 일정 시간 고민해보고, 모르겠으면 웹이나 주변 동료의 도움을 받아 푼 후 이해하는 데 집중했다.
문제를 해결하는 방법은 정말로 사람마다 다 다르다는 것을 이번에 확실히 깨달았다. 성능이 더 좋은 코드, 쉽게 읽히는 코드, 수학의 원리를 활용한 코드까지 모두의 접근방법은 다 달랐고, 그걸 서로 비교해보면서 한 문제를 두세 번 풀어보는 효과를 얻을 수 있었다.
그리고 모여서 풀고 나서 서로에게 설명해주는 시간을 갖는 것도 유익했다. 혼자서 그러려니 하고 넘어갔던 부분을 되짚어보고, 정확하게 설명하기 위해 논리를 한번 더 정립하는 과정에서 지식을 장기기억으로 넘길 수 있었다. 처음에는 풀지 못했던 문제도 시간이 조금 지난 후에 다시 풀어보았을 때, 정확히 어떤 코드였는지 기억은 나지 않더라도 이미 익숙해진 논리구조이므로 수월하게 한단계씩 떠올려가며 풀어내는 데에 성공했다.
정렬
정렬은 어떻게 보면 쉽고 어떻게 보면 어렵다. 파이썬 내장함수 sort를 사용하면 세상에서 제일 간단한 문제가 되지만, 배열의 요소들을 직접 이동시키며 정렬시키는 로직을 짜면 고민할 것이 많아진다.
버블소트, 셀렉션소트, 인서션 소트, 퀵소트, 머지소트, 힙소트, 카운팅소트
다양한 정렬방법은 장단점이 명확해서 목적에 맞게 사용해야 한다. 반복문 두개로 구현할 수 있는 버블소트나 셀렉션, 인서션소트는 구현이 쉽지만 정렬할 요소가 많아지면 성능이 현저하게 낮아진다. 재귀적인 분할을 이용하는 퀵소트와 머지소트는 요소들의 중간지점을 고민해야 하고, 각 정렬의 단계마다 조건을 걸어서 필터링해주어야 한다.
머지소트는 이론상 퀵소트보다 시간복잡도가 낮거나 비슷하지만, 정렬 단계마다 임시로 요소들을 담아둘 추가공간이 필요해서 이 배열을 생성하는 시간이 오래 걸리는 경우 퀵소트보다 시간이 오래 걸릴 수도 있다. 게다가 임시 배열이 담길 메모리 추가공간이 필요하므로 사용할 수 있는 메모리가 제한적인 경우에는 적합하지 않다.
힙소트의 경우에도 이론적으로는 시간복잡도가 다른 소트에 비해 낮지만, CPU의 지역성(값을 조회할 때 인접한 데이터들을 참조하는 특성)이 낮기 때문에 물리적인 시간은 더 오래 걸릴 수 있다.
파이썬이나 자바스크립트 언어에서 자체적으로 지원하는 정렬 함수는 여러가지 정렬방법들을 적절히 섞어 최적화해놓은 함수이기 때문에 성능이 가장 좋은 정렬방법이다. 그래서 문제에서 정렬을 요구할때 언어에 내장된 정렬함수가 있다면 그걸 사용하는 것이 좋다. 하지만 다소 역설적이게도, 정렬을 공부하기 위해서는 성능이 좀 떨어지더라도 직접 로직으로 구현해보아야 한다
재귀, 완전탐색, 분할정복
재귀와 완전탐색은 의외로 간단하다. 반복해야 하는 동작을 하나의 단위로 추려서 조건에 맞게 배치해주면 되기 때문에 직관적으로 구현할 수 있다. 다른 유형에 비해 조금 더 쉽게 느껴졌던 문제유형이기도 하다.
원칙적으로 모든 반복문은 재귀함수로 대체할 수 있다. 그러나 경우에 따라서는 재귀함수의 깊이가 너무 깊어지면서 중복으로 탐색하는 구간이 너무 많아져 시간복잡도가 기하급수적으로 증가할 수 있기 때문에, 반복문이 유일한 해답일 때도 있다.
만약 입력값이 제한적이라서 재귀호출의 깊이가 지나치게 깊어지지 않고, 동일한 패턴이 반복된다면 재귀함수로 푸는 것이 알맞다.
https://www.acmicpc.net/problem/1074
https://www.acmicpc.net/problem/2630이분탐색
이분탐색은 직관적이지만 디테일한 부분이 아주 중요하고, 개인적으로 이 디테일이 너무 어렵다. 디테일이라는 것은 예를 들면 양끝에서 시작해서 절반씩 탐색범위를 줄여 나가다가 정확하게 어느 지점에서 멈추는가이다. 탐색을 중지하는 지점이 중요한 경우는 명확한 하나의 타겟이 없고 최대값(Upper Bound)이나 최소값(Lower Bound)을 찾는 경우이다.
멈추는 지점에 확신이 없다면 전역변수를 미리 선언해두고, 한번 탐색할 때마다 찾아지는 값이 이 전역변수보다 큰지 작은지 따져서 갱신해주는 방법도 있다. 가령 최대값을 찾는 문제라고 할 때, 탐색 도중 일단 최대값을 찾기만 하면 그 다음 탐색에서 그보다 작은 값이 나오더라도 이미 찾은 최대값은 가지고 있기 때문에 안전하게 답을 도출할 수 있다. 하지만 근본적으로는 정확하게 멈출 지점을 아는 것이 중요하다.
