![]()
최소 신장 트리(MST, Minimum Spanning Tree)그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리다.MST를 사용하는 대표적인 알고리즘으로 크루스칼, 프림 알고리즘이 있다. MST 특징사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다.N개의 노드가 있으면 최소 신장 트리를 구헝하는 에지의 개수는 항상 N - 1개다. 아래의 예제는 크루스칼 알고리즘을 기준으로 한다.MST 핵심 이론1. 에지 리스트로 그래프를 구현하고 유니온 파인드 리스트 초기화하기MST는 데이터를 노드가 아닌 에지를 중심으로 저장하기 때문에 인접 리스트가 아닌 에지 리스트의 형태로 저장한다.유니온 파인드를 사용하는 이유는 사이클이 발생하면 안되기 때문에 사이클..
![]()
플로이드-워셜그래프에서 최단 거리를 구하는 알고리즘 중 하나로 다른 최단 거리를 구하는 알고리즘과 차이는 모든 노드 간에 최단 경로를 탐색한다는 것이다.음수 가중치 에지가 있어도 수행할 수 있지만 음수 사이클이 있으면 안 된다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.시간 복잡도는 O(V³) 으로 느린 편에 속하기 때문에 주어진 노드가 적을 경우에 사용한다. 플로이드-워셜의 핵심 이론A 노드에서 B 노그까지 최단 경로를 구했다고 가정했을 때 최단 경로 위에 K 노드가 존재한다면 그것을 이루는 부분 경로 역시 최단 경로라는 것이다. 결국 최단 경로는 각 노드간 최단 경로가 합쳐졌다는 것을 의미한다.플로이드-워셜 점화식: D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E..
![]()
벨만 포드(Bellman-Ford)그래프에서 최단 거리를 구하는 알고리즘 중 하나이다.특정 출발 노에서 다른 모든 노드까지의 최단 경로를 탐색한다.다익스트라와 비슷하지만 다른 점은 벨만 포드 알고리즘은 음수 가중치 에지가 있어도 수행할 수 있다는 점이다.따라서, 벨만 포드 알고리즘은 최단 경로를 구하는 문제 보다는 전체 그래프에서 음수 사이클의 존재 여부를 판단하는 문제로 출제된다.시간 복잡도는 O(VE) V: 노드 수, E: 에지 수벨만 포드 핵심 원리1. 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화하기벨만-포드 알고리즘은 에지를 중심으로 동작하므로 에지 리스트로 구현한다.최단 경로 리스트(정답 리스트)에서 출발 노드는 0, 나머지는 무한대로 초기화한다. (출발 노드는 무한대가 되면 안된다..
![]()
다익스트라(Dijkstar)그래프에서 최단 거리를 구하는 알고리즘 중 하나이다.시간 복잡도는 O(ElogV) E: 에지 수, V: 노드 수에지는 모두 양수로 이루어져 있어야 되며 출발 노드와 모든 노드 간의 최단 거리를 탐색한다. 다익스트라 알고리즘의 핵심 이론1. 인접 리스트로 그래프 구현하기인접 행렬보다 인접 리스트로 구현하여 탐색하는 시간을 줄여야 한다.2. 최단 거리 배열 초기화 하기최단 거리 배열을 초기화 하고 1은 가중치가 없기 때문에 0으로 초기화한다.컴퓨터는 무한대가 없기 때문에 큰 수로 지정해서 초기화 해준다. (예시는 편하게 무한대로 처리)3. 값이 가장 작은 노드 고르기가중치가 없어 0의 값을 가지는 1번 노드를 선택하여 해당 노드가 가리키는 다른 노드를 탐색하고 최단 거리를 구한다...
![]()
위상 정렬위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.시간 복잡도 - O(V + E) V: 노드 수, E: 에지 수위상 정렬은 노드 간의 순서를 결정해준다.※ 항상 유일한 값으로 정렬되지 않는다. 즉, 정답이 여러 개 일수도 있다.위상 정렬의 핵심 이론1. 인접 리스트를 만들고 진입 차수를 초기화해준다.2. 진입 차수가 0인 노드를 선택하고 선택된 노드를 정렬 배열에 저장한다.3. 노드가 가리키는 노드들의 진입 차수를 1씩 빼준다.※ 진입 차수(자기 자신을 가리키는 에지의 개수)
![]()
유니온 파인드(Union Find)유니온 파인드는 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.유니온 파인드는 노드가 어떤 경로에 있는지 보다 서로 연결되어 있는지를 확인하기 위한 알고리즘이다. (같은 집합인지 확인)대표 노드를 저장하는 배열을 초기화한다. 최초에는 인덱스 값을 그대로 저장 배열에 넣어준다. 처음에 각 노드들이 연결되어 있지 않고 서로 독립적으로 세팅되기 때문에 자기 자신이 대표 노드가 된다.유니온 연산을 통해서 하나의 집합 즉, 노드간 연결을 해준다. (대표 노드를 비교하여 더 작은 값을 대표 노드로 설정한다.)처음에 유니온 연산이 가능한 이유는 초기에는..
![]()
정렬(Sort)정렬 알고리즘이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.그럼 정렬은 왜 하는 걸까??내가 편의점에서 아르바이트할 때를 생각해 보면 음료 진열대 뒤쪽에서 음료들을 하나씩 넣어가면서 진열해야 된다. 여기서 중요한 것은 유통기한이 빠른 순서대로 넣는 것이다. 하지만 창고에 쌓인 음료들을 보면 유통기한이 빠른 순서대로 정렬되지 않은 경우를 많이 경험했다.창고에 있는 음료들의 유통기한을 빠른 순서대로 정렬하면 진열대에 음료를 넣을 경우 더 빠르게 작업을 할 수 있을 것이다.이러한 정렬 알고리즘에는 어떤 종류가 있는지 확인해 보면종류설명시간복잡도메모리안정성최고평균최악버블 정렬(Bubble Sort)데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는..
![]()
그래프(Graph)그래프는 자료구조 중 하나로 노드(Node, 정점)와 에지(Edge, 간선)로 구성된 집합으로 비선형 자료 구조이다.노드는 데이터를 표현하는 단위고 에지는 노드를 연결해 준다.언뜻 보면 그래프와 트리가 비슷하게 보일 수 있는데 차이점으로는 그래프는 사이클이 발생하지만, 트리는 사이클이 발생하지 않는다는 차이가 있다. 그래프의 종류그래프 자료구조는 다양한 형태를 가지고 있는데 그중에서 간단하게 3개만 살펴보자. 무방향 그래프무방향 그래프는 말 그대로 정점을 이어주는 간선에 방향성이 없는 그래프로 순서가 지정되지 않은 쌍이다.무방향 그래프에서 정점 Vi와 Vj를 연결하는 간선을 (Vi , Vj)로 표현하는데 방향이 없기 때문에 (Vi , Vj)와 (Vj , Vi)는 같은 간선이다. 방향 그..
![]()
DFS(깊이 우선 탐색)그래프 완전 탐색 기법 중 하나로 코딩 테스트에서 가장 많이 사용되는 알고리즘이다.DFS(너비 우선 탐색)의 원리그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.재귀 함수 or 스택 자료구조를 이용하여 구현한다. (후입 선출 특성을 가지고 있음)시간 복잡도는 O(V + E) - V: 노드 수, E: 에지 수한 번 방문한 노드는 다시 방문하면 안되며 따라서 노드 방문 여부를 체크할 배열이 필요하다.위의 그래프를 사진과 같이 인접 리스트로 표현할 수 있다.※ DFS를 구현할 경우 재귀 함수를 이용하기 때문에 스택 오버플로우에 유의해야 한다.DFS는 어떤 한 분기를 먼저 최대 깊이까지 ..
![]()
스택(Stack)스택(Stack)은 삽입과 삭제 연산이 후입선출(LIFO, Last In First Out)로 이루어진 선형 자료구조이다.가장 마지막에 삽입된 요소가 가장 먼저 삭제되는 구조로 삽입과 삭제가 한쪽에서만 일어난다.- 스택은 DFS(깊이 우선 탐색), 백트레킹 종류의 코딩 테스트에 사용된다. 요리를 배웠던 기억을 되살려 햄버거를 가지고 스택을 표현해보려고 한다.우리가 햄버거를 만든다고 상상해보자.햄버거 재료들을 차곡차곡 쌓아서 맛있게 만들었지만, 만약 중간에 들어갈 토마토를 까먹었다고 하면 어떻게 해야 될까?토마토가 위치해야 되는 자리까지 위에서부터 하나씩 뺄 것이다. 빵에서부터 치즈까지 빼고 난 후 토마토를 다시 쌓고 뺏던 재료들을 다시 쌓는다. 스택에서 사용되는 주요 메서드- top():..
![]()
배열(Array)- 배열은 메모리의 연속된 공간에 값이 채워져 있는 형태의 자료구조이다.- 배열은 인덱스를 통해 값을 바로 접근할 수 있다.- 배열의 단점으로는 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.- 위의 사진처럼 6이라는 값은 3과 4 사이에 삽입하려면 4와 5를 한 칸씩 뒤로 옮겨야 된다. 만약 배열의 길이가 1,000,000 정도 된다면 하나의 값을 삽입하기 위해서 많은 양의 데이터를 움직여야 하는 단점이 있다.- 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.- 구조가 간단하므로 코딩 테스트에서 제일 많이 사용된다. 리스트(List)리스트는 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 선형 자료구조이다.리스트는 배열과 ..
