2023.12.16.

[모두의 랜덤 디펜스] - 카카오 코딩테스트 (S3 ~ P5)

 

시험시간 : 300분, 실제 : 150~160분 정도 응시하다 시간이 너무 늦은 관계로 중도포기

Solved : 6 / 7

 

1. BOJ 17262 팬덤이 넘쳐흘러 - S4

실버 그리디 문제로, 모든 선분들이 적어도 한 지점에서는 겹치도록 선을 하나 그을 때 최소 길이를 묻는 문제.

선분이 끝나는 지점 중 제일 앞에 있는 것과 시작하는 지점 중 제일 뒤에 있는 것과 이으면 되며, 둘의 위치가 역방향이면 0을 출력.

 

2. BOJ 17390 이건 꼭 풀어야 해! - S3

정렬 후 구간 합을 미리 구하여 각 쿼리에 대해서 O(1)로 답을 도출해내는 문제.

구간 합을 아는지를 물어보는 문제인데, 아마 세그로도 풀리긴 할듯함. (물론 세그를 안다면 구간 합을 당연히 알겠지만)

 

3. BOJ 23352 방탈출 - G5

N의 범위가 매우 작으므로 그냥 0이 아닌 모든 지점에서 BFS 등으로 제일 먼 지점들의 거리를 구하고 제일 먼 지점들 중에서 제일 큰 값을 찾아 따로 저장하면 됨.

이후 그냥 모든 칸을 돌아가면서 답을 찾으면 됨.

BFS + 브루트포스는 의외로 많이 못 본 것 같긴해서 좀 신기했음.

 

4. BOJ 2539 모자이크 - G4

제일 밑의 칸에 종이가 붙어야 하고, 종이의 길이가 클 수록 필요한 종이의 최소 개수가 줄어듬을 활용하여 이분탐색으로 푸는 문제. (남으면 그냥 똑같은 자리에 여러번 붙여서 소비하면 됨.)

G4 ~ G3 구간의 이분탐색 문제들은 주로 이런 유형의 문제가 많았던 것 같음. 그래서 어렵지 않게 풀었음.

 

5. BOJ 12946 육각보드 - Unsolved.

일단 모든 칸을 색칠하려면 3가지만 있으면 항상 가능한데, 어떤 케이스에서 막히는 건지 색칠이 안 되는 경우가 있음.

아마 BFS를 짜서 각각마다 색깔을 주고 색칠을 직접 했어야 했나 싶음.

여기에 계속 몇트 박다가 시간이 없어서 다음 문제로 넘어감.

 

6. BOJ 9007 카누 선수 - G2

MITM 기본 문제.

O(N^4)로 찾는 것은 TLE가 나므로 Class 1,2 와 3,4 끼리의 모든 조합을 구하고 Class 1,2의 조합들이 각각 합이 K에 가깝게 되는 수를 Class 3,4의 조합들 중에서 무엇이 있는지를 이분탐색으로 구하는 문제.

O(N^2logN)으로 그러면 구할 수 있으므로 시간내로 충분히 돌릴 수 있음. MITM을 처음 접하는 사람에게는 입문용으로 좋아보임.

 

7. BOJ 14444 가장 긴 팰린드롬 부분 문자열 - P5

매내쳐 알고리즘을 몰라서, 그냥 해싱으로 풀었는데 시간 제한이랑 어찌저찌 아다리가 맞아서 풀린 문제.

구간 합 알고리즘을 활용해서 1...k 까지의 해쉬값을 다 구하고, 역(k..n까지의 해쉬값)으로도 한 번 구해줌.

여기까지는 O(|S|)였고 이후에 제일 긴 팰린드롬은 내부도 팰린드롬이므로 이분탐색을 활용해서 홀/짝인 팰린드롬에 대해서 최댓값을 구함.

이때 이분탐색은 O(logN), 각 길이 후보에 대해서 팰린드롬이 존재하는지의 여부는 페르마의 소정리를 활용해서 모듈로 역원도 구해야하므로 O(|S|logP)라서 O(|S|logPlogN)에 구할 수 있었음.

이렇게 구현하면서도 이게 될 까 싶었는데 2초에 딱 맞춰서 정답이 구해졌음.

나중에 이걸 동일한 문제에 다시 제출했는데 거기서는 TLE가 났음;;;

 

Softeer 찍먹 - 2문제

 

8. 성적 평균 - Lv.3

구간 합을 미리 구하고 각 쿼리별로 구간 합을 O(1)만에 구하기 + 구간의 길이 만큼 나누어 평균값을 출력하기.

딱 오늘 처음에 풀었던 BOJ 17390랑 같은 문제라서 백준으로는 S3쯤 되지 않을까 싶음.

 

9. 징검다리2 - Lv.4

문제에서 요구하는 바를 이해해보면 결국에는 계속 증가했다가 어느 지점부터 감소하는 최장 바이토닉 수열을 구하는 문제인데, N 제한 때문에 O(NlogN)으로 해결해야하는 문제.

기본적으로 문제 해결 패러다임은 BOJ 11054처럼 각 지점에서 해당 지점까지의 최장 증가 수열의 길이 + 해당 지점부터 끝까지의 최장 감소 수열의 길이를 구하면 되는데, 이를 O(NlogN) 풀이를 활용해야 하므로 백준에서는 G1 정도 하지 않을까 싶음.  (못해도 G2 아닐까?)

 

오늘 일지는 여기서 끝.