코딩하는 해맑은 거북이

해당 글은 백준 1043번 문제 '거짓말'을 다룬다. 문제 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 설명 해당 문제는 집합으로 교집합과 합집합을 통해 쉽게 해결할 수 있다. 주의할 점은 진실을 아는 사람들의 집합이 업데이트 되면, 이전의 파티에 왔던 사람들도 다시 검사를 해줘야한다. 즉, 2중 for문으로 전체를 다시 검사하여 최종 진실을 아는 사람들의 집합을 만들어줘야한다. 코드 n, m = map(int, input().split()) true..

해당 글은 백준 1922번 문제 '네트워크 연결'을 다룬다. 문제 https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 설명 해당 문제는 최소 신장트리를 구하는 MST 문제이다. 아래의 코드를 크루스칼 알고리즘을 사용하여 작성하였다. * graph에 간선을 저장할 때, 비용을 앞에 적어서 바로 정렬할 수 있도록 하였다. 코드 n = int(input()) m = int(input()) parent = [0]*(n+1) for i in range(n+1): parent[i] = i graph = [] for _ in range(m): a, ..

해당 글은 백준 1238번 '파티' 문제를 다룬다.문제https://www.acmicpc.net/problem/1238 1238번: 파티첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어www.acmicpc.net 설명해당 문제는 최단 경로를 구하는 알고리즘 중 다익스트라를 활용하면 된다. x까지 가는 최단 경로와 x에서 집으로 돌아오는 최단 경로를 2번의 다익스트라로 구할 수 있다. 코드import heapq import sys input = sys.stdin.readline INF = int(1e9) n, m, x = map..

해당 글은 백준 1141번 문제 '접두사'을 다룬다. 문제 https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 설명 해당 문제는 문자열을 다루는 문제로, 입력받은 단어들을 길이순으로 정렬하여 비교하였다. 접두사가 아닌 부분집합의 최대크기를 구하므로, 2중 for문으로 현재 단어가 다음 단어의 접두사라면 결과에 포함시키지 않으면 된다. 코드 n = int(input()) words = [] ..

해당 글은 백준 1240번 문제 '노드사이의 거리'을 다룬다. 문제 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 첫째 줄에 노드의 개수 $N$과 거리를 알고 싶은 노드 쌍의 개수 $M$이 입력되고 다음 $N-1$개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍 www.acmicpc.net 설명 해당 문제는 그래프로 모든 노드에 대한 거리값을 저장해두고, 두 노드 사이의 거리를 구할 때 BFS 를 사용하여 해결할 수 있다. 코드 from collections import deque import sys input = sys.stdin.readline n, m = map(int, input().spl..

해당 글은 백준 2589번 문제 '보물섬'을 다룬다.문제https://www.acmicpc.net/problem/2589 2589번: 보물섬보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서www.acmicpc.net 설명해당 문제는 L의 위치 각각에서 BFS로 탐색한 후, 가장 먼 지점을 반환해주면 된다. 여기서 모든 L의 위치에서 BFS를 하면, 시간초과가 발생하였고 시간을 줄이기 위해 현재 'L'의 위치에서 상하로 L이 존재하거나, 좌우로 L이 존재하면 보물이 있는 위치가 아니므로 해당 경우에는 BFS를 하지않으면 해결할 수 있다. 코드import copy ..