알고리즘공부 (4) 썸네일형 리스트형 [알고리즘] 서로소 집합 - Disjoint Sets 서로소 집합 서로소 집합은 공통 원소가 없는 두 집합을 의미한다. 예를 들어 {1, 2}와 {3, 4}의 집합이 있다면 두 집합은 서로 서로소 관계이다. 만약 여기에 {2, 3} 의 관계를 나타낸다면 모두 서로소 관계가 아닌 것을 확인할 수 있다. 서로소 개념은 그래프 알고리즘에서 중요하게 사용되는 경우가 있어서 잘 알아두어야 한다. 그래서 서로소 집합 자료구조 (union-find 자료구조)는 서로소 부분 집합들로 나누어진 원소들을 처리하기 위한 자료구조라고 할 수 있다. 이는 union과 find 두 개의 연산자를 사용한다. union은 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산을 담당하고 find 연산은 특정한 원소가 속한 집합을 찾는 연산을 담당한다. 서로소 집합 알고리즘 기본적으로.. [문제풀이] 백준 1932번 정수 삼각형 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제풀이 n = int(input()) t = [] for i in range(n): t.append(list(map(int, input().split()))) k = 2 for i in range(1, n): for j in range(k): if j == 0: t[i][j] = t[i][j] + t[i-1][j] elif i == j: t[i][j] = t[i][j] + t[i-1][j-1] else: t[i][j] = max(t[i-1][j-1], t[i - 1][j]) + t[i][j] k += 1 print(max(t[n-1.. [알고리즘] BFS (Breadth First Search) 너비우선탐색 그래프를 전체 탐색하는 방법 중 너비우선탐색은 DFS와 다르게 루트노드에 인접한 노드들 부터 먼저 탐색하고 그 다음으로 가까운 노드를 탐색하는 구조이다. 즉 정점에 가까운 노드들을 먼저 순회하고, 먼 노드는 나중에 순회하게 된다. 이러한 특징으로 인해서 일반적으로 두 노드 사이의 최단 경로를 찾고 싶을때 사용한다. 구현으로써는 큐를 이용한다. 장점 트리의 깊이가 얕은 경우에 매우 빠르게 동작할 수 있는 알고리즘이다. 더불어 단순하게 생각하면 깊이우선탐색보다 너비우선탐색이 더 빠르다. 또한 루트노드와 가까운 노드부터 탐색하기 때문에 최단경로를 보장할 수 있다. 단점 너비우선탐색은 깊이우선탐색보다 많은 메모리를 필요로 한다. 왜냐하면 다음에 탐색할 정점들을 알고있어야 하기 때문이다. 또한 노드의.. [알고리즘] DFS (Depth First Search) DFS (Depth First Search) 그래프를 전체 탐색하는 깊이 우선 탐색 DFS는 탐색을 시작한 시작점부터 해당 부분을 완벽하게 탐색하고 다음으로 넘어가는 방식이다. 아래 그림을 보면 좀더 빠르게 이해할 수 있다. 위 그림처럼 한개의 분기에 대해 모든 탐색이 완료되면 다음 분기로 넘어가고, 완벽하게 탐색한 후에 다음 분기로 넘어가는 흐름을 띄고 있다. 이는 스택, 재귀호출 방식으로 구현할 수 있다. 일반적으로 재귀호출을 사용하였을때 구현하기 편해 자주 사용하지만, 스택오버플로우가 발생할 수 있기 때문에 잘 구현해야 한다 (노드 방문시 방문여부를 검사하면서 진행해야 무한반복에 빠지지 않을 수 있다). 장점 한 분기의 깊이가 깊더라도 완벽하게 탐색하고 다음 분기로 넘어가기 때문에 목표노드가 깊은 .. 이전 1 다음
