2주차에는 본격적으로 알고리즘 문제를 풀기 시작했다.
기본 문제는 15개, Advanced 문제는 5개였고, 이 문제들을 모두 푼 사람을 위한 Extra 문제도 따로 준비되어 있었다. Extra는 LeetCode 문제들로 구성되어 있었다.
문제 난이도 자체가 엄청 높다고 느껴지지는 않았다. Basic은 백준 기준으로 실버 하위 정도의 문제가 많았고, 단순한 코딩테스트 문제뿐 아니라 자료구조나 알고리즘의 개념을 확인하는 문제도 섞여 있었다.
Advanced는 문제에 따라 실버 상위에서 골드 하위 정도로 느껴지는 것도 있었다.
처음에는 생각보다 빠르게 진도를 나갔다. 첫날에 2주차 문제를 거의 다 풀었던 것 같다.
그런데 지금 생각하면 여기서 말하는 '풀었다' 는 표현에는 조금 함정이 있었다.
문제를 오래 붙잡고 있는 걸 답답해하는 편이라, 20~30분 정도 고민해도 방법이 떠오르지 않으면 AI에게 힌트를 받거나 풀이 방향을 확인하면서 넘어갔다.
당연히 그렇게 하면 문제를 해결하는 속도는 빨라진다. 테스트도 통과하고 다음 문제로 넘어갈 수 있다.
문제는 며칠 뒤였다.
화요일 이후부터는 이미 풀었던 문제들의 힌트를 지우고 처음부터 다시 풀어보기 시작했다.
한 번 봤던 문제니까 금방 풀 수 있을 거라고 생각했는데, 막상 코드를 작성하려고 하니 생각보다 낯설었다.
그때부터 조금씩 느꼈다.
한 번 풀었다는 것과 내가 그 문제를 이해했다는 것은 생각보다 많이 다르다.
이해하는 것과 구현하는 것은 또 달랐다
그 차이를 가장 크게 느꼈던 문제가 Advanced의 N-Queen 문제였다.
N-Queen의 핵심 아이디어만 설명하라고 하면 그렇게 어렵지는 않다.
퀸을 한 행에 하나씩 놓으면서 같은 열이나 대각선에 다른 퀸이 있는지 확인한다. 놓을 수 있다면 다음 행으로 넘어가고, 더 이상 놓을 수 없다면 이전 상태로 돌아간다.
전형적인 백트래킹이다.
설명을 읽으면 이해가 된다.
그런데 빈 화면에 코드를 직접 작성하려고 하면 갑자기 이야기가 달라졌다.
어떤 값을 저장해야 하는지, 재귀 함수에는 무엇을 넘겨야 하는지, 종료 조건은 어디에 둬야 하는지, 다음 상태로 넘어갔다가 다시 돌아왔을 때 상태를 어떻게 복구해야 하는지가 한 번에 떠오르지 않았다.
특히 재귀는 해도 해도 헷갈리는 것 같다.
오늘 코드를 따라가면서 "이제 알겠다"고 생각했는데, 다음 날 다시 보면 또 헷갈린다.
한 줄씩 보면 이해되는데 재귀 호출이 여러 단계 쌓이기 시작하면 머릿속에서 실행 흐름을 놓치는 경우가 많았다.
이번 주에는 여기서 하나를 확실히 느꼈다.
알고리즘의 원리를 이해하는 것, 다른 사람이 작성한 코드를 이해하는 것, 그리고 아무것도 없는 상태에서 직접 구현하는 것은 각각 다른 단계다.
지금까지는 첫 번째와 두 번째까지 하고도 '이해했다'고 생각했던 경우가 많았던 것 같다.
자료구조를 왜 배우는지도 조금씩 느껴졌다
문제를 풀다 보니 자료구조 역시 단순히 시험을 위해 특징과 시간복잡도를 외우는 것이 아니라는 생각이 들었다.
같은 결과를 만드는 코드라도 어떤 자료구조를 선택하고 어떤 연산을 사용하는지에 따라 성능이 크게 달라질 수 있었다.
특히 리스트를 인덱스로 순회하면서 pop(i)를 사용하는 코드가 기억에 남는다.
처음에는 원하는 원소가 있으면 그냥 지우면 되는 것처럼 보였다.
하지만 리스트 중간의 원소를 제거하면 뒤에 있던 값들의 인덱스가 앞으로 당겨진다.
순회 중인 인덱스 자체가 바뀌기 때문에 특정 원소를 건너뛰는 문제가 생길 수도 있고, 중간 원소를 삭제하는 연산 자체도 뒤의 원소들을 이동시켜야 하기 때문에 비용이 든다.
아주 사소해 보이는 코드 한 줄인데도 생각할 것이 많았다.
LeetCode의 Move Zeroes 문제도 비슷한 이유로 기억에 남았다.
0을 발견할 때마다 뒤로 밀어내는 방식으로도 답 자체는 만들 수 있다.
하지만 그렇게 구현하면 같은 배열을 여러 번 순회하게 될 수 있다.
반대로 0이 아닌 원소가 들어갈 위치를 따로 관리하면 배열을 한 번 순회하면서 문제를 해결할 수 있다.
굉장히 간단한 문제지만, 오히려 그래서 좋았다.
복잡한 알고리즘을 몰라도
"동작하는 코드"와 "조금 더 나은 코드" 사이에는 차이가 있다.
는 걸 명확하게 볼 수 있었기 때문이다.
이전에는 배열은 배열이고, 큐는 큐고, 연결 리스트는 연결 리스트라고 각각의 개념을 따로 외웠다면, 이제는 조금씩
왜 여기서는 이 자료구조를 사용하는가?
라는 생각을 하게 된 것 같다.
같은 분할 정복인데도 전혀 다르게 생겼다
이번 주에는 Merge Sort와 Quick Sort도 직접 구현했다.
둘 다 분할 정복의 대표적인 알고리즘이다.
큰 문제를 작은 문제로 나누고, 작은 문제를 해결한 결과를 이용해 전체 문제를 해결한다는 큰 틀은 같다.
그런데 실제 코드는 꽤 다르게 생겼다.
Merge Sort는 배열을 계속 절반으로 나눈 뒤, 재귀가 끝나면서 두 배열을 합치는 과정에서 정렬한다.
반면 Quick Sort는 pivot을 하나 정한 뒤 pivot을 기준으로 작은 값과 큰 값을 나누고, 나뉜 구간을 다시 재귀적으로 정렬한다.
둘 다 '나눈다' 는 표현을 사용하지만 실제로 문제를 나누는 방식과 정렬이 일어나는 시점은 다르다.
교재에서 분할 정복이라는 단어만 봤을 때는 조금 추상적으로 느껴졌는데, 여러 알고리즘을 직접 비교하면서 보니 조금씩 감이 잡히기 시작했다.
그리고 여기서도 어김없이 재귀가 등장했다.
이번 주는 정말 재귀에게 계속 얻어맞은 한 주였다.
아직 잘 이해하지 못한 것도 있다
모든 내용을 이해한 것은 아니다.
Basic의 정수론 문제에서 나온 확장 유클리드 알고리즘은 아직도 완전히 이해했다고 말하기 어렵다.
유클리드 호제법으로 최대공약수를 구하는 과정까지는 이해할 수 있다.
그리고 확장 유클리드 알고리즘이
ax + by = gcd(a, b)를 만족하는 x와 y까지 함께 구하는 알고리즘이라는 것도 알겠다.
문제는 재귀가 돌아오면서 왜 x와 y가 특정 식으로 계산되는지다.
코드를 보고 따라가면 결과는 나오지만, 왜 그 식이 자연스럽게 만들어지는지까지는 아직 내 것이 되지 않았다.
예전 같았으면 코드가 동작하면 일단 넘어갔을 것 같다.
지금은 적어도
"여기까지는 이해했고, 여기부터는 이해하지 못했다."
를 구분하려고 한다.
이것도 이번 주에 생긴 작은 변화라고 생각한다.
그래서 알고리즘을 왜 공부하는 걸까
처음에는 알고리즘 공부의 목적을 거의 코딩테스트라고 생각했다.
취업하려면 코딩테스트를 통과해야 하니까 문제를 많이 풀고 유형을 익혀야 한다는 정도였다.
그 생각이 틀린 것은 아니다. 여전히 가장 직접적인 이유 중 하나다.
그런데 이번 주에 문제를 풀면서 알고리즘 공부에서 가져갈 수 있는 것이 그것만은 아니라는 생각이 들었다.
예를 들어 면접에서 단순히
"이 문제를 풀었습니다."
라고 말하는 것보다,
- 왜 처음 방법이 비효율적이었는지
- 왜 다른 자료구조를 선택했는지
- 시간복잡도를 어떻게 줄였는지
를 설명할 수 있다면 그것도 하나의 무기가 될 수 있다.
자소서에서도 마찬가지다.
처음에는 문제를 빠르게 통과하는 데 집중했지만, 다시 풀어보면서 내가 제대로 이해하지 못하고 있다는 것을 발견했고, 이후 힌트 없이 다시 구현하는 방식으로 공부 방법을 바꿨다는 과정 자체가 하나의 성장 경험이 될 수 있다.
물론 실무에서 N-Queen을 구현하거나 퀵 정렬을 직접 작성할 일이 얼마나 있을지는 모르겠다.
하지만 개발을 하다 보면 결국 비슷한 질문을 계속 만나게 될 것 같다.
이 연산은 비싸지 않은가?
굳이 모든 데이터를 확인해야 하는가?
리스트가 아니라 다른 자료구조를 사용하면 더 단순해지지 않을까?
중복되는 계산을 줄일 수는 없을까?
알고리즘 공부는 결국 이런 질문을 반복해서 던지는 연습일지도 모르겠다.
한 번 풀었다고 내 것이 되는 건 아니었다
이번 주에는 문제를 많이 푼 것보다, 이미 풀었던 문제를 다시 풀어보면서 더 많은 것을 배웠다.
문제를 한 번 해결했다는 것과 그 문제를 내 것으로 만들었다는 것은 꽤 큰 차이가 있었다.
아직 재귀는 하루 지나면 다시 헷갈리고, 확장 유클리드처럼 제대로 이해하지 못한 내용도 남아 있다.
그래도 예전보다 한 가지는 조금 더 명확해졌다.
앞으로는 몇 문제를 풀었는지만큼이나,
풀이를 덮은 뒤에도 내가 다시 설명하고 구현할 수 있는지
를 확인하면서 공부해보려고 한다.
