선택정렬(Selection Sort) 선택정렬은 현재 위치에 들어갈 값을 찾아서 바꾸는 알고리즘이다. 오름차순으로 정렬하는 선택정렬은 다음과 같은 과정을 거친다. 1. 현재 정렬되지 않은 가장 맨 앞의 인덱스를 선택한다. 2. 현재 인덱스의 다음 인덱스부터 끝까지 가장 작은 값을 찾으면 현재 인덱스의 값과 바꿔준다. 3. 다음 인덱스에서 위 과정을 반복한다. 과정이 잘 이해가 가지 않는다면, 다음 예시를 보면 이해가 빠를 것이다. 예를 들어 위와 같은 배열을 오름차순으로 선택정렬한다고 하자. 가장 먼저 맨 앞의 7부터 시작한다. 7 뒤의 값들 중 가장 작은 값인 1과 자리를 바꾼다. i는 현재 인덱스, minIdx는 가장 작은 값의 인덱스를 나타낸다. 다음은 5와 그 이후 값들 중 가장 작은 값인 3의 ..
백트래킹이란? 백트래킹(Backtracking) 은 해를 찾는 도중 해가 아니어서 막힌다면, 되돌아가서 다시 해를 찾아가는 기법이다. 해를 찾아가는 도중, 지금의 경로가 해가 될 것 같지 않다면 그 경로를 더이상 가지 않고 되돌아간다. 이것을 가지치기(Pruning) 이라고 한다. 즉, 백트래킹은 모든 가능한 경우의 수 중에서 특정 조건을 만족하는 경우만 살펴보는 것이다. 해가 될 가능성이 있다면 유망하다(promising)고 한다. N-Queen 문제 N-Queen 문제는 N X N 크기의 체스판에 N개의 퀸(Queen)을 서로 공격할 수 없도록 배치하는 문제이다. 이 때 퀸은 상하좌우, 대각선 방향으로 체스판의 끝까지 공격을 할 수 있다. 따라서 아래 그림처럼 직선, 대각선 상에는 퀸을 배치 할 수 ..
너비 우선 탐색, BFS 란? BFS는 그래프 탐색 방법 중 하나로 임의의 시작 정점에서부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 주로 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. BFS는 큐(Queue) 자료구조를 이용해 구현한다. 큐 자료구조에 대해 알고싶다면 다음 포스팅 참고 [자료구조] 큐(Queue)의 개념, 이해 | c언어 큐 연결리스트로 구현, 소스코드 큐(Queue) 란? 큐는 컴퓨터의 기본적인 자료구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스 code-lab1.tistory.com BFS..
DFS란? DFS 는 Depth First Search 의 줄임말로 깊이 우선 탐색이라는 뜻이다. DFS는 보통 트리 혹은 그래프 탐색에서 사용되는 알고리즘으로 깊이를 우선하여 목표노드를 찾는 탐색법을 뜻한다. DFS는 특정 노드에서 시작해 다음 분기로 넘어가기 전에 해당 분기를 완전히 탐색하는 방법이다. DFS 예시 위와 같은 트리 구조가 있다고 하자. 이 때 DFS 는 다음의 과정을 거치게 된다. 가장 먼저 루트노드인 A를 방문하고, 스택에 추가한다. 이후 스택의 top 부분에 있는 A의 인접 노드인 B노드를 방문하고, 스택에 B노드를 추가한다. (C노드를 먼저 방문해도 된다. 순서는 상관 없다) 이후 스택의 top부분에 있는 B의 인접 노드인 D노드를 방문하고, 스택에 D노드를 추가한다. 이후 스택..
그리디(Greedy) 알고리즘이란? 그리디 알고리즘은 "매 선택에서 그 순간 당장 최적인 답을 선택" 하여 적합한 결과를 도출하는 알고리즘 설계 기법이다. 그리디 알고리즘은 최적 부분 구조(optimal substructure)를 가진 문제를 해결하는데 강점이 있다. 최적 부분구조란 매 순간의 최적해의 합이 문제에 대한 최적해여야 한다는 의미이다. 예를 들어 누군가 A도시에서 B도시를 거쳐 C도시로 간다고 하자. A도시에서 B도시를 갈 때 가장 짧은 거리인 150km 경로를 선택하고, B도시에서 C도시로 갈 때 가장 짧은 거리인 140km 경로를 선택하면, 전체적으로도 최적의 경로가 된다. 매 순간 최적 경로의 합이 전체 경로의 최적 경로가 되었다. 이러한 최적 부분 구조를 가진 문제는 그리디 알고리즘으..
피보나치 수열 피보나치수열은 제2항 까지는 1, 제3항부터는 바로 앞의 두 항을 더한 수가 반복되는 수열이다. 1, 1, 2, 3, 5, 8, 13, 21, 34, 55... 이러한 피보나치수열을 구현할 때는 보통 재귀를 통해 표현하게 된다. c언어에서는 아래와 같이 구현 할 수 있다. 1 2 3 4 5 6 int fibo(int n){ if (n
정의 Divide and Conquer(분할정복)은 해결하기 힘든 큰 문제를 작은 문제로 분할하여 해결(정복)한 후 병합하는 알고리즘이다. 접근법 분할정복은 보통 다음과 같은 3단계의 과정을 거친다. 1. Divide(분할) : 문제를 더 작은 문제들로 분할 2. Conquer(정복) : 분할한 작은 문제들을 해결한다. 3. Combine(병합) : 작은 문제들의 해결법을 병합해 큰 문제의 해결법을 찾는다. 특징 1. 문제를 나눌 때 보통 재귀(recursion)를 많이 사용한다. 2. 재귀(recursion)를 이용할 때 오버헤드가 커 메모리를 많이 사용할 수 있다. 예시 Merge Sort(병합 정렬) 병합 정렬은 분할정복의 대표적인 예이다. n개의 데이터를 가진 배열을 오름차순으로 정렬하기 위해 병..