벨만 포드 알고리즘(Bellman-Ford Algorithm)벨만 포드 알고리즘은 그래프 상에서 최단경로를 찾는 알고리즘이다. 최단경로를 찾는 다른 알고리즘인 다익스트라(Dijkstra)알고리즘과 다른 점은 간선의 가중치가 음수여도 가능하다는 점이다. 다만 다익스트라보다 수행시간이 더 오래걸린다는 단점이 있다.따라서 간선의 가중치에 음수가 없다면 다익스트라를, 음수가 있다면 벨만 포드를 사용하는게 일반적으로 좋다. 다익스트라 알고리즘에 대해 알고싶다면 다음 포스팅을 참고하자. [알고리즘] 다익스트라(Dijkstra) 알고리즘이란? 다익스트라 c++ 구현다익스트라(Dijkstra) 알고리즘이란?다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.다익스트..
다익스트라(Dijkstra) 알고리즘이란?다익스트라 알고리즘은 그래프 상에서 시작 정점부터 나머지 각 정점까지의 최단거리를 계산하는 알고리즘이다.다익스트라 알고리즘은 그래프의 어느 간선의 가중치라도 음수가 있으면 안된다. (벨만-포드 알고리즘은 음수도 가능) 다익스트라 알고리즘을 구현하기 위해서는 다음과 같은 과정을 반복하면 된다. 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. (처음엔 시작 정점 방문)2. 해당 정점을 거쳐서 갈 수 있는 정점의 거리가 이전에 기록한 값보다 작다면 그 거리를 갱신한다. 이해가 잘 가지 않는다면 아래 예시를 보면 이해가 빠를 것이다. 위와 같은 그래프가 있다고 하자. 시작정점은 0번 정점이라고 가정하고 나머지 정점까지의 최단거리를 계산해보자.1차원 ..
백트래킹이란?백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다.해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다.즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다.해가 될 가능성이 있다면 유망하다(promising)고 한다.N-Queen 문제N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다. 따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 없다.N-Q..
너비 우선 탐색, BFS 란?BFS는 그래프 탐색 방법 중 하나로 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다.BFS는 큐(Queue) 자료구조를 이용해 구현한다. 큐 자료구조에 대해 알고싶다면 다음 포스팅 참고 [자료구조] 큐(Queue)란? , 큐 C언어 구현큐(Queue) 란?큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스code-lab1.tistory.com BFS의 과정BFS 는 다음과 같은 과정을 거치게 ..
DFS란?DFS 는 Depth First Search 의 줄임말로 깊이 우선 탐색이라는 뜻이다. DFS는 보통 트리 혹은 그래프 탐색에서 사용되는 알고리즘으로 깊이를 우선하여 목표노드를 찾는 탐색법을 뜻한다.DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다. DFS 예시위와 같은 트리 구조가 있다고 하자. 이 때 DFS 는 다음의 과정을 거치게 된다.가장 먼저 루트노드인 A를 방문하고, 스택에 추가한다.이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가한다. (C노드를 먼저 방문해도 된다. 순서는 상관 없다)이후 스택의 top부분에 있는 B의 인접 노드인 D노드를 방문하고, 스택에 D노드를 추가한다.이후 스택의 top 부..
피보나치 수열피보나치수열은 제2항 까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수가 반복되는 수열이다.1, 1, 2, 3, 5, 8, 13, 21, 34, 55...이러한 피보나치수열을 구현할 때는 보통 재귀를 통해 표현하게 된다. c언어에서는 아래와 같이 구현 할 수 있다.int fibo(int n){ if (n 이렇게 재귀를 통해 피보나치 수열을 구하게 되면 중복 연산이 많아져 매우 비효율적이다. 예를 들어 fibo(5)를 구한다고 하자.fibo(5)를 구할 때 위와 같은 과정을 거쳐 구하게 된다. 그림을 보면 fibo(1), fibo(2), fibo(3) 연산이 중복되는 것을 볼 수 있다. 만약 fibo(1), fibo(2), fibo(3) 연산의 값을 어딘가에 저장해 놓는다면, 중복해서..
퀵 정렬(Quick Sort)퀵정렬은 합병정렬과 비슷하게 분할정복(Divide and Conquer) 알고리즘이다. 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법으로 다음과 같은 과정을 거친다.1. 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 pivot(피벗) 이라고 한다.2. pivot을 기준으로 pivot보다 작은 요소들은 모두 pivot의 왼쪽으로 옮기고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다.3. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.3-1) 분할된 왼쪽 리스트와 오른쪽 리스트도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분리스트로 나눈다.3-2) 재귀를 사용하여 부분 리스트들이 더이상 분할이 불가능 할 때까지 반..
삽입 정렬(Insertion Sort)삽입정렬은 두 번째 원소부터 시작하여 그 앞의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다.위와 같은 배열을 오름차순으로 정렬한다고 하자.두 번째 원소인 5부터 시작하여 그 앞의 원소들과 비교를 시작한다.5와 7을 비교해 5가 더 작으므로 7을 한 칸 뒤로 옮기고 그자리에 5를 삽입한다.세 번째 원소인 1과 그 앞의 원소 7을 비교해 1이 더 작으므로 7을 한 칸 뒤로 민다.그 앞의 원소 5와 1을 비교해 1이 더작으므로 5를 한 칸 뒤로 밀고 1을 그 자리에 삽입한다.네 번째 원소인 4와 그 앞의 원소 7을 비교해 4가 더 작으므로 7을 한 칸 뒤로 민다.그 앞의 원소 5와 4를 비교해 4가 더..
선택정렬(Selection Sort)선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 거친다.1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다.2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다.3. 다음 인덱스에서 위 과정을 반복한다.과정이 잘 이해가 가지 않는다면, 다음 예시를 보면 이해가 빠를 것이다.예를 들어 위와 같은 배열을 오름차순으로 선택정렬한다고 하자.가장 먼저 맨 앞의 7부터 시작한다. 7 뒤의 값들 중 가장 작은 값인 1과 자리를 바꾼다. i는 현재 인덱스, minIdx는 가장 작은 값의 인덱스를 나타낸다.다음은 5와 그 이후 값들 중 가장 작은 값인 3의 위치를 바꿔준다..
버블 정렬(Bubble Sort)버블정렬은 현재 원소와 다음 원소를 비교하여 조건에 맞으면 교환하는 식의 정렬이다. 원소가 거품처럼 올라오는 듯해 버블 정렬이라는 이름이 붙었다.위와 같은 배열을 오름차순으로 버블 정렬한다고 하자.처음 7과 5를 비교해 7이 더 크므로 위치를 바꾼다. 이후 배열의 끝까지 비교해서 값이 더 크다면 위치를 바꿔준다.다시 5와 1을 비교해 5가 더 크므로 위치를 바꿔준다. 이번엔 정렬이 끝난 7 전까지만 해당 과정을 반복 해준다.다시 1과 4를 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이후 4와 3을 비교했을 때 4가 더크므로 위치를 바꿔준다.1과 3을 비교해 1이 더 작으므로 위치를 바꾸지 않는다. 이렇게 하면 버블 정렬이 완료된다.버블정렬의 특징버블 정렬은 하나의 배..
해시 테이블(Hash Table)이란?해시 테이블은 (Key, Value)식으로 데이터를 저장하는 자료구조 중 하나로 key를 통해 평균 O(1)에 value를 검색할 수 있는 자료구조이다.해시 테이블은 Key 값을 해시함수(Hash Function)를 사용하여 변환한 값을 색인(index)으로 삼는다.해시 함수(Hash Function)를 사용해 Key 값을 색인(index)으로 변환하는 과정을 해싱(Hashing)이라고 한다. 해시 함수(Hash Fucntion)해시 함수의 가장 중요한 점은 고유한 인덱스를 만드는 것이다. 만약 중복되는 인덱스가 발생한다면 이는 충돌(Collision)로 이어지게 된다. 따라서 해시 함수를 구현하는 해시 알고리즘을 적절히 구현하는 것이 중요하다. 해시 테이블에 사용되..
그래프란?그래프는 연결되어 있는 원소 사이의 다대다 관계를 표현하는 자료구조이다.그래프 G는 객체를 나타내는 정점 V(vertex)와 객체를 연결하는 간선 E(edge)의 집합이다.트리도 그래프의 한 종류이며, 그 중 사이클(cycle)이 허용되지 않는 그래프를 말한다.그래프의 종류방향 그래프 vs 무방향 그래프간선에 방향이 있는 그래프는 방향 그래프(Directed Graph) 라고 하고, 간선에 방향이 없는 그래프를 무방향 그래프(Undirected Graph) 라고 한다.완전그래프완전 그래프(Complete Graph)는 각 정점에서 다른 모든 정점이 연결된, 최대한 많은 간선 수를 가진 그래프를 뜻한다.정점이 N개인 무방향 그래프에서 최대 간선 수 : N(N-1)/2 개 ( ex : 위 그림에서 ..
