본문 바로가기

백준107

[백준] 1197번 최소 스패닝 트리 (프림, 크루스칼) 사용 언어 - Python3, PyPy3 문제 - 1197번 최소 스패닝 트리 Minimum Spanning Tree 최소한으로 뻗어나가는 트리 - 프림 = 다익스트라 이용해서 MST 구하는 문제 - 크루스칼 = 유니온파인드 이용해서 MST 구하는 문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 정답 최소 스패닝 트리 알고리즘 트리의 기본 조건 : 사이클 발생 X 방법1. 프림 다익스트라를 이.. 2023. 11. 8.
[백준] 1717번 집합의 표현 (유니온 파인드 문제) 사용 언어 - Python3, PyPy3 문제 - 1717번 집합의 표현 유니온 파인드 union & find 두 노드, 두 숫자, 두 무언가가 같은 집합 안에 있나요? https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 정답 유니온 파인드 x==0 인 경우, 두 집합 합치기 _union(a,b) - 부모 리스트 생성 par = [i for i in range(n+1)] 부모는 자기자신으로 시작 - 관계 생성 .. 2023. 11. 6.
[백준] 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.
[백준] 10815번 숫자 카드 사용 언어 - Python3 문제 - 10815번 숫자 카드 이분탐색 : 업다운 게임. 절반부터 시작해서 효과적으로 범위를 줄인다. https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 정답 이분탐색 - 절반부터 값과 같은지, 큰지, 작은지 확인 후 포인터 수정 s = 0, e = n-1, mid = (s+e)//2 1. 정렬 시키기 이분탐색은 기준 숫자카드가 정렬되어 있어야 중간값보다 크고/작다 대소비교가 가능하다. .. 2023. 11. 3.
[백준] 16472번 고냥이 (투포인터 문제) 사용 언어 - Python3 문제 - 16472번 고냥이 투포인터 : 가능성을 지워주는 방법 https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 정답 (투포인터) 양쪽 끝에서 비교하면서 만나면 종료 알파벳 종류가 n넘지 않는지 확인 + 최대 개수 확인 arr.rstrip() 불필요한 공백 제거 s = 시작포인터 = 0 e = 끝포인터 = 0 letters = [] 알파벳 종류 넣을 리스트 letters.append(arr[s]) 첫번째 값을 일단 넣고 시작.. 2023. 11. 3.
[백준] 22988번 재활용 캠페인 (투포인터 문제) 사용 언어 - Python3 문제 - 22988번 재활용 캠페인 투포인터 : 가능성을 지워주는 방법 https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 정답 (투포인터) 양쪽 끝에서 비교하면서 만나면 종료 두 병의 용량 반납 -> (A+B+X/2) 용량이 담긴 새로운 용기 s = 시작포인터 = 0 e = 끝포인터 = n-1 cnt = 채워진 용기 개수 rem.. 2023. 11. 3.

티스토리툴바