📌문제 출처 백준 단계별 문제풀이 : 유니온 파인드 https://www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 주어진 연결 정보들로 도시별 연결성을 나타내는 parents 리스트를 만들자. parents = (인덱스+1)번호의 도시와 연결된 도시 중 가장 작은 번호의 도시 parents를 완성 후 여행계획을 살피며 모두 같은 parents 값을 가지고 있는지 확인하자. 이때 find와 union 함수를 통해 parents 리..
📌문제 출처 백준 단계별 문제풀이 : 유니온 파인드 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net ❓ 문제 📗 풀이 코드 import sys sys.setrecursionlimit(10**6) input = open(0).readline def solution(): n,m = map(int,input().split()) parents = list(range(n+1)) # 같은 집합에 포함된 수중 최소값 d..
📌문제 출처 백준 단계별 문제풀이 : 트리 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 전위 순회 결과는 루트/왼쪽/오른쪽 이다. 그리고 왼쪽은 루트보다 작고 오른쪽은 루트보다 크다. 입력값이 50 30 24 5 28 45 98 52 60 일때 루트/왼쪽/오른쪽 : 50 / 30 24 5 28 45 / 98 52 60 이다. 이를 재귀함수를 통해 마지막 노드에 다다를때까지 루트/왼쪽/오른쪽의 구조를..
📌문제 출처 백준 단계별 문제풀이 : 트리 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 각 탐색 방법에 따라 방문하는 노드 순서를 출력해야한다. 각 방식 별로 루트, 왼쪽 자식, 오른쪽 자식의 순서를 일정하게 모든 노드에서 출력해야하므로 재귀함수를 활용해 탐색을 진행하자. 하나의 루트 노드만 입력하면 모든 방식의 탐색을 진행하도록 하나의 클래스를 만들자. 각 방식별 재귀함수 메소드와 모든 탐색 결과를..
📌문제 출처 백준 단계별 문제풀이 : 트리 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 임의 노드(1)에서 가장 멀리 떨어진 노드가 지름의 한 점이므로 그 노드로부터 가장 멀리 떨어진 노드까지의 거리를 구하자. 출발 노드로부터 가장 멀리 떨어진 노드와 그 거리를 반환하는 BFS함수를 만들자. ''' from collections import defaultdict, deque input = o..
📌문제 출처 백준 단계별 문제풀이 : 트리 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' tree={node:[자식노드]}로 만들어주고 bfs로 1번부터 자식노드로 내려가면서 각 자식노드에 대한 부모노드를 인덱스에 맞게 list로 반환 1) 변수 선언 n : 노드개수 tree = {node:[자식노드]} parents = [0]*(노드개수+1) 2) bfs stack = deque([1]) while stack : 노드를 하나씩 꺼내서 그 노드와 이어진 자식 노드를 하나씩 확..
📌문제 출처 백준 단계별 문제풀이 : 동적 계획법과 최단거리 역추적 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' dp = 해당 인덱스의 수가 마지막일때 가장 긴 증가하는 부분 수열의 길이, 최초는 1 수열의 수를 하나씩 뽑아서 그 수의 바로 직전까지 이중 for문을 반복하여 dp를 완성한다. 1) 변수 선언 n = 수열 A의 크기..
📌문제 출처 백준 단계별 문제풀이 : 동적 계획법과 최단거리 역추적 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net ❓ 문제 📗 풀이 코드 ''' 재귀함수를 통해 최단 연산횟수를 빠르게 찾아주고 찾은 연산횟수를 줄여가며 경우에 맞는 경유 숫자를 출력한다. ''' input = open(0).readline def solution(): n = int(input()) dp = {1:0,2:1} # 숫자별 최소 도달 연산횟수를 담아줄 딕셔너리 # i==2인 경우를 제외하면 -1로 이동하는 것이 최소인 경우는 없기에 1까지 도달할 때 /2,/3만 확인하면 ..
