Algorithm/개념 (12) 썸네일형 리스트형 [Algorithm] 정렬 - 삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort)이란? 이름 그대로, 원소가 들어갈 적당한 자리를 찾아, 삽입하여 정렬하는 방식이다. 예) 1) 배열의 두 번째 값부터 시작한다. arr[1]은 key값으로 따로 저장해놓는다. 2) key값과, 이전 값인 arr[0]값을 비교한다. 3) 이전 값(arr[0])이 key값보다 크므로, 값을 뒤로 한칸 이동시킨다. (arr[0]에 실제로 값이 없어지는 것은 아니지만, 이해를 위해 지웠습니다.) 4) 더 이상 이전으로 이동할 수 없으므로, 비교를 끝내고 저장해놨던 key값을 arr[0]에 설정한다. 5) 다음 값을 key값으로 설정한다. 6) key값과, 이전 값을 비교한다. key값이 더 크므로, 다음으로 넘어간다. 7) 다음 값을 key값으로 설정한다. 8) key값과.. [Algorithm] 유클리드 호제법 유클리드 호제법이란? 두 개의 정수 a, b에 대하여 a, b의 최대공약수를 찾는 방법을 말한다. 유클리드 호제법의 원리 a가 b보다 크다고 할 때, a = bq + r이 성립한다. a, b의 최대공약수를 G라고 하면, a = GA, b = GB가 성립한다. 이를 위 식에 대입하면 GA = GBq + r이다. 여기에서 r = G(A - Bq)로, a와 b와 r의 최대공약수가 G임을 알 수 있다. 알고리즘 위 원리를 이용하여, r = 0일 때 까지 작업을 반복한다. (r = 0인 경우는 나눠 떨어지는 경우) int gcd(int a, int b) { int r = 0; while (b > 0) { r = a % b; a = b; b = r; } return a; } 출처 : https://namu.wiki.. [Algorithm] Breadth-first search (너비 우선 탐색) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 넓이 우선 검색을 적용한다. OPEN List 는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. 출처 : 위키백과https://ko.wikipedia.org/wiki/%EB%84%88%EB%B9%84_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89 예) ① 1을 방문하며 큐에 넣는다. ② 큐에 있는 숫자를 빼, 그 숫자와 인접한 노드들을 차례로 방문하며 큐에 넣는다.(1을 빼며, 1과 인접한 2, 3을 차례로 큐에 넣는다.) ③ 큐에.. [Algorithm] Floyd-Warshall Algorithm (플로이드-워셜 알고리즘) 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)은 그래프에서 모든 꼭짓점 사이의 최단 경로의 거리를 구하는 알고리즘이다. 음수 가중치를 갖는 간선도 순환만 없다면 잘 처리된다. 제일 바깥쪽 반복문은 거쳐가는 꼭짓점이고, 두 번째 반복문은 출발하는 꼭짓점, 세 번째 반복문은 도착하는 꼭짓점이다. 이 알고리즘은 플로이드 알고리즘이라고도 알려져 있다. 출처 : 위키백과 https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 모든 정점들 사이의 최단거리를 구하는 알고리즘이므로, 시간이 많이 소요된다는 단점이 있다. 예) 초기 배.. 이전 1 2 다음
