2024.02.12. ~ 2024.02.18.

백준 19 문제.

 

1. BOJ 11502 : 세 개의 소수 문제 - S4

Number Theory(Primality Test) + Bruteforcing 문제.

1000 이하의 모든 소수를 찾는 건 그냥 O(N^2)로도 찾을 수 있다.

1000 이하의 소수는 대략 200 개 미만일 것이라 생각해서 세 수를 찾는 건 O(N^3)로 모든 조합을 찾아보았다.

앞에 소수 찾는 걸 Sieve로 좀 더 빠르게 찾을 수는 있는데... 귀찮아서 구현을 안 했다.

 

2. BOJ 11332 : 시간 초과 - S3

Implementation + Case-working 문제.

시간복잡도를 나타내는 문자열에 따라서 로직을 전부 다르게 구현해야 한다.

O(N^2), O(N^3), O(2^N), O(N!)은 오버플로우가 나타날 가능성도 존재하기도 하므로 적절히 커팅해주면 된다.

(나는 N^2은 40000 이상, N^3은 1001 이상, 2^N은 31 이상, N!은  13 이상이면 불가능하다고 커팅해주었다.)

 

3. BOJ 12919 : A 와 B 2 - G5

Bruteforcing + Backtracking 문제.

역으로 T에서 S로 바꾸는 게 가능한 지로 판단해보면 T 맨 앞과 맨 뒤의 철자를 가지고 분기점을 나눌 수 있다.

(앞 뒤가 B면 항상 B를 뒤에 추가 + 뒤집기를 한 것이고, 둘 다 A면 항상 A를 뒤에 추가한 작업을 한 것임. 앞이 B, 뒤가 A면 둘 다 가능성이 있고... 반대로 앞이 A, 뒤가 B면 더 이상 진행할 수 없음.)

이게 근데 시간복잡도 계산이 어떻게 되는지를 잘 모르겠어서 일단 질러본건데... 최악이 O(2^N)일 것 같은데 왜 되는건가 싶다.

 

4. BOJ 12904 : A 와 B - G5

Greedy + Implementation 문제.

역으로 T에서 S로 바꾸는게 가능한 지로 판단하는 문제이긴 한데, 맨 마지막 철자에 따라서 행동이 정해진다.

계속 마지막 철자를 지우되, 마지막이 B였으면 뒤집는 연산도 해주면 된다.

왜 BOJ 12919랑 같은 난이도로 책정되었는지 잘 모르겠어서 S1로 기여하긴 했다.

 

5. BOJ 1065 : 한수 - S4

Bruteforcing + Math + Implementation 문제.

N의 범위가 1000까지 이므로 그냥 1부터 N까지 전부 '한수'인지 아닌지를 확인하면 되는데,

어차피 '한수' 판별은 세 자리 수일때만 해도 되므로(99까지는 전부 '한수'이고 1000은 '한수'가 아니므로) 100 이상 1000 미만이면 백의 자리 수 - 십의 자리수 = 십의 자리수 - 일의 자리수 를 만족하는지를 확인하면 되었다.

S4 치고는 너무 쉬워서 S5로 기여하긴 했는데 B1이라고 해도 납득되었을 것 같다.

 

6. BOJ 19591 : 독특한 계산기 - G3

Deque + Parsing + Implementation 문제.

Deque를 활용해서 operator들과 operands를 관리하고, 조건에 따라서 이를 구현하면 된다.

내가 깡구현 문제들을 작정하고 푸는게 아니면 싫어하지만, 너무 어려운 구현 문제는 아니어서 괜찮게 풀었다.

 

7. BOJ 27725 : 지수를 더하자 - G4

Math + Number Theory 문제.

1 ~ K 모든 값에 대해서 각 소수별로 최대 몇 번씩 나눌 수 있는지를 보고 이를 모두 더하면 되는 문제였다.

 

8. BOJ 20930 : 우주 정거장 - P5

Sorting + Sweeping + DSU 문제.

두 선분을 X축과 Y축으로 투영을 했을 때에 둘 중 한 축에서 서로 겹친다면 두 선분끼리는 서로 갈 수 있다.

따라서, 모든 선분들을 X축 및 Y축으로 투영을 하고, X나 Y 좌표가 낮은 순서대로 정렬해서 Sweeping을 하면 O(NlogN)만에 어느 선분끼리 겹치는지를 확인할 수 있다.

겹치는 선분끼리는 DSU를 활용하여 같은 그룹으로 묶어둘 수 있고, 각 쿼리별로 같은 그룹에 있는지 확인해서 응답해줄 수 있다.

총 시간복잡도는 O(NlogN + Q*t(N)) // t(N)은 DSU cost 값, 매우매우 작은 값이라고 알고있음.

 

9 ~ 13. 제 3회 보라매컵 본선 Open Contest (Arena #20) - Solved : 5 / 8

나중에 후기로 올리긴 할텐데...

반성을 매우 많이 해야겠다는 생각이 들었던 대회였다.

어떻게 5 문제중에 첫트로 AC받은 문제가 없지;;;

 

14 ~ 16. SUAPC 2024 Winter Open Contest - Solved : 3 / 13

마지막 15분 정도 남았을 때부터 참가해서 그냥 스코어보드에서 제일 많이 풀린 세 문제만 풀었다.

이건 따로 후기 올릴 생각없으니 여기에 쓰겠음.

 

14. BOJ 31428 : 엘리스 트랙 매칭 - B4

Implementation 문제.

그냥 'A', 'C', 'S', 'I' 개수 다 세고, 마지막 줄에 주어진 철자의 개수를 출력하면 된다.

원래 브론즈는 리뷰 안 하지만 대회 문제니깐...

 

15. BOJ 31416 : 가상 검증 기술 - S5

Implementation + Simulation 문제.

일단, 도훈이만 B 작업을 할 수 있으므로 도훈이에게 전부 B 작업을 맡기고, 그 동안에 상혁이에게 A를 맡긴다.

이후에 둘 중에 먼저 빨리 끝난 사람에게 A 작업을 맡기면 된다.

그래서 구현은 B 작업이 남았으면 도훈이에게 할당, 작업이 없으면 일이 더 빨리 끝난 사람에게 A 할당 이런식으로 하면 된다.

 

15. BOJ 31423 : 신촌 통폐합 계획 - G5

나는 DSU로 풀었다.

먼저 다음 어느 문자열이 오는지를 저장하는 배열 next와 해당 문자열 뒤에 붙인다면 어느 문자열 뒤에 붙이는 지를 판단하는 배열 p를 선언하자. 초기화는 전부 next[i] = i, p[i] = i로 해주면 된다.

그러면, 문자열 a 뒤에 b를 붙이는 걸 DSU merge 함수를 활용해서 구현이 가능하다.

이후에, next에 없는 문자열이 제일 먼저 나오는 문자열이므로 해당 문자열부터 next 배열을 타면서 순서대로 출력하면 된다.

그런데 정해는 DFS 풀이나 연결 리스트로 구현하는 거라고 한다. (나도 연결 리스트까지 생각은 해보긴 했는데 시간이 부족했어서 구현까지 할 엄두가 안 났었다.)

 

이외에도 브론즈 4 문제를 풀었다.

 

이번 주 일지는 여기서 끝.