공부중

모 회사에서 등장했던 알고리즘이었었고 정보처리 기사에서 자주 등장한다는 그 알고리즘 이다. 말 그대로 달팽이 모양으로 빙빙 돌려가며 데이터를 저장하는 거다. 뭐 문제는 이러했다. N x N 크기의 배열에 달팽이 모양으로 데이터를 저장하고 싶다. 저장하고자 하는 데이터는 이와 같다. "HELLOWORLD" 예로 10x10 행렬에 채우면 다음과 같다. HELLOWORLDWORLDHELLHOLOWORLDOELLLOWORHWLLELWORLEOLEHEODLDLROHDHLLEHLLWDLDLROWODOLROWOLLEHRROWOLLEHDL 여기서의 포인트는…. 맨 처음은 가로크기만큼 n번 채우는 것을 한번만 하고 그 뒤로는 위에서 아래로 n-1회, 우에서 좌로 n-1회 아래에서 위로 n-2회, 좌에서 우로 n-2회 위..

전위법은 찾고자 하는 해당 데이터를 찾았을 시 바로 이전 항목과 교환한다 그 외에는 전진 이동법과 같다.. 74210861395여기 이러한 데이터 집합이 있다. 여기서6을 찾아보자. ↓ 742108613956을 찾았다! 742106813956의 앞에 있는 8과 자리 교환을 한다. main.cpp#include static const int ARRAY_MIN = 0; static const int ARRAY_MAX = 10; int TransposeMethod(int *DataBank, const int nSerchVal); int main( ) { int nArray[ARRAY_MAX] = { 8,6,4,7,5,1,3,9,2,0 }; int nSerchVal = 0; while(true) { std::c..

전진 이동법은 주변 프로그램에서 살펴 볼 수 있는 것은 다음과 같을 것이다. 이러한 최근 기록 부분일 것이다. 전진 이동법은 한번 탐색 되고나면 그 항목을 해당 집합의 맨 앞으로 위치시키는 방법이다. 51892436107다음과 같은 데이터 집합에서 2를 찾는다고 하면 … ↓ 518924361072를 찾았다. 25189436107그리고 다음부터는 2를 맨 앞에서 찾을 수 있다. main.cpp#include static const int ARRAY_MIN = 0; static const int ARRAY_MAX = 10; int MoveToFrontMethod(int *DataBank, const int nSerchVal); int main( ) { int nArray[ARRAY_MAX] = { 8,6,4..

탐색은 흔히 알고 있는 것 처럼 찾는다는 의미를 가지고 있다. 그 중 먼저 순차탐색에 대해서 알아보자.. "무식하면 용감하다" 이런 말이 있지 않은가?? 이 말은 바로 이 탐색을 보고 하는 말인 것 같다. 순차탐색은 말 그대로 처음부터 끝까지 하나하나 일일히 차례대로 비교하는것이다. 찾아야 되는 데이터의 수가 10개든 100개든 1000개든 π의 소수점 개수만큼 있어도 일일히 차례대로 하나하나 비교하는 것이다. 이런 무식한 방법은 물론 너무나도 무식해서 찾는데 보통 데이터의 량에 비례하게 속도가 걸린다. 물론 맨 첫 번째에 있으면 고맙겠지만 보통은 그럴일이 없으니 말이다. 하지만 이 방법이 주는 장점은 바로 구현이 간단해서 버그를 만들 가능성이 매우 적다. 구현이 쉬워서 배열, 링크드 리스트 모두 쉽게 ..

퀵 정렬(Quick Sort)… 이름처럼 빠르다고 한다. 퀵 정렬은 분할 정복(Divide and Conquer)에 기반되어 있다. 전체를 공략하는 대신 전체를 구성하는 구성 요소들을 잘게 나누어 쪼갠 적을 공략하는 기법이다. 퀵 정렬은 다음과 같이 정렬을 수행한다. 데이터 집합 내에서 임의의 기준을 선택하고 기준보다 작은 것은 순서에 관계 없이 기준의 왼쪽에 큰 것은 오른쪽에 위치 이렇게 나눈 데이터를 위에서와 같이 임의의 기준을 다시 선택하고 같은 방법으로 데이터를 분할 한다. 1과 2를 더 이상 나눌 수 없을 때 까지 반복 하면 정렬이 완성 된다. 642315↑기준→ ←642315↑기준 → ←642315↑기준 → ←642315↑기준 →←642315↑기준 → ←기준을 6으로 잡고 Left와 Right..

삽입 정렬은 데이터 집합을 순회 하면서 정렬이 필요한 요소를 뽑아내 이를 다시 적당한 곳에 삽입해가는 알고리즘이다. 데이터 집합에서 정렬 대상이 되는 요소들을 선택 이 정렬 대상은 왼쪽부터 선택해 나가며, 그 범위가 처음에는 2개지만, 알고리즘 반복 횟수가 늘어날 때마다 1개씩 커진다. 정렬 대상의 최대 범위는 '데이터 집합의 크기 - 1'이다. 정렬 대상의 가장 오른쪽에 있는 요소가 정렬 대상 중 가장 큰 값을 가지고 있는지 확인 그렇지 않으면 정렬 대상에서 뽑고 이 요소가 위치할 적절한 곳을 정렬 대상 내에서 찾는다. (적절한 위치는 자신보다 더 작은 요소가 없는 위치를 말함) 뽑은 요소를 삽입할 적절한 곳을 찾았을 때 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한 자리씩 오른쪽으로 ..

버블 정렬은 알고리즘이 데이터를 정렬하는 과정이 물속에서 일어난 거품이 위로 올라오는 모습과 같다고 해서 붙혀졌다. 실제로 데이터가 뜨거나 하지는 않지만 간단하고 손쉽게 할 수 있는 정렬이다. 버블정렬은 데이터들을 순회하면서(곳곳히 돌면서) 교환을 통해서 정렬을 한다. 다음을 보자. 5164231부터 6까지 무작위로 저장된 배열이 있다고 해보자 이때 버블 정렬을 이용해 오름차순으로 정렬 해보자. 516423먼저 5와 1을 비교했을 때 5가 1보다 큰 수이므로 서로 위치 교환을 해준다. 1564231과 5의 위치를 바꾼 뒤 5와 6을 비교해보자. 5는 6보다 작으므로 이동의 변화가 없다. 그러므로 비교대상을 다음으로 넘어간다. 156423비교 대상을 넘어가서 6과 4를 서로 비교해 보자. 6은 4보다 큰 ..