작년까지 연습삼아 친 카카오 코딩테스트를 올해는 취준생 입장으로 응시하게 되었다.
지금까지 재미로 풀어왔던 알고리즘 문제를 내 취업을 위해 푼다고 생각하니 기분이 오묘했다.
포지션은 백엔드와 인프라가 있길래 백엔드로 지원했다.
문제의 자세한 설명을 남기면 안될 것 같아 풀이만 간략하게 작성하려고 한다.
모든 문제를 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문제 푼 기억이 나는데 실력이 크게 향상된게 느껴지고 기업 코딩테스트는 부담이 많이 줄었다.
면접에 약하니 면접준비나 열심히 해야겠다.
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] ICPC 2022 인터넷 예선 후기 (2) | 2022.10.20 |
---|---|
[알고리즘] 메타 해커컵 2022 후기 (0) | 2022.10.01 |
[알고리즘] 슈타이너 내접타원 / 마든 정리 (0) | 2022.08.06 |
[알고리즘] Codeforces Round #811 (Div. 3) (0) | 2022.08.02 |
[알고리즘] UCPC 2022 본선 후기 (2) | 2022.07.26 |