본문 바로가기

알고리즘(Algorithm)

 (45)
그래프(Graph)-너비우선탐색(BFS, Breadth First Search) algorithm 지금까지 그래프란 무엇이고 그래프를 표현하기위한 방법으로 인접행렬과 인접리스트를 알아보았다. 이번에는 그래프의 모든 정점(노드)들을 방문하는 순회(traversal)에 대해서 알아보려고한다. 그래프의 일종인 트리에서도 이미 순회하는 방법을 알아 보았는데 pre-order, in-order, post-order, level-order 가 있었다. 그래프에서는 모든 정점들을 순회하기위한 방법은 여러가지가 있지만 대표적으로 2가지가 있는데 하나는 너비우선탐색(BFS, Breadth First Search)이고 다른 하나는 깊이우선탐색(DFS, Depth First Search)이다. △ [출처] https://neo4j.com/blog/graph-algorithms-neo4j-graph-algorithm-co..
그래프(Graph)-깊이우선탐색(DFS, Depth First Search) 그래프를 순회하기위한 방법중 너비우선탐색(BFS, Breadth First Search) 은 알아봤고 이번에는 깊이우선탐색(DFS, Depth First Search)알고리즘을 살펴보자. 깊이우선탐색(DFS, Depth First Search)은 이진트리의 전위순회(pre order)과 비슷한 개념이고 재귀나 스택(Statck)를 이용하여 알고리즘을 구현할 수 있다. △ [출처] https://www.tutorialspoint.com/data_structures_algorithms/depth_first_traversal.htm 위에서 주어진 예제에서와 같이 DFS 알고리즘은 S에서 A에서 D로 G에서 E에서 B로, F에서 마지막으로 C로 이동한다. DFS를 스택를 이용하여 구현할 수 있다고 하였는데 코드..
최소신장트리(Minimum Spanning Tree)-크러스컬(Kruskal) 알고리즘 최소신장트리를 생성하기위한 알고리즘으로 크러스컬 알고리즘을 설명한다. 만약 최소신장트리가 무엇인지 모른다면 최소신장트리(Minimum Spanning Tree) 를 먼저 학습해야한다. Q. 크러스컬 알고리즘은 무엇인가 ? 크러스컬 알고리즘은 최소신장트리를 생성하기위한 알고리즘 중하나로 핵심은 모든 그래프 G 에 연결된 모든 에지들의 가중치를 오름차순으로 정렬하고 에지 중 가장 작은 것부터 하나씩 이어 나가는 방법이다. 주의 할 점은 이어 붙일 때 그래프에 사이클이 생기지 않도록 해야(신장트리가 되려면 사이클이 없다고 얘기했다.) 한다는것이다. 그림으로 설명하면... STEP (a) 그래프에서 에지의 가중치가 가장 작은 E = (h,g)를 젤 먼저 선택한다. 이어서 가중치가 낮은 순서대로 하나씩 선택해 나..
멱집합(Power Set) A의 모든 부분집합을 원소로 하는 집합을 A의 멱집합(power set)이라 하고 P(A) 또는 2A로 나타낸다. 예를들어 S = { 1 , 2, 3, 4 } 일때 부분집합(power set) = {{}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4}, {2,3,4}, {1,2,3,4}} 이다. 따라서 임의의 유한집합에 대해서 그 크기가 |A| = n 이라고 할때, 부분집합의 개수는 2n 개가 된다. 그럼 컴퓨터에서 임의의 집합의 모든 부분집합을 출력하는 알고리즘은 어떻게 될까? 사실 생각해보면 { a, b, c, d, e, f } 의 모든 부분집합을 나열하려면 a 를 제외한 { b, c, d,..
분할정복(Divide & Conquer) 알고리즘이란? 분할정복 알고리즘(Divide and Conquer Algorithm)이란 해결하고자 하는 문제(Problem)를 통째로 놓고 푸는 것이 아니고 문제를 작은 크기의 동일한 문제들(Problems)로 분할해서 각각의 작은 문제를 순환적으로 해결하는 방법을 말한다. ▲ [출처] https://medium.com/cracking-the-data-science-interview/divide-and-conquer-algorithms-b135681d08fc 분할정복에 대한 유례는 1805년 12월 2일 아우스터리츠 전투에서 프랑스의 황제 나폴레옹이 사용했던 훌륭한 전략에서 따왔다고 한다. 오스트리아-러시아 연합군은 나폴레옹의 군대보다 15,000명 정도 많았다. 연합군은 프랑스군의 우측면에 대규모 공격을 감행했다...
버킷정렬(Bucket Sort) 버킷 정렬(bucket sort) or bin sort 은 입력 값이 일정한 범위에 걸쳐 분포(uniformly distributed)되어있을 때 주로 유용하다. 예를들어 0.0에서 1.0 범위의 부동 소수점 숫자 집합을 정렬해야 하고 싶다고 할때 선택할수 있는 정렬의 방법은 여러가지이다. 간단한 방법은 비교 기반 알고리즘(comparision based sort alogrithm)을 적용하면 된다. 비교 기반 알고리즘 중 그래도 시간복잡도가 좀 빠른 병합 정렬(merge sort), 힙 정렬(heap sort), 빠른 정렬(quick sort)은 O(nLogn) 이다. 즉 O(nLogn)보다 좋을수는 없다. 선형 시간(linear time)으로 배열을 정렬할 방법은 없을까? 카운팅 정렬(counting..
(재귀)피보나치 수열(Fibonacci Sequence) 피보나치치 수열(Fibonacci Sequence)은 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열을 말한다. ▲ (출처: https://blogs.glowscotland.org.uk/glowblogs/jypetrieuodep/2018/10/09/fibonacci-sequence-significant-coincidence/) 피보나치 수열을 구현하기 위한 방법이 몇가지 존재하는데 여기서는 재귀함수를 이용하도록 하겠다. 재귀함수(Recursive Function)란? 글을 읽어보면 재귀함수에는 재귀가 수렴해야 할 베이스케이스와 재귀케이스가 있어야 하는데 0번째 항부터 피보나치 수열을 시작할 경우 베이스케이스와 재귀케이스는 아래와 같다. 베이스케이스 : F0 = 0 and F1 ..
(재귀)N-Queen 문제 N-Queen 문제는 재귀문제중 매우 대중적인 문제인데 어떤 문제인지 파악부터 해보자. N-Queen 문제는 N x N 크기의 체스판에 N 개의 퀸을, 서로 공격할 수 없도록 올려놓는 솔류션을 구하는 문제이다. 예를들어 8x8 체스판이 있다면 그림1. 처럼 Queen은 N=8개가 놓일 수 있는데 이게 맘대로 배치하면 안되고 특정 규칙에 따라 배치해야 한다. 특정 규칙이라는것은 그림2처럼 Queen 이 배치 될때 같은 행(row), 열(column)에 다른 Queen이 있으면 안되고 대각선(diagonal) 으로도 있으면 안된다는 것이다. [출처] https://helloacm.com/n-queen-problem-in-back-tracing-bit-logics/ 여기까지 왔으면 문제는 다 파악된것이다. 요..

티스토리툴바