이제 1년하고 1달 조금 넘게 코딩을 하면서, 알고리즘이라고는 실버 2주, 골드 1달, 플래티넘 1달 정도밖에 풀어보지 않은 짬밥에 뭘 얼마나 유용한 걸 설명할 수 있을 지는 모르겠지만
그래도 내 생각을 정리할 목적으로 써보는 중.
참고로 저자 구종만님의 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략에 나오는 내용과 비슷한 말을 할 수도 있다.
카피할 의도는 없는데, 애초에 날 처음 가르친 친구가 이렇게 세뇌 교육을 시켜놨던 터라 나도 모르겠다.
목차
1. 알고리즘과 문제 해결 능력
2. 전략적 접근
3. 알고리즘을 개선하는 흐름
4. 모든 곳에 통용되는 알고리즘 따윈 없다.
1. 알고리즘과 문제 해결 능력
코테 준비를 많이 해보지 않은 시점에서 문제를 슥슥 해결해내는 사람들을 보면 '저 사람은 정말 다양한 알고리즘을 이해하고 있구나!'라고 해석하기 마련이다.
나도 그랬었고, 지금의 내가 코테 준비를 처음 하는 사람들을 만나보면 대부분 그런 반응이다.
이건 반은 맞고, 반은 틀렸다고 할 수 있다.
🤔 알고리즘을 많이 알면, 문제는 그냥 풀릴까?
알고리즘을 많이 아는 것은 수학 공식을 이것저것 다 외우고 있는 사람이라면,
문제 해결 능력이 뛰어난 사람은 자신이 알고 있는 수학 공식을 뜯어 고치고, 혹은 새로운 공식을 유도해낼 수 있는 사람이다.
다양한 알고리즘을 알고 있어도 응용하지 못 한다면 골드 단계 쯤에서 '역시 난 재능이 없어'라는 말과 함께 손절을 치게 수도 있다.
굳이 여러가지를 알고 있다고 하지 않더라도 궁금하다면 실버 단계의 dfs, bfs문제를 줄창 풀어보면 된다.
여기까진 기본 로직을 외우기만 하면 쉽게 풀리기 때문에 내가 이 알고리즘을 온전히 이해하고 있다고 착각하게 된다.
보통 이 단계에서 골드로 넘어가면 머리가 깨지고 어디서부터 잘못된 건지 갈피를 잡지 못 한다.
이 문제는 암기와 이해에서 비롯한다.
모든 문제에서 통용되는 무적의 알고리즘 따위 존재하지 않는다.
골드 정도 단계에서는 알고리즘을 "사용할 수 있느냐"가 아니라 "이 로직을 이해하고 조건에 맞게 바꿀 수 있느냐?"를 묻는다.
(물론 기하학 알고리즘의 경우엔 플래티넘 단계부터 기초 알고리즘이 나오긴 한다..)
✒️ 내가 처음 코테를 준비한 과정
내 친구는 나를 강하게 키웠다.
코테 공부를 어떻게 시작해야 할지 몰라서 도움을 청했더니 한 달 안에 실버 부시기라는 프로젝트 하에 하루에 구현 1문제, 수학 1문제, 알고리즘 1문제를 랜덤으로 던져줬다.
내가 이때 할 수 있는 거라고는 고작 재귀 함수를 사용하는 방법 정도였는데, dfs니 bfs니 이런 알고리즘 존재도 모르는 상태로 일단 풀게 시켰다.
'에라토스테네스의 체'라는 기술로 소수를 빠르게 구하는 방법도 알려주지 않고, 어떤 알고리즘을 써야 하는지 힌트조차 주지 않고 스스로 생각하고 로직을 구현하게 시켰다.
다른 사람의 코드를 참조하지 않되, 문제 풀이가 끝나면 코드 설명을 시키고 다른 사람의 코드를 찾아보게끔 했다.
심지어 첫 bfs 문제가 그 당시에 골드 4였다. (진짜 너무 강하게 키움)
이러다 보니, 한 문제를 푸는데 짧아도 하루 2시간, 길면 이틀, 삼일 이상 소모하여 거의 하루종일 로직 연구만 거듭했다.
내가 만든 로직이 알고보니 dfs라는 알고리즘이라는 이름으로 존재했었고, 알고리즘 문제를 수학문제처럼 풀어버리기도 했다.
그렇다면 여기서 의문. 나는 알고리즘이라고는 쥐뿔도 모르는데 어떻게 골드를 풀 수 있었을까?
여기서 단순히 "그건 니가 머리가 좋아서"라고 답할 거라면 더이상 이 포스팅을 볼 필요가 없다.
💡 문제 해결 능력을 키우기 위해서
대부분의 처음 시작하는 사람들이 오해하는 것이 코테 스터디와 알고리즘 스터디는 결이 다르다.
알고리즘 스터디에서는 어떤 자료구조가 있고, 어떤 알고리즘들이 있는지를 중점으로 공부한다면
코테 스터디는 문제를 읽고, 어떻게 풀어낼 수 있을지가 논제가 되어야 한다.
여기서 많은 알고리즘과 자료구조를 이미 알고 있다면 접근이 다소 수월해질 수는 있지만 문제 풀이와 직결된다는 보장은 없다.
오히려 알고리즘적 사고에 갇혀버리기 때문에 다른 방법으로 해결할 수 있는 길을 스스로 막아버리게 될 수도 있다.
알고리즘을 이해한다는 것은 눈 감고도 로직을 칠 수 있는 단계가 아니라, 변수 하나하나의 위치 선정 이유와 존재 이유에 대해 타인에게 설명할 수 있는 단계이다.
"bfs에선 큐를 쓰고, visited 라는 배열을 이용하더라!"가 끝이 아니라, 도대체 왜 자료구조는 큐여야하고 visited라는 네이밍의 배열을 사용하는 가에 대해 설명할 수 있어야 한다는 뜻이다.
나는 알고리즘에 사로잡히지 않은 환경에서 문제를 풀기 위해 어떤 것들이 필요한지를 끊임없이 고민하면서 로직을 만들었었다.
변수 네이밍부터 위치 선정과 최적화까지 혼자 고민을 거듭하면서 내겐 어느정도 새로운 알고리즘을 보아도 어느정도 데이터의 흐름을 유추할 수 있는 능력을 키울 수 있었기 때문에
새로운 알고리즘을 공부해도 단순히 눈으로 읽어들이는 것이 아니라, 로직의 흐름을 파악하고 분석하는 것이 습관화 되어 있다.
설령 내 힘으로 도저히 못 풀겠는 문제를 발견하고 다른 사람의 코드를 참조하게 된다고 하더라도
내가 참조하고 있는 코드는 대체 어떤 이유로 이런 변수를 할당하고, 이 위치에 선언하였고, 이런 로직을 만들었는지 철저하게 분석하는 과정이 필요하다.
아이디어를 떠올리는 학습은 포기하더라도, 그 사람이 어떤 생각을 가지고 이 아이디어를 짜냈을 지에 대해 이 악물고 흐름을 좇다 보면 어느샌가 그 아이디어를 다른 문제에서 적용할 수 있게 된다.
다시 말하지만 코드 하나하나에 존재 타당성에 대해 고민하고, 눈여겨 보아야 한다.
우리가 배우는 알고리즘들은 하나의 정형화된 로직일 뿐이기 때문에 단순히 외우는 것이 아니라 코드 하나하나를 음미한다는 생각으로 볼 줄 알아야 한다.
이건 단순 알고리즘 공부를 위함이 아니라, 전반적인 코드를 보는 눈을 향상시킬 수 있는 매우 좋은 방법이다.
2. 전략적 접근
나는 문제를 풀기 위해서 몇 가지 염두해두는 것들이 있다. 일련의 접근 순서에 가깝다.
물론 사람마다 스타일이 다르기 때문에 그대로 따라할 필요는 없고 참고만 하면 된다.
1. 문제 잘 읽기
항상 "문제를 잘 읽어라"라고 사람들한테 말해도 나중에 틀린 이유를 찾아보면 "문제를 잘못 읽어서요 ㅎㅎ..."라는 답변을 받을 때가 많다.
어쩔 수 없다. 나도 플래티넘은 30분 컷 내놓고 실버에서 문제 잘못 읽고 2시간 걸린 적이 있다.
이건 조금 다른 조건이긴 하지만 올림피아드 챔피언들 조차 종종 저지르는 실수다.
문제를 대충 훑어보고 결과를 머릿속에서 추측해버리는 판단 실수로 인해 몇 배의 시간적 손해를 입게 될 수 있다.
특히나 대회장에선 타이머가 돌아가고 있기 때문에 더더욱 마음이 급해서 저지르게 되는 실수이다.
반드시 문제를 잘 읽고 멋대로 해석하지 말자.
특히, 이 단계에서 문제 조건을 살펴보는 것은 매우 필수적인 단계이다.
2. 계획
N과 M의 범위가 1보다 크고 100,000보다 작은 조건이 있다고 생각해보자.
만약, int 타입의 크기가 arr[N][M]인 2차원 배열을 선언한다고 치면 4byte * 100,000 * 100,000 크기가 선언되었으므로 약 152587.89Byte 공간이 할당되어 시작도 못해보고 탈락한다.
혹은 시간 복잡도가 O(N*M)인 알고리즘을 사용하게 되면 약 백 억이라는 값이 나오므로 1~2초 내의 시간 제한을 뚫는 데도 무리다.
이제 당신은 문제를 풀기 위해 새로운 자료구조를 사용하거나, 배열의 사용 방식을 바꾸어 크기를 조절할 수 있다.
시간 복잡도를 log 단위로 줄이고자 어떤 알고리즘을 택할지, 나머지 부분은 어떻게 구현할지 대략적으로 선택하고 로직을 구상해야 한다.
3. 추상화
bfs 함수에 visited라는 배열의 용도를 물었을 때, 단순히 "방문 판단을 위한 배열인데요?"라고 답하면 썩 좋은 답변이 아니다.
방문 여부를 체크하는 주체는 누구고, 굳이 전역으로 설정해야할 이유가 있는지 등을 따져보아야 한다.
문제 조건을 직관적으로 이해하기 위해서는 나름대로 문제를 재정의하는 단계를 거쳐야 하고, 추상화를 통해 로직에서 어떻게 다룰 것인지를 생각해야 한다.
현실 세계의 문제를 프로그램에서 모두 구현해서 다루기엔 한계가 있기 때문에, 본질만을 다루기 위해서 어떻게 할지 고민하는 것은 단순히 문제 풀이를 위한 것만이 아니라 개발자의 미덕이라고 볼 수 있다.
예를 들어, dp에 모든 노드에 대한 각각의 함수 그래프를 모두 저장하고 이 함수들을 전부 더하는 연산을 수행하기보단 특정 시점(변곡점이나 꼭짓점 등)의 데이터만 다루면 된다면 함수 데이터를 전부 넣을 필요는 없다.
4. 검증
코드를 작성하기 이전에 내가 구상한 로직의 적합성에 대해 판단해야 한다.
정상적으로 돌아간다고 치고, 과연 시간 제한 내에 통과할 수 있을지에 대해 고민해보는 단계이다.
코드를 작성해보면서 판단하면 시간이 오래 걸린다.
시작하기 이전에 판단하고 코드를 작성해야한다.
5. 구현
구상이 끝났으면 구현을 하면 된다.
검증 단계에서 아무리 완벽하다고 생각되는 로직을 떠올렸어도 구현하지 못 하면 끝이다.
사실 뭐 누구나 아는 너무 중요한 단계라서 딱히 할 말은 없지만, 코테는 문제 하나하나마다 코드를 밑바닥부터 다시 써야 한다는 특징이 있다.
다른 웹 프로젝트 같은 경우에는 코드가 더러워지면 더러워지는 대로 쓰지만, 여기선 그렇지 않다.
코드를 깔끔하고 직관적이면서, 효율적으로 로직이 돌아갈 수 있도록 항상 신경쓰자.
정말 나중에 모든 분야에서 도움이 될 것이다.
6. 회고
나는 다른 사람의 코드를 참고하는 걸 별로 좋은 방법이라고 생각하지 않는다.
하지만 초보자 시절에 정말 해결하지 못 하겠는데 몇 시간이고 붙잡고 있기엔 시간 낭비인 것도 사실이다.
그래서 보긴 보더라도 반드시 내가 참고해서 작성한 코드만이라도 정확히 이해하고 넘어가야 한다.
이해하고 넘어간다는 건 "백준에 제출해봤는데 통과했다."가 아니라 내 코드를 다른 사람한테 완벽하게 설명할 수 있다는 것을 의미한다.
보통 한 가지 문제는 한 가지 알고리즘으로 해결되지 않는다.
더 많은 구현 방법이 존재하고, 당신이 해결한 방법은 그 중 고작 하나에 불과하다.
반드시 다 풀고 나서도 다시 풀어보거나, 다른 사람은 어떻게 풀었을 지 찾아보고 이해해보자.
3. 알고리즘을 개선하는 흐름
Brute force, 소위 전탐색이라 불리는 이 방법은 가장 무식한 알고리즘으로 불린다. (암호학 쪽에서는 무차별 대입 공격이라는 이름으로 불리는 듯 하다.)
물론 코테에서 브루트 포스를 쓸 일은 없겠지만, 어떻게 보면 브루트 포스는 최악의 방법일지언정 무조건 문제를 해결 가능한 알고리즘이다.
즉, 내가 해결할 수 없는 문제를 발견했을 때는 브루트 포스부터 점근적 전개를 통해 아이디어를 개선시킬 수 있다.
한 가지 문제를 풀어보도록 하자.
algospot.com :: FENCE
울타리 잘라내기 문제 정보 문제 너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체
algospot.com
이 문제는 알고리즘에 대해 완전히 무지했던 당시에 읽었던 내용인데 너무 충격적이라 아직까지도 모든 내용이 기억난다.
단계별로 접근해보자. (알고리즘 문제해결 전략 7장)
1. Brute Force
가장 무식한 방법은 이중 반복으로 긁으면 된다.
현재 위치에서 N번째 울타리까지 최소 높이의 울타리를 찾아서 width를 곱해주었을 때 최댓값을 찾으면 된다.
하지만 이 방법은 O(N^2)의 시간복잡도를 가지므로 통과할 수 없다.
int bruthForce() {
int result = 0;
for (int start = 0; start < n; start++) {
int min_height = height[start];
for (int right = start; right < n; right++) {
min_height = min(min_height, height[right]);
result = max(result, (right - start + 1) * min_height);
}
}
return result;
}
2. 분할 정복
경우를 잘게 나누어 작은 단위의 문제를 생각해보자.
N개의 판자를 절반으로 나누어 재귀를 돌린다.
이렇게 되면 판자에서 최대 직사각형은 세가지 영역에서 발견될 수 있다.
- 왼쪽 영역에서 최대 직사각형
- 오른쪽 영역에서 최대 직사각형
- 걸친 부분에서 최대 직사각형
걸친 부분에서 최대 직사각형은 언제나 경계선상에 존재함을 떠올리면 쉽게 구할 수 있다.
중간의 사각형 mid, mid+1 지점에서 더 낮은 높이의 울타리를 탐색한다.
우선 2 * min_height 크기의 직사각형을 구했다면, 다음은 좌우로 확장해보아야 한다.
그렇지만 여기서 무턱대고 좌우로 한 번씩 늘려보면 고작 2칸을 이동하는데도 3번의 반복수행을 필요로 한다.
따라서 최적화를 해주기 위해 고민을 해보면 좌, 우 중에 더 높이가 높은 쪽으로 확장해야 보다 넓은 범위의 직사각형을 구할 수 있다는 결론에 이른다.
"7 8 6 6 6 6 6 6 이라는 배열의 울타리면 어떻게 하나요?"라는 질문을 한다면 이 알고리즘이 분할 정복임을 떠올리자.
우측 영역과 좌측 영역의 최대 직사각형은 재귀가 찾아올 것이다.
내가 필요한 건 당장 중앙에서 발견할 수 있는 가장 큰 직사각형이다.
위의 경우에는 녹색 영역이 아닌 붉은 색 영역으로 직사각형을 확대했다가 다시 좌측으로 직사각형을 확대하며 최댓값을 찾아내면 된다.
int recur(int left, int right) {
if (left == right) return height[left];
int mid = (left + right) / 2;
int result = max(recur(left, mid), recur(mid+1, right));
int l = mid, r = mid+1;
int h = min(height[l], height[r]);
while (left < l || r < right) {
if (r < right && (l == left || height[l-1] < height[r+1])) {
r++;
h = min(h, height[r]);
} else {
l--;
h = min(h, height[l]);
}
result = max(result, h * (r-l+1));
}
return result;
}
정당성을 증명하는 과정은 건너뛰고, 이 로직이 합당하다고 가정한다면 문제를 최소단위로 나누어 O(n)만큼의 너비 판단 후 병합하는 과정을 통해 최종적으로 O(NlogN)의 시간복잡도를 가진다.
물론 이 방법으로도 충분히 문제를 해결할 수 있겠지만, 더 빠른 알고리즘 또한 존재한다.
3. 스위핑 기법과 스택을 활용한 선형 시간 알고리즘
이 문제는 O(N)의 선형 시간으로 해결할 수 있는 방법이 존재한다.
어떤 테스트 케이스에서 최대 직사각형을 찾았을 경우, 직사각형의 높이는 가장 낮은 울타리 i의 높이와 같고 이 사각형을 막고 있는 판자들의 번호를 l[i], r[i]라고 했을 때, (r[i] - l[i] -1) * height[i]를 통해 쉽게 값을 유도할 수 있을 것이다.
하지만 r[i]와 l[i]를 구하는 간단한 로직은 O(N^2)만큼의 시간 복잡도를 요구한다.
브루트 포스부터 지금까지 알고리즘을 개선하면서 변하지 않는 하나의 규칙성이 존재했다.
최대 직사각형의 높이는 영역 내의 가장 낮은 울타리에 의해 결정된다는 것이었다.
N개의 울타리를 차례로 훑을 경우 3가지 케이스로 나누면 다음과 같다.
- height[idx] > height[idx + 1]
현재 판자가 영역을 넓히고 싶어도 다음 판자에 의해 가로 막히게 된다. 따라서 현재 인덱스가 정의하는 최대 직사각형을 판단할 수 있다.
중요한 것은 이제 height[idx]의 정보는 더이상 필요가 없게 된다.
다음으로 더 확장하게 된다고 한들 최대 높이는 height[idx + 1]에 의해 지배되기 때문이다.
따라서 현재 판자를 데이터에서 지워버린다.
- height[idx] < height[idx + 1]
현재 판자가 다음 판자의 확장을 가로막고 있긴 하지만 right[i]를 알 수 없으므로 일단 저장한다.
- height[idx] == height[idx + 1]
현재 판자와 다음 판자의 높이가 완전히 동일하다.
따라서 현재 판자의 정보는 더이상 필요없기 때문에 마찬가지로 지워버린다.
위에서 구한 일련의 과정을 일반화하면 대충 감을 잡을 수 있다.
i번 판자의 기준에서 왼쪽에는 언제나 자신보다 낮은 울타리만이 존재해야만 한다.
이때, 현재 판자의 idx만 기억해줄 수 있다면 이 방법을 구현하는 건 어려운 일이 아니다.
가장 먼저 스택에 -1번 인덱스 위치에 0 높이의 울타리 l[i]를 넣어준다.
((-1, 0)이라고 적었어야 했는데 실수 ㅎ)
아직까진 r[i]가 정해지지 않았으므로 그대로 스택에 쌓는다.
높이 1의 울타리가 들어옴으로써 0번 울타리의 l[0]과 r[0]이 정의되었으므로 width와 height 값을 이용해 최대 직사각형의 너비를 구할 수 있을 것이다.
이대로 값을 한 번에 쭉 넣어보자.
가상의 울타리 상에서 0번 인덱스의 울타리 정보는 더이상 존재하지 않는다는 걸 기억하자.
문제는 여기서 발생한다. 6번째 인덱스의 높이가 3인 울타리가 들어옴으로써 7, 6, 5 높이의 울타리가 차례로 방을 빼야하는데, 어떤 로직이 수행되어야 할까?
(5, 7)의 기준에서 (l[i]와 r[i] 사이의 거리합 - 1) * i 높이가 된다.
여전히 왼쪽 울타리는 r[i]보다 크기 때문에 최대값을 갱신할 수 있다.
i번 째를 기준으로 봤을 때, 확장을 가로막는 l[i]와 r[i] 사이의 거리는 3이 된다.
따라서 최댓값은 18이 되며, 높이 5의 울타리에 대해서도 똑같은 작업을 수행하면 최대 넓이 20의 직사각형을 찾을 수 있다.
그리고 마지막에 (-1, 0)과 같은 개념으로 (N, 0)의 울타리를 stack에 push하여 모든 stack을 끄집어내면 연산은 끝난다.
이 과정은 단 O(N) 시간복잡도 내에 로직을 수행할 수 있게 된다.
int solveStack {
int result = 0;
stack<int> st; stack.push(make_pair(-1, 0));
for (int i = 0; i <= n; i++) {
if (i == n) st.push(make_pair(i, 0));
while(!st.empty() && st.top().second >= height[i]) {
int h = st.pop().second;
int w = st.pop().first;
width = (st.empty()) ? i : i - st.top().first - 1;
result = max(result, h * width);
}
st.push(make_pair(i, height[i]));
}
return result;
}대충 블로그에 바로 작성한 코드라 정상적으로 돌아갈진 모르겠지만 ㅋㅋ 얼추 이해할 수 있을 듯.
4. 모든 곳에 통용되는 알고리즘 따윈 없다.
1915번: 가장 큰 정사각형
첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다.
www.acmicpc.net
이 문제도 울타리 문제 처럼 접근이 가능하다.
하지만 울타리 문제에서 엄청난 시간 복잡도 단축을 자랑했던 선형 시간 알고리즘이 똑같이 단축될까?
모든 graph를 히스토그램화 시켜 해당 row에서 최대 높이를 구한다.
1는 1x1 블럭이고 5는 1x5 블럭이 된다.
이렇게 문제를 변형시키면 위의 문제처럼 똑같이 수행할 수는 있지만
O(M) 과정을 N번 반복해야 하므로 대략 O(N*M)의 시간 복잡도가 소요된다.
이렇게 되면 차라리 훨씬 간단하게 dynamic programming으로 해결하는 게 쉬울 수 있다.
이 문제는 dp로 해결해도 O(N*M)의 시간복잡도를 가지기 때문이다.
(솔직히 DP도 필요없다. 브루트 포스로도 O(N*M) 내에 해결하려면 할 수 있을 거 같다.)
즉, 어떤 곳에선 치트키처럼 쓰일 수 있는 알고리즘일지라도 그 범위는 매우 한정적이라는 의미가 된다.
다른 경우로는 O(N*M)의 간단한 로직으로 해결할 수 있는 문제를 어렵게 풀어서 O(N)으로 풀었을 때 그 허무함은 느껴봐야 안다. (기분 좋지 않고, 진짜 허무함...)
닭 잡는데 소 잡는 칼 쓰지 말라는 말을 괜히 하는 것이 아니다.
문제를 풀기 전에 알고리즘 분류표를 보면 다양한 아이디어가 알고리즘에 갇히게 된다.
다양한 로직을 만들어내는 것이 아니라, 특정 로직 안에 갇혀서 문제에 접근하는 굉장히 좋지 않은 습관을 들이게 될 수도 있다.
알고리즘 공부가 아니라 코딩 테스트 준비를 하는 사람들이라면, 적어도 골드 단계 이상에선 알고리즘 분류표를 찾아보지 말고 처음 문제에 접근하는 방법부터 공부하는 것이 바람직하다.