수학인듯 과학아닌 공학같은 컴퓨터과학/알고리즘 기초

이 문서는 정말 쉽습니다.

문서의 내용이 너무 쉬워서 오늘부터 프로그래밍 할 수 있을 것 같습니다.

이 문서는 쉽게 알 수 있다 시리즈이며, 집단연구 문서입니다.

이 문서에는 독자적으로 연구한 내용이 들어갑니다. 다른 사람의 의견을 존중하면서 무례하지 않도록 작성해 주시고, 의견 충돌 시 토론 문서에서 토론해 주세요.

들어가기 전

~~일단 이게 입문인지부터 생각해보자~~ 빨간 컵에 칠성사이다가 담겨져 있고 파란 컵에 스프라이트가 담겨져있다. 여기서 파란 컵에 칠성사이다를 넣고 빨간 컵에 스프라이트를 넣을려면 어떻게 해야 될까? 해답은 간단하다. 다른 컵(여기선 노란 컵이라 하겠다.)에 빨간 컵의 칠성사이다를 노란 컵에 붓고 빨간 컵이 비게 되면 파란 컵의 스프라이트를 빨간 컵에 붓고 파란 컵이 비게 되면 노란 컵에 담았던 칠성사이다를 파란 컵에 부으면 된다. 갑자기 노란 컵이 튀어나와서 쌩뚱맞다고 생각하는 사람이 있을 수 있겠지만 다른 컵을 쓰면 안된다고는 안했다. 알고리즘은 문제를 해결하기 위한 것이지 수수께끼나 넌센스 문제가 아니다.

이 이야기가 왜 나왔냐면 프로그래밍을 할 때 아래 소스 처럼 2개의 변수 값을 서로 바꿀 경우 변수 2개 가지고 끙끙 거리지 말고 간단하게 변수 하나 더 사용해서 쉽게 해결하면 되기 때문이다. ~~이제 제 3의 변수를 쓰지 않고 변수 2개의 값을 맞바꾸는 알고리즘을 생각해보자.~~

의사코드 펼치기

 1 function 바꾸기(첫번째컵, 두번째컵):
 2     잠시담아둘컵 ← 첫번째컵
 3     첫번째컵 ← 두번째컵
 4     두번째컵 ← 잠시담아둘컵
 5 end function
 6
 7 function 지금상황():
 8     파란컵 ← "칠성사이다"
 9     빨간컵 ← "스프라이트"
10     바꾸기(파란컵, 빨간컵)
11     print 파란컵
12     print 빨간컵
13 end function

using System;

namespace 사이다컵바꾸기
{
    class Program
    {
        static void Main(string[] args)
        {
            // 빨간 컵과 파란 컵에 칠성사이다와 스프라이트가 담겨져 있다.
            string 빨간컵 = "칠성사이다";
            string 파란컵 = "스프라이트";

            Console.WriteLine("=====바꾸기 전=====");
            Console.WriteLine("빨간컵 : {0}", 빨간컵);
            Console.WriteLine("파란컵 : {0}", 파란컵);

            // 새롭게 준비한 노란 컵
            string 노란컵;

            // 스프라이트를 빨간 컵에 붓기 위해 칠성사이다를 노란컵에 붓는다.
            // 그 다음 파란 컵의 스프라이트를 빨간 컵에 붓는다.
            // 그 다음 노란 컵에 임시로 담아둔 칠성 사이다를 파란 컵에 붓는다.
            노란컵 = 빨간컵;
            빨간컵 = 파란컵;
            파란컵 = 노란컵;

            Console.WriteLine("=====바꾼 후=====");
            Console.WriteLine("빨간컵 : {0}", 빨간컵);
            Console.WriteLine("파란컵 : {0}", 파란컵);
        }
    }
}

여담으로, 위 취소선의 답은 의외로 간단하다. 정수가 저장되어 있는 a와 b가 있을 때, a와 b를 더한 다음 a에 저장한다. 그 다음 a에서 b를 뺀 값(즉 원래 a값)을 b에 저장한다. 그 다음 a에서 b를 뺀 값을 a에 저장하면 된다. ~~숫자가 아니고 객체면?~~ ~~포인터 주소값을 더하고 빼면... ...~~ 사실 덧셈보다 더 빠른 방법은 XOR 회로를 사용하는법이 있다. 값이 같지 않으면 a=a^b b=a^b a=a^b를 넣어두면 정수가 아니더라도, 산술적 연산이 아니라 비트 배열 자체가 바뀌기 때문에 값이 교환된다.~~하지만 병렬 프로그래밍에서는 무리DA☆ZE★~~

알고리즘의 시간 복잡도

방을 정리한다고 해보자. 방에 널려있는 물건의 양에 따라 정리에 걸리는 시간이 달라질 것이다. 이렇게 입력된 자료의 양과 알고리즘 실행에 걸리는 시간 사이에는 어느 정도의 관계가 있는데, 이걸 알고리즘의 시간 복잡도라 한다.

알고리즘의 시간 복잡도는 계산 횟수가 많아지면 높아진다. 그런데 이 계산 횟수의 정확한 측정이 어렵기 때문에, 보통 Big O 표기법이라는 걸 이용해서 표시한다.

예를 들어, 입력된 데이터의 갯수가 [math]\displaystyle{ n }[/math]개일 때 [math]\displaystyle{ 2n+7 }[/math]번 계산하는 알고리즘과 [math]\displaystyle{ 2n }[/math]번 계산하는 알고리즘이 있다고 하자. [math]\displaystyle{ n }[/math]이 커지면 둘 사이의 차이는 사실상 없어진다. 즉 [math]\displaystyle{ O(2n+7)=O(2n) }[/math]이다. 좀 더 나아가면 계산 횟수가 [math]\displaystyle{ n }[/math]에 비례하므로, 그냥 [math]\displaystyle{ O(n) }[/math]라고 표현할 수 있다. 일반적으로, 이 중 가장 간단한 형태인 [math]\displaystyle{ O(n) }[/math]로 표기한다. 이와 비슷하게, [math]\displaystyle{ 2n^3+n^2 }[/math]번 계산하는 알고리즘의 시간 복잡도는 [math]\displaystyle{ O(n^3) }[/math]로 나타낼 수 있다.

자주 등장하는 알고리즘의 시간 복잡도는 아래와 같다. 위에서 아래로 갈수록 시간 복잡도가 높아진다.

시간 복잡도	설명
[math]\displaystyle{ O(1) }[/math]	상수 형태. n의 값에 상관없이 일정한 양의 계산만 한다.
[math]\displaystyle{ O(\log n) }[/math]	로그 형태
[math]\displaystyle{ O(n) }[/math]	선형
[math]\displaystyle{ O(n\log n) }[/math]	선형로그 형태
[math]\displaystyle{ O(n^2), O(n^3),\cdots }[/math]	다차 형태
[math]\displaystyle{ O(2^n) }[/math]	지수 형태
[math]\displaystyle{ O(n!) }[/math]	팩토리얼 형태

예를 들어 아래의 링크드 리스트에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 [math]\displaystyle{ O(n) }[/math], 해시 테이블에서 특정 값을 찾는데 걸리는 평균 시간 복잡도는 [math]\displaystyle{ O(1) }[/math]이다. 이는 평균적으로 해시 테이블에서의 탐색이 링크드 리스트에서의 탐색보다 빠르다는 뜻이다.

알고리즘의 정당성 증명

갑자기 왠 뜬금없이 증명이 튀어나왔는지 궁금할 것이다. 당연하지만, 우리는 천재가 아니라서 머릿속으로 생각한 알고리즘이 실제로 아주 잘 돌아간다고 보장할 수 없기 때문에 생각해낸 알고리즘이 문제를 풀 수 있다는 것을 보여야 한다.

수학적 귀납법

다들 수학 공부하면서 한 번씩은 들어봤을 그것이다. 수학적 귀납법을 이용한 증명은 크게 단계 나누기와 첫 단계 증명, 귀납 증명으로 나눈다. 자세한 내용은 해당 항목 참고.

반복문 불변식

반복문의 내용이 매 번 실행될 때마다 중간 결과가 올바른 답을 도출하기 위한 결과로 잘 나오는지를 판별하는 조건이다. 반복문이 마지막에 올바른 답을 내놓으려면 항상 이 식이 변하지 않아야 한다(그러므로 불변식이라고 한다).

불변식을 이용해 다음과 같이 반복문의 정당성을 증명할 수 있다.

반복문 진입시에 불변식이 성립함을 보인다.(초기 조건)
반복문 내용이 불변식에 영향을 주지 않음을 보인다.(유지 조건)
반복문 종료후 불변식이 성립하면 항상 올바른 답이 나옴을 보인다.

귀류법

수학에서도 많이 사용되는 만능의 증명법, 귀류법이다. 자세한 내용은 해당 항목 참고.

비둘기집의 원리

경우의 수에서 자주 언급되는 그 원리 맞다. 해당 항목 참고.

구성적 증명

위에 언급한 증명 방법들과는 달리, 구성적 증명은 답의 존재성을 보이는게 아닌, 답을 구하는 방법 그 자체를 보이는 것이다. 쉽게 말해, 그냥 답을 구하는 알고리즘의 실행 과정을 설명한다고 생각하면 된다.

이 문서에서 알고리즘을 표현하기위해 사용한 언어

아래 나오는 모든 코드는 C언어를 기본으로 하며, 다른 언어들은 알아서 추가해주길 바란다. 실제 문제 풀이 예제를 제외한 알고리즘을 의사코드로 작성할 수 있다면 각 언어별 코드보다 위에 의사코드 버전을 추가해주길 바란다.

플로우 차트

기호

자료구조

데이터를 저장하는 방식을 말한다. 수많은 자료구조 중 데이터에 맞는 특성을 지닌 자료구조를 선택하는 것은 효율적인 알고리즘 작성에 반드시 필수적이다.

선형 자료구조

한 종류의 데이터가 선처럼 길게 나열된 자료구조이다.

랜덤 접근 가능

모든 자료에 O(1)으로 접근이 보장되는 자료구조들이다.

배열

가장 쉬운 자료구조이자 언어에 따라 활용법이 가장 크게 달라지는 자료구조. C언어에서는 대괄호를 사용한다.

int array1[]; //int *array1과 비슷함.
int array2[10]; //크기를 가지는 배열
int array3[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}; //초기화한 배열

C에서 배열에 포인터를 사용하여 접근하는 것을 보면, 배열의 각 원소의 주소가 연속적으로 배치되어 있다는 것을 알 수 있다.

해시

해시는 해시 함수로 구현한다. 해시 함수는 마치 배열처럼, 어떤 자료를 찾을 때 [math]\displaystyle{ O(1) }[/math]의 시간만을 소요한다. 해시함수에 키 값을 넣어 주소값을 얻고, 그 주소에 위치한 버킷에 저장된 데이터를 가져오는 방식을 사용한다. 하지만, 언제나 [math]\displaystyle{ O(1) }[/math]이 보장되는 것은 아니다. 자세한 것은 해시 테이블 참고.

랜덤 접근 불가능

모든 자료에 O(1)으로 접근이 보장되지 않는 자료구조들이다.

스택

스택 자료구조

먼저 들어간 자료가 나중에 나오는 자료구조. 유식한 말로 후입선출(後入先出) 구조라고 한다. 자료를 넣는 push 함수와 자료를 빼는 pop 함수를 갖는 게 정석이다. empty, full 등 다른 함수들을 옵션으로 가질 수도 있다.

아래는 배열로 구현한 스택이다.^[1]

//헤더 부분
void push(int); //push 함수 정의
int pop();

//소스 부분
int array[500]; //스택의 최대 크기는 500
int top = -1; //스택의 현재 크기는 0;

void push(int n)
{
    top = top + 1;
    array[top] = n;
}
int pop()
{
    int value = array[top];
    top = top - 1;
    return array[top];
}

사용법은 스택에 넣고 싶은 것을 push로 넣고, pop로 빼면 된다.

push(1), push(2), push(3);
printf("%d %d %d", pop(), pop(), pop());

출력 결과는 3 2 1과 같을 것이다.

큐

큐 자료구조

먼저 들어간 자료가 먼저 나오는 자료구조. 선입선출(先入先出) 구조라고도 한다. 자료를 넣는 Enqueue 함수와 자료를 빼내는 Dequeue 함수를 가진다.

밑의 큐는 연결 리스트로 구현된 큐이다. 배열로 하는 경우에는 보통 순환 큐라고 해서 맨 끝과 앞을 연결(나머지 연산자 % 이용)하는 방식으로 구현한다. 소스는 다음과 같다.

void enqueue(int);
int dequeue();

struct linkedList
{
    int value;
    struct linkedList *next;
};
struct linkedList *front; //큐의 맨 앞을 가리킨다.
struct linkedList *back; //큐의 맨 뒤를 가리킨다.

void enqueue(int n) //큐에 자료를 넣는 함수
{
    if(front == NULL) //큐가 비어있을 경우
    {
        *front = {n, NULL}; //맨 앞에 자료를 넣고
        back = front; //맨 뒤와 맨 앞을 같게 한다.
    }
    else
    {
        back -> *next = {n, NULL}; //맨 뒤 다음에 자료를 넣는다.
        back = back -> next; //넣은 자료를 맨 뒤로 한다.
    }
}

int dequeue() //큐에서 자료를 빼는 함수
{
    int res = front -> value;
    front = front -> next;
    return res;
}

데크

간단하게 말하자면 스택과 큐의 융합형태. 양쪽 끝에서 삽입과 삭제가 모두 가능하다. 보통 입력이나 출력 중 하나를 한 쪽 입구만 가능하게 제한하는 형태가 많이 쓰인다.

링크드 리스트

연결 리스트라고도 불린다. 값과 다음 노드를 가지고 있다. 옵션으로 이전 노드를 가지게 할 수도 있으며, 맨 뒤 노드가 맨 앞 노드를 다음 노드로 가지게 할 수도 있다. 가장 간단하게 구현한 것은 위의 큐. 다시 한 번 뜯어보고 옵션을 넣어본다면 실력 향상에 도움이 될 것이다.

비선형 자료구조

선형 자료구조가 아닌 모든 자료구조이다.

그래프

이런 거.

수학, 과학 시간에 많이 보던 그 그래프와는 사뭇 다르다. ~~고등학교 교육과정에서 이산수학이 빠지고 행렬도 빠짐에 따라 같이 빠지게 되는 비운의 단원~~알고리즘을 배우다 보면 자주 나오는 구조. 점들, 그리고 점들을 연결하는 선들로 이루어진 지도 비스무리한 걸 연상하면 편하다. 이때의 점을 정점, 선을 간선이라고 부른다. 간단한 구조체를 만들어 보자.

struct Edge //정점보다는 간선으로 나타내는 편이 대부분의 경우에 더 좋다.
{
    int snode; //시작 정점
    int enode; //종료 정점
    //int cost; //가중치를 가지는 간선에 사용된다.
};

위의 struct Edge가 하나 이상 있는 것이 바로 그래프이다.

그래프 관련 용어

정점(Vertex)
간단하게 말해서, 연결점이다. 좀 더 구체적으로 정의하자면, 여러가지 특성을 가질 수 있는 객체이다. 즉, 어떤 객체도 정점이 될 수 있다.
- 고립 정점
  간선이 단 하나도 연결되지 않은 외톨이봇치 정점이다.
간선(Edge)
두 정점을 연결하는 연결선이다. 구체적으로는, 두 정점간의 관계이다.
- 단방향 간선
  단방향으로만 이동 가능한 간선이다. 이동이 가능한 방향으로 화살표를 그린다.
- 양방향 간선
  양 방향으로 모두 이동이 가능한 간선이다. 양쪽 화살표를 사용해도 되지만, 양방향 그래프에서는 모든 간선이 양방향 간선이므로 화살표 대신 선분으로 표현하기도 한다.
인접
두 정점이 하나의 간선으로 연결되어 있을 때 두 정점이 인접하다고 한다.
차수(Degree)
정점에 연결된 간선의 수이다.
- 진입 차수
  정점으로 들어오는 간선의 수이다.
- 진출 차수
  정점에서 나가는 간선의 수이다.
경로(Path)
어떤 한 정점에서 다른 하나의 정점으로 가는 길이다. 두 정점이 반드시 다를 필요는 없다.
- 길이(Length)
어떤 경로에서 시작 정점에서 도착 정점까지 거쳐야 하는 정점의 수.
- 단순 경로
  경로에서 시작, 끝 정점을 제외한 방문하는 모든 점이 서로 다른 경로.
  - 사이클(Cycle)
    시작 정점과 끝 정점이 같은 단순 경로
    - 재귀 사이클
      간선 하나만으로 이루어진 사이클
부분 그래프(Sub Graph)
그래프를 구성하는 정점들을 임의로 선택한 후 그 정점을 연결했던 간선들로 선택한 정점을 연결한 그래프를 말한다.

그래프의 종류

그래프
일반적인 정의는 객체들 사이의 관계를 점과 선으로 나타낸 그림이다. 그래프는 크게 두 구성요소 정점과 간선으로 이루어져 있다.
- 단순 그래프
  임의의 두 정점 사이에 간선이 최대 하나 있는 그래프
- 다중 그래프
  임의의 두 정점 사이에 여러 개의 간선을 허용하는 그래프
- 의사 그래프
  다중 그래프이면서 사이클을 허용하는 그래프
- 양방향(무향) 그래프
  연결된 두 정점의 순서를 바꾸어도 같은 간선이 되는 그래프, 즉 양방향으로 통행이 가능한 그래프.
- 단방향(유향) 그래프
  일방통행만 가능한 그래프.
- 연결 그래프
  임의의 두 정점 사이에 반드시 경로가 존재하는 그래프.
  - 완전 그래프
    모든 정점이 서로 간선으로 양방향 연결되어 있는 그래프
- 가중치 그래프
  간선에 가중치가 부여된 그래프

그래프 순회 알고리즘

그래프를 순회하는 방법이다. 각 방법마다 장단점이 있으니 상황에 따라 적절한 알고리즘을 선택하는 것이 중요하다.

깊이 우선 탐색

Depth First Search, DFS라고 불리며, 구현하기 쉬운 알고리즘 중 하나이다. 이름 그대로, 방문한 정점으로 부터 깊게 들어가며 쭉 탐색한 후, 되돌아 나오다가 아직 탐색하지 않은 노드를 탐색하는 방식을 사용한다.

알고리즘의 실행과정을 설명하면 다음과 같다.

첫 정점을 방문한다.
인접한 정점 중 아직 방문하지 않은 정점을 방문한다(한 길로 쭉 파고 들어간다).
더 이상 들어갈 길이 없을 때(인접한 모든 정점이 이미 방문한 정점일 때), 방문하지 않은 인접한 정점을 찾을 때까지 들어간 길을 돌아나온다.
위 과정을 반복한다.

너비 우선 탐색

Breadth First Search, BFS라고 불린다. 이름 그대로, 넓게 퍼져가며 정점을 방문한다.

알고리즘의 실행과정은 다음과 같다.

첫 정점을 방문한다.
아직 방문하지 않은 인접한 정점들을 큐에 넣는다.
큐에 있는 정점들을 순서대로 방문한다.
큐에 있는 정점에 대해 인접하면서 아직 방문하지 않은 정점들로 새로운 큐를 구성한다.
위 과정을 반복한다.

트리

파일:Tree Sample.png

그래프의 일종이다. 트리에서의 정점을 특별히 노드라고 하고, 간선을 특별히 가지라고 한다.

코드를 작성해보자.

struct Node;

struct List
{
    struct List *next;
    struct Node *element;
};

struct Node
{
    struct Node *Parent;
    struct List *Sons;
};

자식 노드의 수가 몇 개인지 모르기 때문에, 각 노드의 자식노드 리스트를 단방향 링크드 리스트를 이용해 저장하였다. 위의 struct Node가 하나 이상 있는 것이 트리이다.

트리 관련 용어

노드(Node)
그래프의 정점에 해당하는 것이다.
- 루트 노드
  트리의 기준이 되는 노드이다. 나무의 뿌리를 생각하면 된다. 루트 노드 위에 가지가 뻗어 있다는 이미지.
- 부모 노드
  어떤 노드에서 자신과 인접한 노드들 중 루트 노드로 향하는 노드.
- 자식 노드
  어떤 노드에서 자신과 인접한 노드들 중 루트 노드의 반대 방향으로 향하는 노드.
- 단말 노드
  자식 노드가 존재하지 않는 노드. 가지의 끝이라고 생각하면 된다.
- 형재 노드
  부모 노드가 같은 노드.
가지(Branch)
그래프의 간선에 해당하는 것이다. 트리에서는 양방향 간선만 사용한다.
부트리(Sub Tree)
부분 그래프와 비슷하게 정의한다.
차수(Degree)
자식 노드의 개수.
길이(Length)
임의의 두 노드를 시작 노드, 도착 노드로 하는 경로에서 거치게 되는 노드의 수.
- 깊이(Depth)
  루트 노드에서 해당 노드까지의 길이.
  - 레벨(Level)~~트리도 레벨업을 하나?~~
    깊이가 같은 노드의 집합.
  - 높이(Height)
    가장 깊이가 깊은 단말 노드까지의 길이.

트리의 종류

이진 트리
모든 노드의 차수가 2 이하인 트리.
- 전 이진 트리
  모든 노드의 차수가 0 또는 2인 트리.
- 포화 이진 트리
  모든 단말 노드의 깊이가 같은 이진 트리.
- 완전 이진 트리
  모든 단말 노드의 깊이의 최댓값과 최솟값의 차이가 0 또는 1인 이진 트리.

트리 순회 알고리즘

전위 순회

그래프에서의 깊이 우선 탐색과 같다.

특정 노드를 방문한다.
그 노드의 부트리들을 방문한다.

중위 순회

이진 트리에서만 할 수 있는 순회 알고리즘이다.

후위 순회

레벨 순서 순회

그래프에서의 너비 우선 탐색과 같다.

이진 검색 트리

문자열

기초 정렬 알고리즘

정렬 알고리즘은 크기순, 사전순과 같이 정렬하는 알고리즘을 말한다. 효율적인 알고리즘들 중 대부분은 데이터가 사전에 정렬되어 있을 것을 요구하는 것이 많다.

~~뿅뿅뿅뿅뿅~~ 일단 이걸 보고 뭘 배우면 좋을 지 생각해보자. 참고로 이걸 돌릴 수 있는 프로그램이 동영상에 적힌 웹사이트에 있다. 직접 속도조절을 해보면서 뭐가 빠른지, 어떻게 작동하는지 등등을 유심히 관찰하자. ~~근데 영어다.~~ 참고로 소리를 직접 켜야 들을 수 있다.

영상을 보다보면 마지막의 보고(Bogo) 정렬은 결과를 보여주지 않는걸 보고 의아해 할 수도 있는데, 보고 정렬은 모든 값을 랜덤하게 줄세우는걸 반복하다보면 언젠가는 정렬이 된다는 식으로 동작하는 알고리즘이라서 그렇다(...) 알고리즘의 구성도 랜덤배치->정렬여부 확인의 무한루프. 당연하지만 효율성은 바닥을 긴다. 잘하면 한방에 정렬되지만, 영원히 정렬되지 않을 수도 있다. 기글 하드웨어의 한 유저가 10개의 값으로 테스트하니 결과를 보기까지 4천만번의 읽기작업이 수행되었다고 한다.^[2]~~설마 이런데도 배우고 싶다고는 안하겠지?~~

거품(Bubble) 정렬

세상에서 가장 만만한 정렬(...) 바로 뒤의 원소와 비교해 더 크다면 뒤로 간다. 구현이 쉬운 만큼 성능이 구리다. 알고리즘이 쉬워서 입문용으로 나오는거지 사실 정렬이 되어있든 아니든 대체적으로 느리고 캐시도 못 타고 여러모로 안 좋다. 공부할 목적으로만 쓰고 실제로 정렬을 돌려야한다면 쓰지 말자.

int arr[] = {5, 3, 7, 8, 6, 4, 2, 1, 0, 9};

void sort()
{
    int i, j;
    for(i = 0; i < 10; i++)
        for(j = i; j < 9; j++)
            if(arr[j] > arr[j + 1]) //j번째 원소가 다음 원소보다 크다면 바꾼다.
            {
                int temp;
                temp = arr[j + 1];
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
}

선택(Selection) 정렬

거품정렬하고 살짝 다른 방식의 정렬이다. 구현 방식도 거품정렬하고 비슷하며 시간복잡도도 똑같이 O(n^2)이다. 그러나 한 가지 다른 점은 선택 정렬은 1번째부터 끝까지 훑어서 가장 작은 게 첫번째, 그 다음에 2번째부터 끝까지 훑어서 가장 작은 게 두번째, 그런 식으로 정렬하는 것이다. 역시 거품 정렬과 마찬가지로 공부용으로만 써보자.

int arr[10]={4, 8, 6, 48, 64, 86, -4, -8, -6};

void sort()
{
    int i,j,t;
    for (i=0;i<9;i++)
        for (j=i;j<10;j++) // 이 때 j는 무조건 i보다 크다
            if (arr[i]>arr[j]) { // j번째(뒷) 원소가 i번째(앞) 원소보다 작을 때
                t=arr[i];
                arr[i]=arr[j];
                arr[j]=t;
    }
}

삽입(Insertion) 정렬

시간 복잡도 O(n^2)의 정렬 치고는 괜찮은 정렬이다. 이름 그대로 하나씩 삽입해 나가는 형태의 정렬방식으로, 특정 값에 대해서 그 값이 맞는 위치를 찾고, 나머지는 한칸씩 밀어낸다. 실제로 O(n²) 정렬 알고리즘 중에서는 가장 빠른 형태며, 대부분 정렬 알고리즘이 실행되는 시점이 정렬된 데이터에 새 값을 하나 넣을 때인데, 이 경우 삽입 정렬은 꽤 빠르다. 또, 값이 적은(10개 정도) 상태에서는 캐시도 잘 타기 때문에 여러 정렬 알고리즘에서도 적당히 큰 단위에선 퀵 소트를 쓰고 자잘한 단위에선 삽입 정렬을 쓰는 방식을 사용하기도 한다.

구현방법 1

int arr[10]={4, 8, 6, 48, 64, 86, -4, -8, -6};

void sort()
{
    int i,j,t;
    for (i=1;i<10;i++) {//i번째 값에 대해서
        for (j=i-1;j>=0;j--) {//j를 i의 왼쪽으로 이동시켜가며
            if (arr[j]>arr[j+1]) {//i번째 값이 커질 때까지 이동시킨다
                t=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=t;
            }
            else break;//이동이 끝나면(제자리를 찾으면) 루프에서 나간다
        }
    }
}

다음 단계로

축하한다. 우리는 일단 밑바탕을 배운것이다. 이제 다음 단계로 넘어갈 차례이다. 이제부터 슬슬 긴장해야 한다.

각주

↑ C++ STL의 그것보다 빠를 것이다. 다만 확장이 어려울 뿐.
↑ http://gigglehd.com/zbxe/10760945

틀:쉽게 배우는 프로그래밍 입문

[1] C++ STL의 그것보다 빠를 것이다. 다만 확장이 어려울 뿐.

[2] ttp://gigglehd.com/zbxe/10760945

[1]

[2]