크루스칼 알고리즘(Kruskal MST) 탐욕적인(Greedy) 방법을 이용하여 그래프의 모든 정점을 최소비용으로 연결하는 최적 해답을 구하는 것 동작과정 1. 간선데이터를 비용에따라 오름차순으로 정렬 2. 간선을 하나씩 확인하며 현재의 간선이 싸이클을 발생 시키는지 확인 2-1.사이클이 발생하지 않은 경우 최소 신장 트리에 포함 2-2.사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음 3. 모든 간선에 대하여 2번을 반복 시간복잡도 간선의 갯수가 E개일때 : O(ElogE) 시간이 가장 오래걸리는 부분이 간선을 정렬하는 작업 정렬의 시간복잡도 = O(ElogE)

신장트리(Spanning Tree) 그래프 내의 모든 정점을 포함하는 트리 그래프에 사이클이 형성이 되면 안됨 - 그래프의 최소 연결부분 그래프 - 최소연결 = 간선 수가 제일 적다 - n개의 정점을 가지는 그래프에서 n-1 개의 간선으로 연결되어 있는 형태 - 일부 간선을 선택해서 만든 트리 최소 신장트리(Minimum Spanning Tree) 신장트리 중에서 사용된 간선들의 가중치 합이 최소인 트리 - 각 간선의 가중치가 동일하지 않을 때 가장 적은 간선을 사용한다고 해서 최소비용이 얻어지지 않음 - MST는 간선에 가중치를 고려하여 최소 비용의 신장트리를 선택하는 것을 의미 - 간선의 가중치의 합이 최소(n개의 정점엔 n-1개의 간선) - 사이클이 형성 되면 안됨

깊이 우선 탐색(Depth- First Search) 특정 노드에서 시작해 다음 분기(branch)로 넘어 가기 전에 해당 분기를 완벽하게 탐색하는 방법 - 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘 - 자기 자신을 호출하는 순환 알고리즘 또는 스택의 형태를 지님 - 마지막에 들어온것이 먼저나가는 방식. LIFO(Last In First Out) - 알고리즘을 구현할때 노드의 방문여부 확인 필요 장점 - 현 경로상의 노드만 기억하면 되므로 저장공간의 수요가 비교적 적음 - 목표노드가 깊은 단계에 있을 경우 해를 빨리 구할 수 있음 단점 - 해가 없는 경로에 깊이 빠질 가능성 존재 - 얻어진 해가 최단경로가 된다는 보장이 없음 동작과정 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2-1..

2019 KAKAO BLIND RECRUITMENT (2019 카카오 블라인드 채용 문제) 채팅방에 들어오고 나간 기록들을 출력하는 문제입니다. 사용자는 Enter, Leave, Change 3가지를 할 수 있습니다. Enter는 "ABC님이 들어왔습니다." 를 출력합니다. 다른 닉네임으로 같은 방에 들어올 경우 채팅방 내의 해당 id의 닉네임이 전부 변경됩니다. Leave는 "ABC님이 나갔습니다." 를 출력합니다. Change는 ABC라는 닉네임을 변경할 수 있습니다. 이때 변경된 내용은 채팅방 전체에 변경됩니다. 1. 입력된 값들을 차례대로 확인 2. Enter나 Change의 경우 해당 id의 닉네임을 변경해주는 작업을 해줍니다. 3. 변경 된 닉네임으로 Enter과 Leave의 명령어에 맞게 해..

위상 정렬이란 순서가 정해져있는 작업을 차례로 수행해야 할 때 그 순서를 결정해주기 위해 사용하는 알고리즘 사이클이 발생하는 경우 위상 정렬을 수행할 수 없음 큐와 스택을 통해 구현 가능 위상 정렬 과정 1. 진입차수가 0인 정점을 큐에 삽입 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거 3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입 4. 큐가 빌 때까지 2번 ~ 3번 과정을 반복 4-1. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재 4-2. 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과 시간 복잡도 O(V + E)

플로이드 와샬 알고리즘 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘 각 경로에서 새로운 중간 노드로 사용할 수 있는 노드를 선택하고, 더 짧은 길이를 선택하여 줄이는 과정을 반복 시간 복잡도 (최선 = 최악 = 평균) O(V^3) 점화식 distance[i,j] = min(distance[i,j], distance[i,k] + distance[k,j]) 코드 for(int k = 0; k < 4; k++) // k 는 거쳐가는 정점 for(int i = 0; i < 4; i++) // i 는 행 (출발 정점) for(int j = 0; j < 4; j++) // j 는 열 (도착 정점) if (a[i][k] + a[k][j] < a[i][j]) a[i][j] = a[i][k] a[k][j];

다익스트라 알고리즘이란 음의 가중치가 없는 그래프의 한 정점에서 모든 정점까지의 최단거리를 각각 구하는 알고리즘 다익스트라 알고리즘 과정 1. 출발점으로부터의 최단거리를 저장할 배열 d[v] 생성. 출발 노드에는 0을, 출발점을 제외한 다른 노드들에는 매우 큰 값 INF를 채움 2. 현재 노드를 나타내는 변수 A에 출발 노드의 번호를 저장 3. A로부터 갈 수 있는 임의의 노드 B에 대해, d[A] + P[A][B]와 d[B]의 값을 비교 4. 만약 d[A] + P[A][B]의 값이 더 작다면, d[B]의 값을 이 값으로 갱신 5. A의 모든 이웃 노드 B에 대해 이 작업을 수행 6. A의 상태를 "방문 완료"로 바꾼다. 더 이상 A는 사용하지 않음 7. "미방문" 상태인 모든 노드들 중, 출발점으로부터..

그래프란 정점과 간선으로 이루어진 자료구조 그래프 용어 정점(vertex) : 노드(node)라고도 하며 데이터가 저장 됨 간선(edge): 링크(arcs)라고도 하며 노드간의 관계를 의미 인접 정점(adjacent vertex) : 간선에 의해 연결된 정점 단순 경로(simple-path): 같은 간선을 자나가지 않는 경로 차수(degree): 무방향 그래프에서 하나의 정점에 인접한 정점의 수 진출 차수(out-degree) : 방향그래프에서 사용되는 용어로 한 노드에서 외부로 향하는 간선의 수 진입차수(in-degree) : 방향그래프에서 사용되는 용어로 외부 노드에서 들어오는 간선의 수 그래프 구현 방법 -인접 행렬 -인접 리스트 인접 행렬 그래프의 노드를 2차원 배열로 만든 형식 인접 정점인 경우..