개요
조금씩 풀다보니 다이아5가 되었습니다!
풀다보니 골드가 없어져 있어서 플레티넘 4이상이 아니라면 제자리 걸음...
나름 1일 1알고를 하려 노력을 했습니다. 8월 중에는 SSAFY에서 SWEA에 집중한다고 백준을 잠깐 손놓긴 했었지만, 프로젝트 기간에 밤을 새더라도 문제는 풀자는 주의로 웬만하면 문제를 풀었습니다.
아무래도 집중해서 문제만 풀 수는 없는 입장인지라, 플레티넘에서 다이아까지는 굉장히 오랜시간이 걸렸던 것 같습니다.
흔히 PS계에서 티어 올리기 쉬운 세그먼트 트리 등 구간 쿼리 문제들도 많이 풀긴 했는데, 확실히 세그먼트 트리가 알면 티어에 비해서는 쉬운편이 맞는 것 같습니다. 그래도 금광은 어려웠...
개인적으로 재밌게 푼 알고리즘 분류들은
- Dynamic Programing
- Sparse Table
- Network Flow & MCMF
이 분류들이 재밌었습니다.
수학, 기하학을 풀면 사실 좀 더 빨리 찍었을 것 같기도 한데, 사실 기업 코딩 테스트에는 거의 안나오는 유형이기도 해서(라고 하기엔 코딩 테스트에 나오는 알고리즘은 넘어서 푼 것 같긴 하지만) 배제하고 있었습니다. 하지만 이제 DP도 CHT(Convex Hull Trick) 등 최적화를 요하는 문제가 슬슬 나와서 관련 문제도 슬슬 풀어야겠다고 생각은 듭니다.
무엇보다 다각형이 이쁘게 나오고 싶긴 합니다ㅎㅎ
그리고 문자열을 Trie, Rabin-Karp 몇 문제만 풀어봐서 많이 못풀었는데 문자열도 좀 풀어야 될 것 같네요
지금까지 기억나는 문제들
승급을 시켜준 마지막 문제 : 1396 - 크루스칼의 공(P1)
Sparse Table로 풀이하였습니다. 병렬 이분 탐색의 기본 문제로도 알려져있는 것으로 알고 있지만, 해당 알고리즘 대신 다른 방법으로 해결하였습니다. 개인적으로 되게 참신한 방식이라 생각됩니다.
티어가 가장 높은 문제 : 1626 - 두 번째로 작은 스패닝 트리(D4) / 풀이
Sparse Table로 풀이하였습니다. 처음에 한번 틀렸는데, 가장 큰 간선만 저장해서 교환하는 방식을 취했기 때문입니다. 반례를 찾아서 두 번째로 큰 간선도 추가로 저장을 해 주었습니다.
가장 많이 틀린 문제 : 10217 - KCM Travel(P4)
얼마나 틀렸냐고요? 사진 한장으로 대체합니다...ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
딱 봐도 Dijkstra 입니다. 다만 일반 다익스트라를 돌리면 안되고, 노드와 비용에 대해서 정보를 저장하는 Dynamic Programing 이 결합된 형태로 해결해야 됩니다. 하지만 이 문제는 이렇게 해서 TLE가 나기 때문에 우선순위 큐가 아닌 미리 간선들을 소요 시간에 대해서 정렬을 해놓고 큐로 풀어야 됩니다.
너무 힘들게 풀긴 했는데, 삼성 역량 테스트 Professional(B형)을 취득했을 당시에도 Dijkstra + DP 유형이 나와서 해당 문제로 먼저 얻어맞은 저는 역량 테스트 문제는 아주 쉽게 풀 수 있었습니다. 그래서 여러모로 또 가장 생각나는 문제이기도 합니다.
가장 오래 풀었던 문제 : 5372 - 큐빙(P5)
골드 시절 풀었던 문제인데, 푸는데 1주일이나 걸렸습니다. 특별한 건 없습니다. 회전하는 것을 일일이 구현하면 됩니다. 구현 능력이 정말 안좋았을 때라 오래 걸리긴 했는데, 지금 풀면 또 빠르게 풀지않을까 싶습니다. 그래도 빡구현 유형은 아직까지 가장 힘듭니다.
후기
다이아는 늦어도 올 중순까지는 찍고 싶긴 했는데 찍게 되어서 우선 기쁩니다.
사실 티어를 올리는 건 이제 크게 의미는 없긴 합니다. 대학생도 아니고, 소소한 일반인 대상 대회 정도는 생각 있지만 그런거 외에는 의미가 없기도 합니다.
개발을 하면서 느끼는 건, 알고리즘 역량이 정말 개발에 도움이 되냐 했을 때 느끼는 건 아직까진 반반인 것 같습니다.
물론 아직 실무에서 핵심 비즈니스 로직을 설계해본 경험은 없어서 이 부분은 모르겠지만, 이렇게 문제 풀면서 구현 능력이나 문제 상황에서 바로 코드부터 작성하는 대신 어떻게 접근을 해야되는지 설계하는 능력은 확실히 많이 늘어난 것 같습니다.
이제 그만 풀 것인가? 라고 하기에는 알고리즘 공부 자체가 많이 재밌어졌습니다. 그냥 게임 대신 한번 스트레스 풀겸 종종 풀 것 같습니다. 대신 백준은 조금 쉬엄쉬엄하고 코드포스도 좀 풀어야겠습니다.
