본문 바로가기

Algorithm/DFS&BFS&백트래킹&재귀52

[백준] 11725번 트리의 부모 찾기 (트리 문제) 사용 언어 - Python3, PyPy3 문제 - 11725번 트리의 부모 찾기 트리 = Tree = 나무 = Root + Seed 족보(가족관계도) = 조상 + 자손 https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 정답 트리의 조건 1. 모든 노드들은 연결되어 있어야 한다. (1개도 트리 가능) 2. 사이클이 발생하면 안된다. (내 아들이 할아버지이다? 불가능) 트리의 종류 1. 조상이 정해진 트리 = 루티드 트리 2. 조상이 정해지지 않은 트리 = 트리 1. 양방향 누가 부모이고 누가 자식인지 모르기 때.. 2023. 11. 4.
[백준] 1991번 트리 순회 (트리 문제) 사용 언어 - Python3 문제 - 1991번 트리 순회 트리 = Tree = 나무 = Root + Seed 족보(가족관계도) = 조상 + 자손 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 정답 트리의 조건 1. 모든 노드들은 연결되어 있어야 한다. (1개도 트리 가능) 2. 사이클이 발생하면 안된다. (내 아들이 할아버지이다? 불가능) 트리의 종류 1. 조상이 정해진 트리 = 루티드 트리 2. 조상이 정해지지 않은 트리 = 트.. 2023. 11. 4.
[백준] 1753번 최단경로 (다익스트라 문제) 사용 언어 - Python3, PyPy3 문제 - 1753번 최단경로 다익스트라 : BFS + 우선순위 큐 활용 (그래프에서 노드의 가중치에 따라 탐색해야 한다면, BFS만으로는 한계가 있다.) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 정답 다익스트라의 3가지 중요 포인트 1. 각각의 노드에 값(가중치)을 업데이트 2. 여러 경로가 있다면 min 최솟값을 사용 3. 방문 순서 = 시작점으로부터 거리를.. 2023. 11. 4.
[백준] 2589번 보물섬 사용 언어 - Python3, Pypy3 문제 - 2589번 보물섬 DFS (Depth-Frist search, 깊이 우선 탐색) = 경우의 수를 탐색하는 방법. 백트래킹 이용 BFS (Breadth-Frist search, 넓이 우선 탐색) = 노드와 노드의 관계를 탐색하는 방법. 그래프 탐색에 더 좋다. https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net 정답 BFS 알고리즘을 활용해 그래프 탐색하기 BFS (deque()) = 샛길로 새지 않는다.. 2023. 11. 3.
[백준] 2606번 바이러스 사용 언어 - Python3 문제 - 2606번 바이러스 DFS (Depth-Frist search, 깊이 우선 탐색) = 경우의 수를 탐색하는 방법. 백트래킹 이용 BFS (Breadth-Frist search, 넓이 우선 탐색) = 노드와 노드의 관계를 탐색하는 방법. 그래프 탐색에 더 좋다. https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍 www.acmicpc.net 정답 DFS / BFS 알고리즘을 활용해 그래프 탐색하기 0. 그래프 형태로 입력받기 각 노드에서 연결된 .. 2023. 11. 3.
[백준] 9251번 LCS (LIS 문제) 사용 언어 - Python3 문제 - 9251번 LCS LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 정답 해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기 dp[i] = max(dp[i], dp[j]+1) 완전탐색 방법).. 2023. 11. 1.
[백준] 2565번 전깃줄 (LIS 문제) 사용 언어 - Python3 문제 - 2565번 전깃줄 LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 정답 전체 n개에서 LIS 빼주기 dp[i] = max(dp[i], dp[j]+1) 전봇대에 겹친다 = A 전봇대 값이 작은 값 중에서, B전봇대 값이 더 크다. 안겹친다 = .. 2023. 11. 1.
[백준] 11053번 가장 긴 증가하는 부분 수열 (LIS문제) 사용 언어 - Python3 문제 - 11053번 가장 긴 증가하는 부분 수열 LIS/LCS 문제 : 가장 긴 증가하는 부분 수열 LIS (Longest Incresing Subsequence) LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 정답 해당 위치 기준 나보다 작은 숫자가 있으면 추가해주기 dp[i.. 2023. 11. 1.
[백준] 1520번 내리막 길 사용 언어 - Python3 문제 - 1520번 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 정답 2차원 그래프의 DP # 모든 점을 방문 # 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다 # 재귀로 구현한 뒤 DP로 바꾼다. 현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex ey = y + dy, ex = x + ex 조건1) ex,ey가 m*n 그래프 안에 있어야함 조건2) .. 2023. 11. 1.
[백준] 19947번 욕심쟁이 판다 사용 언어 - Python3 문제 - 19947번 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 정답 2차원 그래프의 DP # 모든 점을 방문 # 방문한 뒤 이동할 수 있는 모든 경우의 수를 재귀로 구현한다 # 재귀로 구현한 뒤 DP로 바꾼다. 현재 위치 graph[y][x] / 상하좌우 이동 dy,dx / 이동위치 ey, ex ey = y + dy, ex = x + ex 조건1) n*n 그래프 안에 있어야함 0 조건.. 2023. 11. 1.

티스토리툴바