Always Be Wise

▶ 문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net ##### 문제 ##### # N×M크기의 배열로 표현되는 미로가 있다. # 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. # 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 # (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. # 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. # 칸을 셀 때에는 시작 위..

▶ 문제 : https://www.acmicpc.net/problem/2606 ##### 문제 ##### # 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. # 한 컴퓨터가 웜 바이러스에 걸리면 # 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. # 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. # 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, # 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에는 컴퓨터의 수가 주어진다. # 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번부터 차례대로 번호가 매겨진다. # 둘째 줄에는 네트워크 상에서 직접 연결되어 ..

▶ 문제 : https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net ##### 문제 ##### # 방향 없는 그래프가 주어졌을 때, # 연결 요소(Connected Component)의 개수를 구하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) # 둘째 줄부터 M..

▶ 문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net ##### 문제 ##### # 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. # 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, # 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. ##### 입력 ##### # 첫째 줄에 정점의 ..

▶ 문제 : 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 ##### 문제 ##### # 그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오. # 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 # 그 가중치의 합이 최소인 트리를 말한다. ##### 입력 ##### # 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 ..

크루스칼 알고리즘(Kruskal Algorithm)이란 무방향의 가중치 그래프의 모든 정점을 최소 가중치로 연결하는 방법을 의미한다. 최소 스패닝 트리를 찾을 때 대표적으로 사용하는 알고리즘이다. 크루스칼 알고리즘은 무언가를 결정해야 할 때마다 그 순간에 가장 좋다고 생각하는 것을 선택하는 탐욕적인(Greedy) 방법을 따른다. 구체적인 동작 과정은 아래와 같다. 1) 모든 엣지들을 끊어 놓는다. 2) 엣지들을 가중치 순으로 오름차순 정렬한다. 3) 정렬된 엣지들을 순서대로 선택한다(가장 낮은 가중치를 먼저 선택). 4) 선택한 엣지가 사이클을 형성하지 않는지 확인한다. 5) 사이클을 형성하지 않는다면, 해당 엣지를 최소 스패닝 트리에 포함시킨다. 엣지들을 가중치 순으로 오름차순 정렬한다. B-C D-E..

▶ 문제 : https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net ##### 문제 ##### # 이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다. # 노드의 왼쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 작다. # 노드의 오른쪽 서브 트리에 있는 모든 노드의 키는 노드의 키보다 크다. # 왼쪽, 오른쪽 서브 트리도 이진 검색 트리이다. # 이진 검색 트리를 전위 순회한 결과가 주어졌을 때, # 이 트리를 후..

▶ 문제 : https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net ##### 문제 ##### # 이진 트리를 입력받아 # 전위 순회(preorder traversal), # 중위 순회(inorder traversal), # 후위 순회(postorder traversal) # 결과를 출력하는 프로그램을 작성하시오. ##### 입력 ##### # 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. # 둘째 줄부터 N개의..

그래프(Grpah)란 연결 관계를 저장할 수 있는 자료 구조를 의미한다. 그래프에서 하나의 데이터 단위를 나타내는 객체를 노드라고 한다. 위 그림에서 하나의 유저가 하나의 노드다. 두 노드의 직접적인 연결 관계를 엣지라고 한다. 위 그림에서 흰 선들이 그래프의 엣지에 해당한다. 두 노드 사이에 엣지가 있을 때 두 노드는 인접해 있다고 표현한다. 엣지가 갖는 특성에 따라 그래프의 종류를 세부적으로 구분할 수 있다. 우선, 엣지들이 방향을 가지고 있을 경우 방향 그래프라고 한다. 방향 그래프를 통해 인스타그램의 팔로우 관계처럼 한 유저가 다른 유저를 팔로우하는 일방적인 관계를 나타낼 수 있다. 엣지들의 연결 관계뿐만 아니라 어떤 정보를 나타내는 수치를 갖는 그래프를 가중치 그래프라고 한다. 예를 들어, 인천..

트리(Tree)는 데이터 사이의 계층 관계를 표현하는 비선형 자료구조를 의미한다. 트리는 노드(Node)와 가지(Edge)로 구성된다. 아래 그림에서 A, B, C 등이 노드에 해당하며 해당 노드들을 연결하는 선들이 가지다. 트리의 가장 위쪽에 있는 노드를 루트(Root), 가장 아래쪽에 있는 노드를 리프(Leaf)라고 한다. 리프는 단말 노드(Terminal Node), 외부 노드(External Node)라고도 하며, 물리적으로 가장 아래쪽에 위치한다는 의미가 아니라 해당 노드 아래로 가지가 더 이상 뻗어나갈 수 없다는 의미이다. 리프를 제외한 노드(루프 포함)를 비 단말 노드(Non-Terminal Node), 내부 노드(Internal Node)라고도 한다. 어떤 노드와 노드가 가지로 연결되어 있..