정글 2주차 알고리즘 후기

1주차 알고리즘이 끝나고 2주차 알고리즘을 하는 중이다.

지금 목요일부터 금토일 이렇게 4일 지났는데 일단 40문제 다 풀거나 답보고 이해한 상태다.

내일은 틀렸거나 풀 때 힘들게 푼 문제들 다시 볼 시간이다.

한 10문제 정도 되는 것 같은데 이것들 다 복습하는 시간을 가져야겠다.

 

코드를 적다가 다음에 어떤 코드를 적어야 하는지 모를 때가 있다.

이때 잠깐 생각을 코드의 영역에서 한글의 영역으로 전환해서 다음에 내가 작성할 코드의 내용을 한글주석으로 작성해준다.

이렇게 하면 한창 코드를 작성하다가 멍해지는 타이밍에 다시 목표를 상기시킬 수 있다.

 

그리고 이번 알고리즘 팀은 정말 체계적으로 만나는 시간대도 오전 10시, 오후 4시, 오후 8시 이렇게 세 타임을 만들어서 각자의 코드를 설명하고, 코드 제출용 그룹 깃헙 저장소를 만들어서 이곳에 풀어서 올리고 각자 진도를 체크하는 리드미도 있다.

 

이번 조는 아주 순도 100%의 닭가슴살처럼 모든 것이 체계적이고 효율적으로 이루어지고 있다.

밥도 12시, 6시에 딱 맞춰서 다른데 안가고 학식만 먹고 남은 시간으로 문제를 푼다.

그래서 하루종일 루틴화된 코드작성기계가 된 것 같은 기분이 든다.

이렇게 한 달만 하면 코딩고수가 될 것 같다.

 

풀 때 어려웠거나 틀리고 답본 후 이해한 내용들

 

괄호의 값

- 이전 문제가 올바른 괄호문자열인지 판단하는 문제였고 그것의 상위 문제라고 볼 수 있다. 괄호 안에 괄호 안에 괄호 이런식으로 되어있기 때문에 처음에는 재귀호출로 문제를 해결하려고 했었다. 결과적으로 올바른 괄호끼리 붙어 있는 경우에 어떻게 처리해줘야 할지를 해결하지 못해서 실패했다. 이후 답을 보니 여는 괄호가 나올 때마다 temp에 해당하는 숫자를 곱해주고, 닫는 괄호가 나오면 다시 나눠주는 방식이었다. 분배법칙에 의해 a(x+y) = a*x + a*y 라서 a를 분배해주면 됐었다.

 

원 영역

- 원을 그릴 때마다 무조건 영역의 개수는 +1 되고, 해당 원 내부의 원들이 서로 접하면서 해당 원의 양쪽 끝에 내접할 때는 위 아래로 나눠지기 때문에 +2가 된다. 풀지 못해서 답을 보니 스택과 우선순위 큐를 사용했다. 그중 우선순위큐로 푸는 답이 더 깔끔해서 이걸 위주로 이해하려고 했다. 우선 원의 데이터를 정제해서 (원의 오른쪽 끝좌표, 지름)으로 만든 후, 끝좌표값 오름차순, 지름 오름차순해서 정렬한다.

이후 하나씩 순회하는데, 여기서 최소힙이 사용된다. 기본은 비어있고, 원을 순회하는 for문이 끝나면 해당 원을 넣는다. 이렇게 하면 i = 0일 땐 비어있고, 그 이후부터 힙에 원이 있게 되는데, 힙에 있는 원은 i번째 원보다 이전에 순회되었던 원이므로 i번째 원보다 오른쪽 끝 지점이 작다. 따라서 while heap 을 돌면서 계속 원을 꺼내며 해당 원이 i번째 원 내부에 있는지, 내부에 있으면 접하는지를 파악한다. 그리고 접한다면 다음에 힙에서 꺼내질 원은 이 내부의 원과 또 접해야 하기 때문에 접해질 좌표를 내부 원의 왼쪽 끝 좌표로 갱신해준다.

이런식으로 계속 내부 원끼리 접하다가 외부 원과도 접하게 되는 순간이 바로 우리가 찾던 +2를 해주는 순간이다. 

 

가운데를 말해요

- 예전에 본 문젠데 틀려서 답보고 이해했었는데 이번에 또 어떻게 푸는지 모르겠어서 답 봤다. 이 문제는 최소힙과 최대힙을 하나씩 사용해서 푸는 문제다. 중간값은 오름차순 정렬된 수열이 있으면 가운데에 있는 숫자다. 홀수인 경우 딱 1개가 있고, 짝수인 경우 가운데의 두 수 중 더 작은 것이 중간값이다. 답을 보면, 두 큐의 크기가 같을 땐 최대힙에 넣고, 최대힙이 더 클 땐 최소힙에 넣는다. 그후 최대힙에서 제일 큰 수가 최소힙에서 제일 작은 수보다 더 크면 둘을 스위칭한다. 이렇게 하고 나면 최대힙의 제일 큰 값이 중간값이 된다. 이 답을 이해하기 위해서 우선 교체하는 상황을 봤다. 최대힙과 최소힙의 크기는 같거나 최대힙이 1개 더 많은 상태라서 일단 최대힙의 제일 밑 부분을 1번이라고 하고 최대힙 맨 위에서 최소힙의 맨 위로 이어진다고 보면, 위치로만 따졌을 때 일단 최대힙의 TOP이 중간지점이다. 이제 값의 크기를 보면, 최대힙의 TOP <= 최소힙의 TOP 조건을 만족하면 최소힙의 TOP 밑부분부터는 최대힙의 TOP보다 더 큰 값이기 때문에 중간 위치의 값이 중간값이 된다. 어떻게 최소힙의 TOP 밑부분부터 최대힙의 TOP보다 더 큰 값임을 알 수 있을까? 그건 맨 처음에 값 1개를 넣을 때부터 항상 조건을 체크해가며 정렬을 해왔기 때문이다. 그래서 정렬이 틀어진 경우에 딱 한 번만 교체를 해주면 다시 정렬이 된다.

 

철로

- 단순하게 완전탐색하면 O(N^2) 풀이가 나오고 시간초과를 맞는다. 그래서 O(NlogN) 풀이가 필요하다. 내가 시도한 풀이는 (집, 회사)를 오름차순 정렬한 후, (st, en) 쌍들을 st를 기준으로 오름차순 정렬해서 순회해가면서 철로를 en과 나란히 두었다고 쳤을 때 st가 철로 내에 있는지 없는지를 기준으로 개수를 셌다. 테스트케이스는 맞췄지만 반례를 찾아보니 (5, 10), (6, 8) 같이 st는 더 작은데 en이 더 큰 경우에는 구할 수 없는 로직이었다. 답을 보니 우선 선분의 길이가 철로의 길이보다 같거나 짧은 (st, en) 쌍들만 취하여 en 을 기준으로 오름차순 정렬한 후, 순회하면서 내부에 while을 돌면서 heap을 pop 해주는데, 이 힙에는 i - 1번째까지의 (st, en)이 들어가 있고, pop되는 조건은 철로의 시작점보다 st가 더 작은 경우이다. 이렇게 조건이 맞지 않는 선분들을 다 pop 시켜주고 남은 것들은 철로 내에 있다는 것이므로, 힙의 크기 + i번째 철로까지 포함한 개수를 잠재 답으로 갱신해준다.

 

최소 스패닝 트리

- 이 문제는 유니온 파인드를 이용한 크루스칼 알고리즘이나 프림 알고리즘을 모르면 dfs로 풀게 되는데 나는 몰랐기 때문에 dfs로 시도했고 시간초과가 났다. 유니온 파인드는 노드들이 있으면 노드끼리 싸워서 이긴쪽이 진쪽의 부모가 되는 알고리즘이다. 이걸 크루스칼 알고리즘 구현시 사용하는 이유는 스패닝 트리가 만들어질 때 방문한 노드간에 영역이 같으면 버리고 다르면 영역을 하나로 합쳐야 하기 때문이다. 이 과정에서 간선이 가장 작은 것부터 확인하면서 가면 모든 노드를 방문하는 최소 스패닝 트리를 얻을 수 있다.

그리고 유니온 파인드를 최적화하는 기법도 있다. 파인드할 때 재귀적으로 가장 높은 조상까지 거슬러 가게 되는데, 이때 거쳐갔던 각 노드들의 부모를 다 가장 높은 조상으로 갱신해주는 것이다. 이렇게 하면 다음에 부모를 찾으려고 할 때 거슬러 가지 않고 한 번에 부모를 반환하게 된다. 그리고 유니온(합치기)할 때도 랭크라는 것을 도입해서, 랭크가 다르면 랭크가 작은 쪽의 부모를 랭크가 큰 쪽으로 하고, 랭크가 같으면 한쪽을 다른쪽의 부모로 한 후 부모쪽의 랭크를 높인다.

 

이분 그래프

- 처음 풀이 시도할 때 정답과 유사한 방향으로 갔지만, 큐에 시작노드를 넣고 방문체크를 하면서 A영역과 B영역으로 계속 분배한 후, A,B 를 또 순회하면서 서로간 연결된 노드들이 있나 없나를 확인하는 과정에서 시간초과가 발생했다. 답을 보니 방문체크를 할 필요 없이, 계속 노드를 순회하면서 현재 노드의 다음 노드가 어느 영역에 이미 들어가 있을 때, 현재 노드와 같은 영역에 있는지 없는지를 계속 검사해서 있으면 False를 리턴하고, 없으면 continue를 해서 큐에 집어넣지 않으면 됐었다.

 

동전 2

- 동전의 가치는 중복해서 나올 수 있다. 그래서 각각의 동전 가치를 하나의 노드로 보고 bfs를 돌려서 문제를 풀려고 했는데 시간초과가 났다. 중복해서 검사하는 부분을 없애주어야 했는데, 만약 같은 가치의 동전이 여러개 나올 경우, 가치 리스트를 오름차순 정렬해서 큐에 하나씩만 넣어서 돌리면 된다. 이유는, 만약에 1 1 1 2 3 이렇게 있으면 첫 번째 1에서 가지치기를 했을 때, 두 번째에서 가지치기를 했을 때와 중복되는 모양이 나오기 때문이다. 이렇게 처리하고 제출을 해봤는데도 시간초과가 났다. 그래서 질문리스트를 참고해서 예외처리 하나를 더 추가했다. 그건 바로 가치의 합이 나왔다는 유무를 체크하는 배열을 사용하는 것이다. 그리고 이후에 같은 가치합인 상태가 나오면 해당 상태를 큐에 넣지 않고 버린다. 이래도 되는 이유는, 이후에 나올 것들은 어차피 이전에 다 처리되기 때문이다. 오름차순 정렬된 수열이고, 해당 수열은 중복 가능한 조합이라서 가지 depth가 높아질 때 자신의 값부터 시작한다.

 

그래프 수정

- 이 문제는 위상정렬을 사용하는 문제다. 위상정렬 규격 코드는 줄 세우기 문제에서 배웠고, 이걸 사용해서 푸는 문제다. 처음에 문제에 접근할 때는, indegree가 0인 노드를 담는 큐를 최소힙으로 만든 후, 큐에서 하나씩 꺼내서 번호를 순서대로 지정했었다. 틀렸고 반례를 보면 사전순으로 더 빠른게 존재했다. 답에서는 indegree와 outdegree를 서로 바꿔서 위상정렬을 하고, 최소힙은 최대힙으로 만든다. 그리고 번호는 N부터 1씩 줄여가며 붙인다. 이렇게 하면 가장 늦게 정렬되는 노드들에 가장 큰 숫자번호가 부여되면서 우리가 원하는 사전순으로 가장 빠른 수열을 구할 수 있게 된다.

 

임계 경로

- 이 문제는 방향이 있는 그래프, 시작노드, 도착노드가 주어지고 시작노드의 indegree는 0, 도착노드의 outdegree도 0이다. 시작노드에서 도착노드로 가는 가장 비용이 긴 경로가 있을 텐데, 비용은 다 최대로 큰데 경로만 다른 것들이 존재할 때, 이 경로들 내의 간선을 중복은 세지 않고 개수를 세는 문제다. 처음에 문제를 풀 때는 비용은 다익스트라처럼 기존의 비용보다 현재 비용 + 간선 비용이 클 때 비용을 갱신하는 식으로 구했고, 경로는 비용에 따라 비용이 더 크면 새로운 경로로 갱신하고, 같으면 set을 사용해서 중복된 간선 제외하고 더하고 하는 식으로 도착노드까지 이렇게 구했다. 결과적으로 테스트케이스는 다 맞았지만 시간초과가 걸렸다. 답을 보니 대체로 비슷한데 경로를 구하는 부분에서 내가 한 것처럼 모든 간선을 다 추가하는게 아니라, 바로 직전에 어떤 노드를 거쳐야 최대 비용의 경로인지 딱 노드 한개만 이용했다. 그리고 기존의 경로와 새로운 경로의 비용이 같은 경우에는 append하는 방식으로 여러 경로가 있다는 것을 표현했다.

이후, 이걸 사용하는 방법은 도착지에서부터 시작해서 다시 거꾸로 시작점까지 가는 방법인데, 도착지에서 어떤 노드로 가야 최대 비용인지를 구해서 답에 간선을 추가하고 다시 또 이 노드는 어떤 노드로 가야 최대 비용인지를 구해서 추가하는 식으로 시작지점까지 이동한다.