[BOJ] 2023 11월 5주차 정리

2023년 11월 27일 (월)  ~ 12월 3일 (일) - 푼 문제 (20 solved)

 

1969번 DNA (2024-01-02 기준 Silver IV)

 

문제 링크: https://www.acmicpc.net/problem/1969

 

행을 기준으로 가장 많이 나온 단어를 Counter와 정렬로 구해주고 문자열과 답을 구해주면 된다. 솔직히 코드 짜는 건 바로 됐는데 문제 자체가 잘 안 읽어졌다..

---

1813번 논리학 교수 (2024-01-02 기준 Bronze I)

문제 링크: https://www.acmicpc.net/problem/1813

 

N개의 Ni를 배열에 1씩 더해주고 뒤에서부터 찾아서 Ni == i가 같은 경우를 출력해주면 된다. 옛날에 레이튼 교수(아마 이상한 마을 아니면 악마의 상자?)에서 5명인 경우인 문제가 나왔던거 같은데... 그게 생각나서 바로 풀렸다.

---

16214번 N과 M (2024-01-02 기준 Diamond V)

문제 링크: https://www.acmicpc.net/problem/16214

 

오일러 피를 이용해서 구하는 웰?노운 문제. 정확히는 모르겠고 $N^{N} \;(mod \; M) $를 구할 때 $gcd(N, M) = 1$이면 페르마의 소정리로 더욱 간단하게 할 수 있는데 아닌 경우라면 사용할 수 없으니 $\phi (M)$을 구하고 $N^{\phi(M)}\equiv N^{2\phi(M)} (mod\;M)$은 N과 M이 서로소가 아닐 때도 성립해서 이 성질을 사용했다. 그리고 $\phi(...\phi(\phi(\phi(M)))...)$은 결국 1로 수렴되는데 그 뜻이 문제에서 말하는 일정한 나머지 값이 되는 것이다. 그리고 M이 2 이하가 되거나 N이 1이면(이땐 무조건 0 혹은 1이다) $ N\;(mod \; M) $ 을 리턴하는 재귀 함수를 작성했다. 증명이라 하면 적을 게 정말 많아지는데 나도 인터넷에 널려있는 정보를 모아서 푼거라 자세하게 잘 적으신 분들보다 잘 쓸 자신이 없네요;

---

26741번 Farma (2024-01-02 기준 Bronze I)

문제 링크: https://www.acmicpc.net/problem/26741

 

머리는 모두 1개고 다리는 닭이 2개고, 소는 4개이므로 식 2개가 만들어진다. 즉, 연립방정식을 이용하여 풀 수 있다.

---

13358번 Exponial (2024-01-02 기준 Platinum I)

문제 링크: https://www.acmicpc.net/problem/13358

 

위의 N과 M과 거의 똑같은 문제. 팩토리얼과 제곱을 합친 문제인데, N과 M 문제처럼 재귀적으로 풀면 된다. Exponial(N)의 식에 N이 1, 2, 3일때는 큰 수가 아니라서(지금보니 4도 262,144인데 그냥 3까지만 리턴했네요) 직접 구할 수 있다(각각 9, 2, 1). 그래서 그냥 리턴해줬고, M이 1이면 0을 리턴,  N이 1이면 1을 리턴하고 아닐 때는 오일러 피 함수를 이용해서 재귀적으로 값을 계산했다.

---

7255번 Sujungimas (2024-01-03 기준 Gold IV)

문제 링크: https://www.acmicpc.net/problem/7255

 

간단한 분리 집합 문제. 같은 집합 내에서 가장 작은 값을 저장해주고 집합들의 값들을 곱해주면 된다.

---

3063번 게시판 (2024-01-03 기준 Silver IV)

문제 링크: https://www.acmicpc.net/problem/3063

 

첨에 케웤 문제인 줄 알고 삽질 하다가 1 ≤ x1 < x2 ≤ 10,000, 1 ≤ y1 < y2 ≤ 10,000, 1 ≤ x3 < x4 ≤ 10,000, 1 ≤ y3 < y4 ≤ 10,000이어서 케이스가 생각보다 별로 없었다. 암튼 x2와 x4의 최솟값, x1과 x3의 최솟값을 구해서 뺐을 때 0보다 작거나 같으면 겹치지 않으므로 0으로 바꿔 어떤 수를 곱해도 0이 된다. y값도 마찬가지다. 이후 두 값들을 곱했을 때 0보다 큰 값이 나온다면 겹쳤다는 뜻이고, 전체 넓이에서 겹친 부분의 넓이만 빼면 된다.

---

22116번 창영이와 퇴근 (2024-01-03 기준 Gold IV)

문제 링크: https://www.acmicpc.net/problem/22116

 

BFS에 PQ를 곁들어 보세요 근데 파이썬 기준으로 생각보다 널널하진 않네요

---

11266번 단절점 (2024-01-03 기준 Platinum IV)

문제 링크: https://www.acmicpc.net/problem/11266

 

단절점 기본 문제. 루트고 자식의 개수가 2개 이상이면 무조건 단절점이고 루트가 아니라면 이전에 방문한 값보다 다음 값이 작거나 같다면 무조건 이전 노드를 가야 현재 노드로 갈 수 있다는 것을 의미하고, 이 점을 없애면 단절된다. 즉 단절점이다. 어쨌든 DFS를 이용해서 구해줬다. set을 이용해서 단절점 중복을 없앴다.

---

11400번 단절선 (2024-01-03 기준 Platinum IV)

문제 링크: https://www.acmicpc.net/problem/11400

 

단절선 기본 문제. 단절점보다는 조건이 덜 까다로운데 이전 방문 노드가 현재 방문 노드보다 크다는 조건이 단절선인데 이 조건을 DFS로 구현해서 단절선을 구했다. 단절점 코드에서 살짝만 수정해주면 끝

---

14675번 단절점과 단절선 (2024-01-03 기준 Silver IV)

문제 링크: https://www.acmicpc.net/problem/14675

 

단절점과 단절선의 성질을 이용해서 푸는 문제다. 이 문제는 트리에서 적용 하는거라 더욱 쉽다. 먼저 트리니깐 사이클이 없으니 자식 노드가 2개 이상이면 단절점이다. 그리고 트리는 최소의 간선(노드의 개수 - 1)을 연결했기 때문에 하나라도 끊기면 모든 노드를 갈 수 없으니 모든 선이 단절선이다. 문제에 단절점과 단절선의 정의를 알려주긴 하다만... 트리의 성질도 알아야 해서 실4보단 어려운 거 같다.

---

12813번 이진수 연산 (2024-01-03 기준 Bronze II)

문제 링크: https://www.acmicpc.net/problem/12813

 

간단한 이진수 연산이다. 내장 함수 써도 되는데 왜인지 모르겠지만 그냥 구현했다. 왜 그랬지?

---

2321번 Crowing (2024-01-03 기준 Bronze III)

문제 링크: https://www.acmicpc.net/problem/2321

 

Fortran 언어를 이용해서 까마귀를 출력하는 문제...인데 포트란을 써봐야 알지..

---

26529번 Bunnies (2024-01-03 기준 Bronze II)

문제 링크: https://www.acmicpc.net/problem/26529

 

세상에 N이 45 이하인 피보나치 문제를 O(lgN)으로 푸는 사람이 어딨어요

---

30821번 별자리가 될 수 있다면 (2024-01-03 기준 Bronze III)

문제 링크: https://www.acmicpc.net/problem/30821

 

정말 간단하게 nC5를 구하는 문제다. 파이썬 내장함수를 사용했다.

---

4763번 Tangled in Cables (2024-01-03 기준 Gold IV)

문제 링크: https://www.acmicpc.net/problem/4763

 

기본 MST 문제에 해시 섞어서 푸는 문제다.

---

6927번 Connect The Campus (2024-01-03 기준 Gold IV)

문제 링크: https://www.acmicpc.net/problem/6927

 

간선의 비용은 좌표들의 거리이므로 거리를 구하고 MST에 적용하면 된다. 적용할 때 연결된 노드들을 저장하면서 마지막에 총 비용과 노드들을 출력해주면 된다.

---

8549번 Autostrady (2024-01-03 기준 Gold IV)

문제 링크: https://www.acmicpc.net/problem/8549

 

MST에서 가장 큰 비용이 드는 간선을 출력하면 된다.

---

27009번 Out of Hay (2024-01-03 기준 Gold IV)

문제 링크: https://www.acmicpc.net/problem/27009

 

MST에서 가장 큰 비용이 드는 간선을 출력하면 된다.

왜 위랑 문제 풀이가 똑같냐고요? 똑같아서요

---

25777번 Word Tree (2024-01-03 기준 Gold IV)

문제 링크: https://www.acmicpc.net/problem/25777

 

문제에서 정의된 단어들의 거리를 정의해주고 MST를 구해주면 된다. 어떤 언어든 1초인데 PyPy3 기준 0.952초에 겨우 뚫었다. 재채점 될 일은 없겠지만 되면 C++로 짜야할듯