본문 바로가기

알고리즘58

행렬 90° 회전 (C 언어) 행렬 회전에 대한 설명은 정방행렬 90° 회전 (python) 참고 해당 게시글은 C언어 구현 Code만 작성하였습니다. #include int i, j, k, B[4][5][5]; int main() { int N = 5; int A[][5] = { {0, 0, 0, 0, 1}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 1}, {1, 1, 1, 1, 1}, {0, 0, 0, 0, 1} }; for (i = 0; i < N; i++) { for (j = 0; j < N; j++) { B[0][i][j] = A[i][j]; B[1][N - 1 - j][i] = A[i][j]; B[2][N - 1 - i][N - 1 - j] = A[i][j]; B[3][j][N - 1 - i] = A[i][j].. 2021. 2. 28.

정방행렬 90° 회전 (python) C 언어로 구현한 행렬 회전 ※ 행렬 90° 회전 (C 언어) 행렬 90° 회전 (C 언어) Python으로 구현한 내용은 아래 참고 [Python] 정방행렬 90° 회전 #include int i, j, k, B[4][5][5]; int main() { int N = 5; int A[][5] = { {0, 0, 0, 0, 1}, {0, 0, 0, 0, 1}, {0, 0, 0, 0, 1}, {1, 1, 1, 1.. zoosso.tistory.com Input 5 3 4 1 2 3 2 3 4 5 6 2 3 4 6 7 1 7 6 5 4 6 8 9 3 4 Output 6 1 2 2 3 8 7 3 3 4 9 6 0 4 1 3 5 6 5 2 4 4 7 6 3 행렬을 90° 회전시 아래와 같이 원소를 배치하려는 경.. 2021. 2. 28.

PS시 자주 사용하는 함수 모음 strlen() 문자열의 길이 반환 int strlen(const char*s, int len = 0){ while (s[len]) len++; return len; } strcmp() 문자열 대소 비교 int strcmp(const char*s, const char*t){ while (*s && *s == *t) s++, t++; return *s - *t; } strcpy() 문자열 복사 void strcpy(char*dest, const char*src){ while (*dest++ = *src++); } 문자열 Hash unsigned long djb2(const char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = .. 2021. 2. 28.

BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서는 발견과 방문이 같지 않습니다. ① 아직 발견되지 않은 상태 ② 발견되었지만 아직 방문되지 않은 상태 (큐에 저장되어 있는 상태) ③ 방문된 상태 DFS와 BFS 비교 출처: 나무위키 경로 비교 BFS - Queue 이용 - 최소신장트리(Minimum Spanning Trees), 최단경로(Shortest Paths) 장점: 무한히 깊거나 무한에 가까운 트리인 경우에 효과적 단점: 목표 노드로 가는 경로들 모.. zoosso.tistory.com 활용 최단 경로를 찾을 때 유용 ※ BFS와 달.. 2021. 2. 27.

깊이 우선 탐색(depth-first search, DFS) DFS 그래프의 모든 정점을 방문할 때 최대한 깊숙히 정점을 방문하는 방식입니다. - Stack 이용 즉, 연결된 정점을 따라 계속 순회하다가 갈 곳이 없어지며 바로 이전단계로 가는 백트래킹 방식. (깊이 우선 탐색은 탐색의 각 과정에서 가능한 한 그래프 안으로 '깊이' 들어가려고 시도하며, 막힌 정점에 도달하지 않는 한 뒤로 돌아가지 않습니다. 더 따라갈 간선이 없을 경우 이전으로 돌아갑니다.) 특징 - 찾고자 하는 해가 깊은 곳에 있으면 유용하지만 Stack OverFlow에 유의해야 합니다. - BFS의 경우에는 탐색과정에서 목표를 찾으면 최단경로에 해당되지만 DFS는 최단경로가 아닐 수 있습니다. ▶ DFS와 BFS 비교 DFS와 BFS 비교 출처: 나무위키 경로 비교 BFS - Queue 이용 .. 2021. 2. 27.

최소신장 트리 - 프림(Prim) / 크루스칼(Kruskal) 최소 신장 트리(MST, Minimum Spanning Tree) 사이클을 형성하지 않으면서 모든 간선(Edge)가 최소로 연결된 그래프. ※ 신장 트리(Spanning Tree) 사이클을 형성하지 않지만 모든 노드가 간선(Edge)로 연결되어 있는 그래프. ▶ 간선의 개수 = 정점의 개수 - 1 ex) 정점의 개수 |V| = 6 / 간선의 개수 |E| = 5 5 = 6 -1 ▶ 크루스칼 알고리즘Kruskal's Algorithm 혹은 프림 알고리즘Prim's Algorithm을 통해 구현가능 시간복잡도: 둘다 동일하게 O(ElogV)로 구현 가능 Kruskal's Algorithm ; 가중치가 낮은 간선으로 정점을 이어가면 모든 정점을 방문하는 방식 ① 비용이 낮은 간선 선택 ← 우선순위 큐 ② 선택된.. 2021. 2. 27.

Disjoint-Set & Union-Find Disjoint-Set, 상호 배타적 집합 서로 중복되지 않는 부분 집합들을 의미 (교집합 존재 X) Union-Find Disjoint-Set을 표현할 때 사용하는 알고리즘. ex) 여러 노드가 존재할 때, 두 개의 노드를 선택해서 두 노드가 서로 같은 그래프에 속하는지 판단하는 그래프 알고리즘. 이름 그대로 union 연산과 find 연산이 존재 ▶ union(a, b) : a와 b가 포함되어 있는 집합을 합치는 연산 ▶ find(x) : x가 어떤 집합에 포함되어 있는지 찾는 연산 시뮬레이션 ▶ 모든 노드(정점)은 자기 자신을 가리키는 상태. ▶ 정점 [1] - [2] 연결 / 정점 [3] - [4] 연결 → union(1, 2) / union(3, 4) 일반적으로 두 노드 중 낮은 번호 정점으로 .. 2021. 2. 27.

벨만-포드 (Bellman-Ford) 개념 가중 유향 그래프에서 최단 경로를 구하는 알고리즘입니다. 벨만 포드 알고리즘은 동작원리는 다익스트라(Dijkstra)와 유사합니다. 차이점은 벨만 포드는 음수 가중치가 존재하는 경우에도 적용할 수 있으며 시간 복잡도가 O(VE) 입니다. (V: 정점 개수, E: 간선 개수) 다익스트라 알고리즘에서 우선순위 큐를 이용한 방식으로 시간구현하면 시간 복잡도 O(VlogV)이므로 벨만 포드 알고리즘보다 실행속도가 빠릅니다. 다익스트라 알고리즘의 한계 정점 A → C로 갈 때, 두 가지 경로가 존재합니다. ① A → B → C cost: 7 + (-4) = 3 ② A → C cost: 5 결과적으로는 ① 경로가 최단 거리 비용이지만, 다익스트라 알고리즘에서는 정점 [A]와 연결된 정점 [B], [C] 중에서.. 2021. 2. 26.

다익스트라 (Dijkstra) 개념 다익스트라 알고리즘은 Single Source shortest path problem으로 하나의 정점에서 다른 모든 정점까지 최단 경로를 구할 때 주로 사용됩니다. 이때, 간선의 가중치는 only 양수가 전제조건입니다. (음의 가중치 X) 실제, 현실 세계에서는 음의 가중치는 일반적이지 않기에 현실에 적합한 알고리즘이라고 볼 수 있습니다. 시뮬레이션 그래프를 인접행렬로 표현 ▶ dist[] 배열 초기화 ※ 시작 정점 = [5] 가정. ← 방문 표시 - 정점 [5]와 연결된 정점 [2], [4]와 정점 [5] 자체에 대한 dist[] 초기화 ▶ 방문하지 않은 정점 가장 비용이 적은 정점 [4] 선택 ← 방문 표시 [4]번 정점과 연결되었으면서 동시에 아직 한번도 방문하지 않은 정점 [2], [3]에 .. 2021. 2. 25.

플로이드 와샬 (Floyd Warshall) 개념 아래와 같은 가중 그래프에서 최단 경로를 찾는 알고리즘. ex) 정점 ③ → ⑤로 가는 최단 경로는 다음과 같습니다. 경로Path: ③ → ② → ④ → ① → ⑤ 비용Cost: +4 +1 +2 -4 = 3 플로이드 와샬을 이용해서 정점 [u] → 정점 [v]로 가는 최단 거리를 구할 때, 아래의 두 개의 테이블을 이용합니다. - 최단 거리 비용을 나타내는 테이블 D - 최단 거리 경로를 구할 수 있는 테이블 P 시뮬레이션 ▶ 초기 테이블 상태 - (테이블 D) 『INF』: 현재 시점에서 바로 연결되어 있지 않기에 무한대. - (테이블 P) 『NIL』: 경로가 없다. ▶ 중간 경로로 정점 [1] 추가 정점 [1]을 중간 경유하여 최단 거리 비용 테이블 D가 갱신됩니다. · [4] → [1] → [2.. 2021. 2. 25.

이전 1 2 3 4 5 6 다음

티스토리툴바