✅ PS/BAEKJOON

[백준 13335번] 트럭 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/13335 13335번: 트럭 입력 데이터는 표준입력을 사용한다. 입력은 두 줄로 이루어진다. 입력의 첫 번째 줄에는 세 개의 정수 n (1 ≤ n ≤ 1,000) , w (1 ≤ w ≤ 100) and L (10 ≤ L ≤ 1,000)이 주어지는데, n은 다리를 건너는 트 www.acmicpc.net 🔐 풀이 트럭들이 다리를 지나감에 따라 시간대별로 다리 위의 트럭 무게를 누적해 문제를 해결했습니다. 문제의 첫 번째 예시를 이용해서 설명하자면, 우선 아래와 같이 시간대별 다리 위 트럭 무게를 0으로 초기화해줍니다. 이 때 0초는 -1로 설정하는데, 이는 나중에 모든 트럭이 다리를 건너는 시점을 무게 0을 통해 찾기 위함입니다. 트럭이 ..

[백준 2503번] 숫자 야구 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 🔐 풀이 문제에서 영수가 생각하고 있을 수 있는 정답은 1~9로 이루어진 세 자리 수이기 때문에, 우선 1~9로 이루어진 세 자리 수를 순열을 통해 모두 구해줍니다. 그리고 숫자를 한 번 물어볼 때마다 위에서 구한 숫자 리스트 중 스트라이크, 볼 개수가 맞지 않는 수를 리스트에서 제거해 나가면 마지막에 리스트에 남아있는 숫자들이 결국 영수가 생각하고 있을 수 있는 정답 숫자 리스트가 됩..

[백준 1167번] 트리의 지름 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 🔐 풀이 이 문제는 트리의 지름을 구하는 방법을 알고 있으면 쉽게 풀 수 있습니다. 트리의 지름을 구하는 방법은 아래와 같습니다. 트리의 임의의 노드(A)에서 가장 먼 노드(B)를 찾는다. 찾은 가장 먼 노드(B)에서 다시 가장 먼 노드(C)를 찾는다. 찾은 두 노드(B, C) 사이의 거리가 트리의 지름이 된다. 위 방법의 증명은 다른 블로그에서도 다룬 글이 많이 있으니..

[백준 15900번] 나무 탈출 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/15900 15900번: 나무 탈출 평소에 사이가 좋지 않던 성원이와 형석이가 드디어 제대로 한 판 붙으려고 한다. 성원이와 형석이 둘과 모두 똑같이 친한 인섭이가 대결 종목을 정해 가져왔다. 바로 '나무 탈출' 이라는 보드게 www.acmicpc.net 🔐 풀이 문제에서 모든 게임말은 리프 노드에 존재하고, 각 차례에 게임말을 부모 노드로 옮겨야하는데 더 이상 옮길 말이 없으면 게임이 끝납니다. 이때 먼저 게임을 시작한 "성원"이가 게임을 이기기 위해서는 말을 움직일 수 있는 총 횟수가 홀수여야 합니다. 말을 움직일 수 있는 총 횟수는 각 리프노드까지의 depth를 모두 더한 것과 같기 때문에 이를 구해 홀수인지 확인하면 성원이가 게임..

[백준 1240번] 노드사이의 거리 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net 🔐 풀이 BFS를 사용해 해결할 수 있습니다. graph에는 연결되어 있는 노드와의 거리, 연결되어 있는 노드 번호를 튜플로 저장해두었습니다. 거리를 구해야 하는 두 노드를 first, second라 했을 때, first에서 BFS로 그래프를 탐색하며 second까지의 거리를 구하면 됩니다. 🧑🏻‍💻 코드 import sys from collections import deque N, M = map(int, sys.stdin.read..

[백준 5052번] 전화번호 목록 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 🔐 풀이 다른 비슷한 문제에서 접두어를 찾을 때 문자열 배열을 문자 길이 순으로 정렬하고 이를 이중 for문으로 확인했었는데, 이 문제를 똑같은 방법으로 풀면 시간 초과가 발생합니다. 이를 해결하기 위해서는 문자열 배열을 정렬했을 때의 특성을 파악해야 합니다. 아래와 같이 sort 함수에 인자 없이 문자열 배열을 정렬하면, 첫번째 문자를 기준으로 정렬하고 같으면 ..

[백준 5639번] 이진 검색 트리 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 🔐 풀이 트리를 전위 순회한 결과를 입력으로 주는데, 전위 순회는 루트-왼쪽-오른쪽 순으로 탐색하기 때문에 루트 출력 -> 왼쪽 서브트리 모두 출력 -> 오른쪽 서브트리 모두 출력 형태가 됩니다. 문제에서는 후위 순회한 결과를 출력해야하기 때문에 아래처럼 재귀를 통해 왼쪽 서브트리를 먼저 끝까지 탐색하고 오른쪽 서브트리를 끝까지 탐색하고 루트를 출력해주면 됩니다. 🧑🏻‍💻 ..

[백준 1141번] 접두사 - 파이썬

⚠️ 문제 https://www.acmicpc.net/problem/1141 1141번: 접두사 접두사X 집합이란 집합의 어떤 한 단어가, 다른 단어의 접두어가 되지 않는 집합이다. 예를 들어, {hello}, {hello, goodbye, giant, hi}, 비어있는 집합은 모두 접두사X 집합이다. 하지만, {hello, hell}, {giant, www.acmicpc.net 🔐 풀이 문제에서 접두사X 집합이란 집합의 어떤 한 단어가 다른 단어의 접두어가 되지 않는 집합입니다. 접두사X 집합인 부분집합의 최대 크기는 곧 전체 집합에서 다른 단어의 접두어가 되는 단어만 제외한 집합이 됩니다. 또, A 단어가 B 단어의 접두어가 되기 위해서는 A 단어의 길이가 B 단어의 길이보다 짧거나 같아야 합니다. ..