[알고리즘] 2025 카카오 하반기 코딩테스트 문제 풀어보기

문제 링크

2025년 하반기 카카오 공채에 사용된 1, 2차 알고리즘 코딩테스트 문제가 프로그래머스에 올라와서 풀어보았다. 최근 알고리즘을 많이 놓기도 했지만 지금까지 경험해본 코테중에 가장 어려운 난이도에 속한 것 같다...

 

1차 중요한 단어를 스포방지

카카오 코테의 전통일수도 있지만 1번문제는 쉬운 구현문제이다. 스포방지 구간에 포함되는 단어들을 set, map 등으로 관리한 뒤 스포방지가 해제될 때마다 해당 단어들이 얼마나 존재하는지를 더하면 쉽게 풀 수 있다.

 

1차 노란불 신호등

lcm, gcd 같은 느낌이 들지만 제한이 충분히 작아 500만정도까지 돌려봐도 무난하게 통과할 수 있다.

 

1차 리프 노드 수 최대화

트리의 모양이 위에서부터 깊이에 따라 2, 2, 2, 2, ... , 3, 3, 3 또는 3, 3, 3, 3, ..., 2, 2, 2 꼴이 될 줄 알고 열심히 구현했으나 구현실수를 했는지 WA 를 받았다. 트리 배치를 랜덤하게 구성해서 2, 3, 3, 2, ... 같은 모양도 나오게 해서 500 번정도 돌려보니 통과했다. 아직도 정해는 뭔지 모르겠고 실전이었으면 틀렸을 문제

 

1차 바이러스 파이프

코테 단골 소재인 완전탐색 문제이다. $k \le 10$ 이므로 처음부터 A 가 열렸을때, B 가 열렸을때, C 가 열렸을때 모든 경우에 대해 각각 탐색하면 $3^k$ 의 경우의 수가 나온다. 각 경우마다 $O(n)$ 에 bfs 하면 $O(n 3^k)$ 에 넉넉히 풀 수 있다.

 

1차 카카오 앱 정리하기

정말 풀기 싫게 생긴 빡구현문제다. 실전이었으면 시간관리를 위해 다른 문제로 달렸을 것 같다. 시간 길게 잡고 고민했는데도 칸 넘어가는 경우 해결하기 어려웠다. 단순 구현보다는 자료구조를 사용해서 해결하는 문제인 것 같다.

 

1차 발전소 회로 복구

이 문제 재미있었다. 각 패널이 모두 연결된 인접 행렬로 그래프를 그려서 가중치를 거리로 둔다. 패널의 개수가 최대 15개이므로 bit-dp 를 사용할 수 있다. 예를 들어 상태가 1000 (3번 패널이 활성화됨)일 때 1001 로 갈 수 있는지 확인한다. 즉, 0번 패널을 활성화 시키는데 1번, 2번 패널이 이미 활성화 되어있지 않아도 되는지 확인한다. 가능하다면 1000 의 상태값 + 3번 -> 0번 이동 비용을 추가한다. 

상태 전이는 1000 -> 1001 도 가능하고 0001 -> 1001 도 가능하므로 각각 조건에 위배되지 않는지 확인하고 이동 후 더 작은 값으로 설정한다. 모든 경우에 대해 위 과정을 진행하고 모든 패널이 활성화된 상태(1111)의 값을 반환한다. 모든 패널을 안전하게 활성화 가능한 경우만 주어지므로 (사이클이 존재하지 않으므로) 위상정렬을 통해 가능성을 판별하지 않아도 된다.

 

코테에서 bit-dp 가 나와서 신기했다. 다른 방법도 있으려나?

 

1차 최고 속도

interested_point 를 정의하자. 이 점은 교점, 과속카메라가 있는 점, 도시가 있는 점을 포함한다. 그 후 점들끼리 도로로 이동할 수 있으면 연결해서 그래프를 만든다. 가중치는 과속카메라가 있다면 해당 과속카메라의 속도, 없다면 무한으로 둔다. 그렇게 하면 문제는 A 부터 B 까지 가는 경로에서 최소 가중치의 최댓값을 구하는 문제가 된다. 이는 웰노운이므로 그래프 구성만 잘 하면 쉽게 해결할 수 있다.

 

2차 힌트 스테이지

이 문제도 $O(2^n)$ 완전탐색 문제이다. 각 step 에서 힌트를 쓴다/안쓴다로 모든 경우를 나누어 계산하면 쉽게 답을 구할 수 있다.

 

2차 보물 찾기

신기한 인터랙티브 문제이다. 나는 못풀었지만 행렬곱셈순서 dp 를 잘 사용하면 풀 수 있을 것 같다.

 

2차 선인장 숨기기

정해는 정말 아름다울 것 같지만 다차원 세그먼트 트리를 알면 딸깍으로 풀 수 있다. 정해는 모른다.

 

2차 제곱 개수 배열

뭔가 코포틱한 run length encoding 문제이다. K 를 구하는 것은 제곱수의 누적합을 이분탐색하여 쉽게 할 수 있다. C 를 못구해서 못풀었다 ㅠㅠㅠ 슬라이딩 윈도우를 하면 되려나..?

 

2차 기차 선로

선로를 하나 딱 두면 상하좌우에 올 수 있는 선로랑 올 수 없는 선로가 결정된다. 이를 통해 완전탐색을 하면 탐색공간이 충분히 줄어들 것 같은데 손대지는 못했다. 만약 이게 맞다면 나머지는 빡구현 문제가 된다. 나중에 각잡고 풀어봐야겠다.

 

 

 

 

이번 공채 코딩테스트는 너무 어렵고 실수할 부분이 많아 실제로 응시했다면 떨어졌을 것 같다. ㅠㅠㅠ AI 때문인지 실력 상향평준화 때문인지 코테가 날이 갈수록 어려워지는 것 같다.