정렬이란? n개의 서로 다른 수가 주어졌을 떄, 이들을 이동하여 점점 커지게(오름차순), 또는 점점 작아지게(내림차순)으로 만드는 문제이다. ex) 4 2 1 9 5 -> 1 2 3 5 9 이런 식의 문제들은 아주 기본적이지만 실생활에 자주 쓰인다. 수능시험을 본 후 수십 만개의 omr카드를 성적순으로 분류해야하는데 이를 일일히 카운팅하면 정말 피곤할것같다. 머리가 대머리가 되버릴 수도 있다! 이 문제를 풀기 위해선 여러가지 정렬방법을 적용할 수 있다. 대표적인 정렬 방법으로는 버블 정렬 (Bubble sort) 삽입 정렬 (Insert sort) 병합 정렬 (Merge sort) 퀵 정렬 (Quick sort) 힙 정렬 (Heap sort) 그 이외에 버킷 정렬, stable sort, 기수 정렬, 계..
algorithm class
탐색 문제의 최적성 입력으로 주어진 수들 중 어떤 값을 찾는 탐색 문제는 항상 정렬만이 최적의 답은 아니다 문제 1. 정렬되지 않은 배열 A = {1,2,...,n} 중에서, 특정한 수 하나만 빼고, 무작위의 순서로 총 n-1개의 숫자가 한번에 하나씩 입력된다. 배열 A에서 빠진 하나의 수를 찾아라 이러한 문제를 봤을 때 가장 먼저 떠오르는 풀이법은 입력된 숫자들을 boolean배열에 저장하면서 숫자가 나왔을 때 그 배열을 true값으로 바꾸고, n-1개의 숫자가 모두 들어오면 배열을 처음부터 뒤져서 false인 값을 찾는다. 이런식으로 하면 boolean배열이 하나 필요하고, for문을 이용해 배열을 돌면서 boolean을 찾기 때문에 최소 1번, 최대 n번의 비교가 필요한 방법이다. 이 방법의 시간 ..
하노이 탑이란? 그림과 같이 세 개의 기둥과 이 기둥에 꽃을 수 있는 다양한 원판들이 있다. 이 탑은 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 기존에 있던 그대로 다른 기둥으로 옮겨서 다시 쌓아야한다. 조건은 다음과 같다 1. 한 번에 하나의 원판만 옮길 수 있다. 2. 큰 원판이 작은 원판 위에 있어서는 안 된다. 이 문제는 원판의 개수가 적을 경우는 머리로 쉽게 생각할 수 있지만 조금만 커져도 원판을 이동시키는 횟수가 급격하게 많아기지 때문에 생각만큼 쉽지 않다. 이 문제에 대한 해결방안은 알고리즘 설계 기법중 하나인 재귀(recursion)을 이용하는 것인데 방법은 다음과 같다. n=1 : 원판을 그냥 옮긴다 n=k 일 때 옮길 수 있다고 가정 한 후 n=k+1 일 때 (미리 가정한)..
