본문 바로가기
728x90

전체 글432

[python] 백준 14939 불 끄기 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 문제 해결 문제의 이해는 쉽지만 풀기 많이 어려웠던 문제 어디서부터 시작해야할지 많이 어렵다. 이 때 불 키고/끄고를 비트마스크를 이용해서 풀 수 있다고 하는데 어려워서 여러 코드를 확인하였다. 가장 중요한 것은 '첫 번째' 행의 불이 켜져있든 꺼져있든 스위치를 누루는 경우의 수를 모두 탐색하는 것이다. 이유는 첫 번째 행이 꺼져있어서 눌러 불을 켜도 다음 밑에 있는 스위치를 눌러서 다.. 2024. 3. 2.
[python] 백준 1647 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 해결 조금 고민하면 한 번 노드를 다 이은 후 가장 긴 길이를 빼면 되지 않을까? 싶은 생각을 할 수 있다. 하지만 이 때 가장 긴 길이가 짧아서 나눌 때 최소 길이가 되지 않을 수 있지 않나? 생각을 하게 되었다. 하지만 정렬(sort)를 이용하여 가장 유지비용이 짧은 두 노드부터 이어가며 모든 노드를 다 이은 다음 가장 나중에 이은 노드를 뺀다면 최소.. 2024. 3. 1.
[python] 백준 1509 팰린드롬 분할 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 해결 팰린드롬은 좌우 대칭인 문자열을 의미한다 문자를 하나씩 나누면 무조건 팰린드롬 분할이 된다. 두 개씩 보면서 팰린드롬을 확인하는 것도 어렵지 않다. $O(N)$ 3개 이상일 때는 어떻게 할 수 있을지 어려웠다. 길이를 3부터 L까지 늘려나가면서 $l$ 확인한다. 시작점을 0부터 $L-l$까지 이동하며 잡고 끝점을 시작점.. 2024. 2. 25.
[python] 백준 2887 행성 터널 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 해결 최소 거리를 측정해야하는데 각 축에서 가장 차이가 작은 값으로 거리를 정의한다. 축을 분리해서 정렬 후 (오름차순) 거리차를 계산하는 것은 짐작할 수 있다. 그 후 점을 연결시키는데 이미 연결 되어있으면 넘어가고 아니면 점을 연결하고 비용을 추가해준다. 연결 되어있고 아니고를 유니온-파인드(Union-find)를 통해 계산한다. 이와 같은 방법을 크루스칼.. 2024. 2. 24.
728x90