2024.02.26. ~ 2024.03.03.

백준 18문제.

 

1. BOJ 13511 : 트리와 쿼리 2 - P3

LCA, Sparse Table 문제.

일단 아무 노드를 루트로 두어 LCA Table + 루트로부터 해당 노드까지 가는데의 비용을 O(NlogN)으로 다 계산한다.

그리고 이제 각 쿼리에서의 u,v에 대한 LCA를 lca라고 한다면...

• 1번 쿼리는 루트에서의 u까지의 비용 + v까지의 비용 - 2 * lca까지의 비용 이렇게 계산하면 된다.
• 2번 쿼리는 만약에 k가 u에서 lca까지의 거리보다 크다면 역으로 v에서부터 lca까지 가는 도중에 (u에서 v까지 거치는 노드 개수) - k 번째 노드를 아니면 u에서 lca까지의 k번째 노드를 LCA Table로 O(logN)에 구하면 된다.

총 시간복잡도는 O((N+Q)logN).

하필 이 문제 제출하자마자 백준 서버가 터졌어서 한 번 제출할때마다 결과를 보기까지 15분 정도 걸렸었다. (그 와중에 3 WA를 적립했어서 AC까지 1시간 걸렸음;;;)

 

2. BOJ 17479 : 정식당 - S3

Implementation + Hash set 문제. 

여러 구현 방법이 있을 것 같은데, 나는 그냥 hash map으로 메뉴 이름 주면 {종류, 가격} 이렇게 담았다.

그러고 모든 메뉴를 받아서 이를 {종류, 가격}으로 바꾸고 정렬해서 일반 메뉴들 계산하고 다음에 특별 메뉴들 계산, 마지막에 서비스 계산하도록 했다.

 

3. BOJ 11724 : 연결 요소의 개수 - S2

나는 DSU로 풀었다.

양방향 간선으로 이루어져 있다면 어느 노드부터 시작해도 연결된 노드들은 다 갈 수 있으니 DFS나 BFS로도 풀 수 있다.

그게 정해였는데, 나는 귀찮아서 DSU로 풀었다. 그리고 개인적으론 DSU 풀이를 익히는게 나중에 Kruskal Algorithm(MST찾는 알고리즘)처럼 DSU를 활용하는 그래프 알고리즘 및 문제 유형들을 이해하는 데도 좀 더 도움이 된다고 생각한다.

 

[제3회 초콜릿컵] - Solved : 5 / 14 (시작 시간에 점심 먹을 것 같아서 아레나 등록은 안 했다.)

4. BOJ 31458 : !!초콜릿 중독 주의!! - B2

Implementation 문제. 

일단 팩토리얼 먼저 계산한다 그랬는데, 팩토리얼은 0! = 1, 1! =1 이므로 팩토리얼이 뒤에 하나라도 붙는지만 보면 된다.

logical not은 개수가지고 짝수면 그대로, 아니면 값을 바꿔주면 된다.

 

5. BOJ 31460 : 초콜릿과 11과 팰린드롬 - S4

Math + Constructive 문제.

N이 짝수면 그냥 1로 도배해도 괜찮다. (길이가 2k라면, 11이 k번 도배하는걸로 생각하면 되니깐.)

그런데 N이 홀수면 케이스를 좀 더 고려해야 한다.

• N == 1 : 11 * 0 = 0 이므로 0을 출력한다.
• N%4 == 3 : ...1x1... 이러한 형태인데, 앞뒤의 1이 홀수 개수이다. 2를 넣는다면, ...1 121 1... 이런식으로 11의 배수를 만들 수 있다.
• 나머지, 그냥 ...101... 이렇게 구성하면 된다. (0 앞뒤의 1의 개수가 짝수이므로 11로 다 묶인다.)

6. BOJ 31459 : 초콜릿과 ㄱ나이트 게임 (Sweet) - S2

Greedy 문제.

나이트가 하나라도 공격을 하지 못하는 곳에 최대한 배치하는게 최선이라 생각을 했고,

나이트의 공격범위가 우측 하단이므로, 우측 하단부터 순서대로 채우는 게 최선일 거라는 판단을 하였다.

솔직히 Proof by AC인 느낌이라 매우 짜치는 것 같아서 나중에 에디토리얼을 봐야겠다.

 

7. BOJ 31462 : 삼각 초콜릿 포장 (Sweet) - S2

Implementation+Greedy 문제.

맨 위부터 맞게 되었는지 순차적으로 확인하면 된다.

그래서 R를 처음에 찾았으면 우측 하단과 좌측 하단이 R인지 확인, B를 찾았으면 우측과 우측 하단이 B인지 확인하면 된다.

확인을 했으면 다른 값으로 바꿔서 중복으로 확인하지 않도록 구현했다.

 

8. BOJ 31464 : 초콜릿 괴도 코코 (Sweet) - G2

Implementation + Bruteforcing + BFS 문제.

관찰을 했을 때, 하나로 이어져 있지만 어느 점이든 단절점이 될 수 있는 형태의 그래프는 트리라는 결론을 내렸다.

그래서 모든 가능한 점에 대해서 먼저 없애고, 이후에 남은 연결요소의 개수가 1개이면서, 트리 형태인지를 확인하였다. 

트리 형태를 확인하는 것은 어느 점이든 루트로 두었을 때 사이클만 생기지 않으면 되므로 BFS 시간복잡도인 O(N^2)만에 가능했다. 

그래서 총 시간복잡도는 O(N^4)인데, 구현량이 매우 많았어서... Implementation 문제라고도 생각된다.

 

9. BOJ 17087 : 숨바꼭질 6 - S2

Number Theory 문제.

생각해보면 +-D로 갈 수 있는 위치들은 전부 S + kD라는 형태로 표현이 가능하다.

그렇다면, Ai = S+kD이므로 S-Ai는 D의 배수라는 의미이다.

이말은 즉슨, |S-A1|, |S-A2|....의 공약수만 D가 될 수 있는데, D가 최대일려면 이 중에서 최대공약수를 찾으면 된다.

__gcd 함수를 사용해서 쉽게 풀었다.

 

10. BOJ 27907 : The primes contain arbitrarily long arithmetic progressions - S5

Ad hoc + Constructive + Math 문제.

지문 논문 관련 이야기는 그냥 '이러이러한 일이 있었다~' 수준이었고 결국에 구해야하는 건 특정 길이 n의 소수로만 이루어진 등차수열이었다. 그런데 문제에서 수를 중복해서 넣으면 안 된다는 말이 없었다.

따라서, 공차가 0도 가능하므로 특정 소수를 n번 출력하면 되었다.

 

11. BOJ 31499 : 프랙탈 수열 - S3

Ad hoc + Combinatorics + Math 문제.

A의 정의를 보았을 때 모두 서로 다른 양의 값이라서 B의 원소들도 양수일 것인데, C에 0이 들어가 있으면 B = C가 불가능 하다.

따라서 B = C를 만족할려면 B의 모든 원소들은 1 ~ N 사이의 값을 가지고 있어야 한다.

그런데, A는 서로 다른 N개의 양의 정수들로 구성되어 있다고 한다.

따라서, A는 1~N까지 모든 정수가 들어있는 순열이 되어야 한다.

그렇다면 A가 어떤 순서로 배치되어 있든 B는 항상 정렬된 결과 = {1,2,3,....,N}이 되며, B_i = i 이므로 B_{B_i} = B_i = C_i를 만족하니 A가 프랙탈 수열인 경우의 수는 N!이 된다.

 

 

이외에도 Bronze 7 문제를 풀었다.

 

Programmers 2 문제.

 

1. [2024 KAKAO WINTER INTERNSHIP] 가장 많이 받은 선물 - Lv.1

Implementation + Simulation 문제.

각 이름을 index로 mapping하여 2D matrix를 만든다. (a[i][j] -> i번째 사람이 j번째 사람에게 선물을 준 횟수)

이러면서 gifts 배열을 전부 돌면서 a[i][j] 및 각 사람의 선물 지수도 따로 계산한다.

이후에 모든 사람들에 대한 짝에 대해서 누가 누구에게 선물을 주는지 계산해보면 된다.

 

2. [2024 KAKAO WINTER INTERNSHIP] 가장 많이 받은 선물 - Lv.1

관찰 + BFS/DFS 문제.

관찰을 해보면, 새로 생긴 노드는 in-degree가 0이고, out-degree가 2 이상인 노드가 된다.

그런데, 8자나 도넛 모양에 속하는 노드는 in-degree가 0인 노드가 있을 수 없고, 막대 모양은 out-degree가 1 아니면 0이다.

따라서, 새로 생긴 노드는 그냥 in-degree가 0인 노드들 중에서 out-degree가 2 이상인 노드를 찾으면 된다.

찾은 다음에 해당 노드와 이어진 노드들에서 시작해 BFS를 돌리면 된다.

탐색할 때 간선들과 노드들의 개수를 기록하면, 8자 / 도넛 / 막대 모양인지도 쉽게 파악이 된다.

다만, 막대 모양은 해당 모양에 속한 노드들을 전부 탐색할 수 없는 경우도 있긴 한데, 그래도 막대의 일부도 막대 모양을 지니므로 막대인지 아닌지는 판단할 수 있다. (사실 사이클이 없는 모양은 막대 밖에 없다!)

관찰이 꽤 재밌었던 문제였다. 코테 문제들에도 이런 관찰을 요구하는 문제가 있어서 놀랐다. (너무 구현 위주라고만 생각했나보다.)

 

이번 주 일지는 여기서 끝.