알고리즘

신장 트리(Spanning Tree)신장 트리(Spanning Tree)는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이기도 하다. 그래서 이러한 그래프를 신장 트리라고 부른다. 크루스칼 알고리즘우리는 다양한 문제 상황에서 가능한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있다. 예를 들어 N개의 도시가 존재하는 상황에서 두 도시 사이에 도로를 놓아 도시가 서로 연결될 수 있게 도로를 설치하는 경우를 생각해보자. 2개의 도시 A, B를 선택했을 떄, 도시 A에서 도시 B로 이동하는 경로가 반드시 존재하도록 도로를 설치하고자 한다. 모든 도시를 연결할 때, ..

그래프(Graph) 그래프(Graph)란? 노드(Node)와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조를 의미한다. 알고리즘 문제를 접했을 때 '서로 다른 개체(혹은 객체)가 연결되어 있다.'는 말이 나오면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 예를 들어 '여러 개의 도시가 연결되어 있다.'와 같은 내용이 등장하면 그래프 알고리즘을 의심해 봐야 한다. 트리(Tree) 자료구조트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다. 컴퓨터공학 분야에서 트리 자료구조는 방향 그래프로 간주된다.  그래프트리방향성방향 그래프 혹은 무방향 그래프방향 그래프순환성순환 및 비순환비순환루트 노드 존재 여부루트 노드가 없음루트 노드가 존재노드간 관계성부모와 자식 관계 없음부모와 자식 관계모..

플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘이다. 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm)은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다.  다익스트라 알고리즘은 단계마다 최단 거리를 가지는 노드를 하나씩 반복적으로 선택한다. 그리고 해당 노드를 거쳐 가는 경로를 확인하며, 최단 거리 테이블을 갱신하는 방식으로 동작한다. 플로이드 워셜 알고리즘 또한 단계마다 '거쳐 가는 노드'를 기준으로 알고리즘을 수행한다. 하지만 매번 방문하지 않은 노드 중에서 최단 거리를 갖는 노..

최단 경로(Shortest Path) 알고리즘 최단 경로(Shortest Path) 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단 경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다.  최단 경로 문제는 보통 그래프를 이용해 표현하는데 각 지점은 그래프에서 '노드'로 표현되고, 지점  간 연결된 도로는 그래프에서 '간선'으로 표현된다.  코딩 테스트에서 가장 많이 등장하는 최단 거리 알고리즘은 다익스트라 최단경로와 플로이드 워셜 알고리즘이다. 최단경로 알고리즘에는 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 그대로 적용된다는 특징이 있다.  다익스트라(Dijkstra) 알고리즘다익스트라(Dijkstra) 최단 경로 알고리즘은 그래프에서 ..

다이나믹 프로그래밍(Dynamic Programming)은 동적 계획법이라고도 하며, 메모리 공간을 약간 더 사용함으로써 연산 속도를 비약적으로 줄일 수 있는 방법이다.  다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치 수열의 점화식은 다음과 같이 표현할 수 있다. 결과적으로 첫 번째 항과 두 번째 항의 값이 모두 1이기 때문에 최종적으로 피보나치 수열을 나타낼 때에는 다음과 같이 정의할 수 있다.이를 해석하면 다음과 같다. n번째 피보나치 수=(n-1)번째 피보나치 수  + (n-2)번쨰 피보나치 수단, 1번째 피보나치 수 = 1, 2번째 피보나치 수 = 1프로그래밍에서는 이러한 수..

순차 탐색(Sequential Search) 순차 탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있다.  순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용..

정렬(Sorting) 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 정렬 알고리즘을 공부하다 보면 자연스럽게 알고리즘 효율의 중요성을 깨달을 수 있다.  예를 들어 숫자가 하나 씩 적힌 카드가 10장이 있다.이제 이 카드를 오름차순으로 정렬하자. 보통은 카드를 빠르게 흝고 숫자가 0부터 9까지로 구성된   걸 눈치챈 다음 카드를 0부터 9까지 순차적으로 나열할 것이다. 이러한 과정 속에서 우리의 뇌는 우리도 모르게 데이터의 규칙성을 파악한다. 하지만 우리에게 쉽다고 컴퓨터에도 쉬운 일은 아니다. 컴퓨터는 인간과 다르게 데이터의 규칙성을 직관적으로 알 수 없으며, 어떻게 정렬을 수행할지에 대한 과정을 소스코드로 작성하여 구체적으로 명시해야 한다. 이 카드 예제를 기..

DFS(Depth-First Search) - 깊이 우선 탐색  DFS(Depth-First Search)는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 이 알고리즘은 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.  DFS는 스택 자료구조를 이용하며 구체적인 동작 과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.  ..