쥬코딩

최소의 총 가중치를 갖는 spanning tree를 찾는 방법 중 prim's algorithim과 kruskal's algrithm에 대해 알아보겠다. spanning tree에 대한 글은 아래 참고 2022.07.01 - [자료구조] - [자료구조] spanning tree (sub graph) [자료구조] spanning tree (sub graph) spanning tree: 그래프에서 cycle이 제거된 sub graph -Depth First Traversal을 이용해 spanning tree 만들기 먼저 DFS방식으로 그래프를 순회한다. 위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결.. jicoding.tistory.com - Prim's algorithm 1. undirected..

자료구조 2022. 7. 4. 13:30

#define _CRT_SECURE_NO_WARNINGS #include int heap[100001]; int t = 0; int n; void swap(int i, int j) { int tmp = heap[i]; heap[i] = heap[j]; heap[j] = tmp; } //값 저장 void push(int x) { heap[++t] = x; for (int i = t; i > 1; i /= 2) { if (heap[i] < heap[i / 2]) swap(i, i / 2); else break; } } //내림차순으로 값 출력 int pop() { int top = heap[1]; heap[1] = heap[t]; heap[t--] = 0; int i = 1; while (i * 2 heap..

자료구조 2022. 7. 4. 09:23

이 문제는 dfs방식을 이용해서 풀었다. #define _CRT_SECURE_NO_WARNINGS #include char graph[25][25]; int house[625] = { 0, }; int sorted[625]; int dfs(int i, int j, int n, int cnt) { //한번 집이 있는 것(1)을 확인했다면 0으로 바꾸어주기 graph[i][j] = 0; //하나의 단지에 있는 집의 개수 세기 house[cnt]++; //좌우 위아래로 집이 있으면 같은 단지이기 때문에 재귀로 dfs호출 if (i - 1 >= 0 && graph[i - 1][j] == '1') dfs(i - 1, j, n, cnt); if (i + 1 < n && graph[i + 1][j] == '1') d..

알고리즘 2022. 7. 2. 12:55

spanning tree: 그래프에서 cycle이 제거된 sub graph -Depth First Traversal을 이용해 spanning tree 만들기 먼저 DFS방식으로 그래프를 순회한다. 위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결시키면 spanning tree가 만들어진다. -Breadth First Traversal을 이용해 spanning tree 만들기 먼저 BFS방식으로 그래프를 순회한다. 위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결시키면 spanning tree가 만들어진다.

자료구조 2022. 7. 1. 12:29

그래프는 node와 edge로 이루어진다. edge에는 undirected edge, directed edge, weighted edge 가 있다. undirected edge (and unweighted) directed edge (and weighted) weighted edge -용어 subgraph: 그래프의 한 부분(그래프의 특성을 가지고 있는) connected graph: 모든 노드가 다른 모든 노드로 접근이 가능한 그래프 disconnected graph: 최소 하나의 노드가 다른 모든 노드로 접근이 불가능한 그래프 adjacent node: 두 노드 사이에 edge로 곧바로 연결된 것 complete graph: 모든 노드가 다른 모든 노드로부터 인접한 것(edge로 곧바로 연결된 것) ..

자료구조 2022. 6. 28. 10:24

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다. 이를 충돌(collision)이라고 부른다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다. double hashing은 선형 프로빙의 문제를 부분적으로는 해결해준다. 아래의 글에서 선형프로빙의 단점(문제점)을 확인할 수 있다. 2021.12.21 - [알고리즘] - [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing) 더블 해슁은 두개의 hash function을 사용하는 것이다. 하나는 처음에 key를 저장할 index를 찾기 위한 것이고, 나머지 하나는 충돌 발생 시 저장할 index를 찾기 위한 것이다. 충돌 발생 시 저장할..

알고리즘 2022. 6. 24. 13:13

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다. 이를 충돌(collision)이라고 부른다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다. 쿼드라틱 프로빙은 선형 프로빙의 문제를 부분적으로는 해결해준다. 아래의 글에서 선형프로빙의 단점(문제점)을 확인할 수 있다. 2021.12.21 - [알고리즘] - [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing) [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing) 오늘은 오픈 어드레싱 중에서 선형 프로빙(linear probing)에 대해 알아보겠습니다. 해쉬테이블은 저장할 key 값은 달라도 h..

알고리즘 2022. 6. 24. 13:04

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다. 이를 충돌(collision)이라고 부른다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다. 체인을 이용하는 방법은 충돌이 발생한 지점에 포인터로 링크드리스트와 같이 연결하는 것이다. 아래는 오버플로 체이닝의 예이다.

알고리즘 2022. 6. 16. 20:40