[알고리즘] 2023 KAKAO BLIND RECRUITMENT 1차 코딩테스트

작년까지 연습삼아 친 카카오 코딩테스트를 올해는 취준생 입장으로 응시하게 되었다.

지금까지 재미로 풀어왔던 알고리즘 문제를 내 취업을 위해 푼다고 생각하니 기분이 오묘했다.

포지션은 백엔드와 인프라가 있길래 백엔드로 지원했다.

 

문제의 자세한 설명을 남기면 안될 것 같아 풀이만 간략하게 작성하려고 한다.

모든 문제를 python으로 풀었다.

티어와 태그는 솔브드 기준 주관적으로 작성하였다.

 

1번 [Solved!]

티어 : B1

태그 : 구현, 사칙연산

날짜에서 종류에 맞게 달을 더한 뒤 현재 날짜와 비교하면 되는 단순 구현 문제이다.

python에 datetime이라는 편리한 라이브러리가 있다.

 

2번 [Solved!]

티어 : S4

태그 : 그리디, 투포인터

어차피 모든 집을 돌아야 한다면 가장 먼 집부터 방문하는게 이득이다.

가장 멀리 있는 배열의 값이 0이 아닌 인덱스를 각각 $a, b$라고 하면 방문마다 답에 $2\max(a,b)$를 더해주면 된다.(왔다갔다 2배)

방문할 때마다 최대한 많은 양을 처리한다.

코드포스 B에 나올 것 같은 문제

 

3번 [Solved!]

티어 : S2

태그 : 백트래킹

할인 경우의수가 4이고 이모티콘이 7개라는 것은 백트래킹 사용을 유혹한다.

실제로 백트래킹하면 답을 구할 수 있고 조건에 따라 답을 구하면 된다.

작년 카카오 양궁문제와 비슷하다.

실수연산 주의!!

 

4번 [Solved!]

티어 : G5

태그 : 분할정복

각 수를 이진수로 바꾸고 현재 길이보다 길면서 가장 가까운 $2^n-1$모양이 되도록 앞에 $0$을 추가해준다.

예를들면 $8 = 1000_{(2)}$이고 $0001000_{(2)}$로 바꾼다.

이러면 언제나 중심이 생긴다.

중심을 확인하고 중심을 기준으로 왼쪽, 오른쪽 부분을 재귀적으로 처리한다.

처리할때 다음 조건을 지켜야한다.

- 중심에 $0$이 나왔다면 그 이후 재귀적으로 처리할 때 $1$이 나오면 안된다.

위 규칙을 만족하면 1 아니면 0이다.

 

5번 [Solved!]

티어 : G4

태그 : 구현

문자열을 저장하는 배열이랑 셀 그룹을 저장하는 배열 두개를 선언했다.

- update : 그냥 구현하면 된다.

- print : 그냥 출력하면 된다.

- merge : 병합하려는 셀 그룹 두 부분을 $u, v$를 구한 다음 모든 배열을 돌면서 해당하는 셀을 새로운 수를 이용하여 그룹으로 만들어준다.

- unmerge : 해제하려는 셀 그룹 $u$를 구한 다음 모든 배열을 돌면서 해당하는 셀 그룹이 나오면 중복되지 않는 적당한 새로운 수로 대체한다.

 

6번 [Solved!]

티어 : G2

태그 : 그리디, 구성적

답은 길이가 $k$인 문자열임은 고정이다.

만약 $k$랑 시작점부터 도착점까지 거리의 홀짝이 다르면 "impossible"이다.

$k$와 현재위치부터 도착위치까지의 거리 $d$가 다른 동안에 아래 연산을 반복한다. (한번이라도 $k = d$이면 바로 중단)

1. 밑으로 내려갈 수 있는 동안 밑으로 한칸 내려가고 $k$를 1 뺀다.

2. 밑으로 못 갈 때 왼쪽으로 갈 수 있다면 왼쪽으로 한칸 이동하고 $k$를 1 뺀다.

3. 맨 왼쪽아래에 도착하면 오른쪽으로 한칸 이동하고 $k$를 1 뺀다.

4. 2, 3 반복

$k = d$이면 도착점까지 이동하면 된다. (d -> l -> r -> u 순서대로)

코드포스 C에 나올 것 같은 문제

 

7번

티어 : P4

태그 : ???

6번까지 풀고 시간 보니 3시간 남아있어서 한시간정도 연구하다가 그냥 포기했다.

일단 길은 계속 바뀌는데 주기가 있다.

예를들어 도달하는 순서가 $7 8 9 7 8 7 8 9 7 8 \cdots$ 이라면 가장 짧은 주기인 $7 8 9 7 8$을 선택할 수 있으면 된다.

이는 Z알고리즘으로 구할 수 있다.

여기에서 적당히 dp를 사용하면 될 것 같았지만 실패했다.

 

---

글솜씨가 없어서 제대로 전달이 됐는지 모르겠다.

평소에 백준, 코드포스, 각종 대회를 참여한게 큰 도움이 된 것 같다. (5시간 뒤에 또 해커컵있네..)

작년에 한 3문제 푼 기억이 나는데 실력이 크게 향상된게 느껴지고 기업 코딩테스트는 부담이 많이 줄었다.

면접에 약하니 면접준비나 열심히 해야겠다.