알고리즘 사실 알고리즘이라고 표현할만한 대단한 알고리즘이 있는 것이 아니다. 누구나 알고 있는 그 룰, 바위는 가위를 이기고, 보는 바위를 이기며, 가위는 보를 이긴다는 것만 기억하면 된다. 가위바위보를 짜기 위한 가장 기본적인 아이디어는, 이런 관계를 숫자로 나타내보자는 데에서 출발한다. '바위는 가위를 이긴다' 라는 명제를 숫자로 가장 간단히 표현해보자면, 바위를 1이라는 숫자로, 가위를 0이라는 숫자로 바꿔 놓으면 되는 것이다. 즉, A가 바위를 냈다면 A = 1, B가 가위를 냈다면 B = 0 이라고 놓으면 단지 A와 B의 숫자 크기를 비교하는 것으로 누가 이겼는지 판단이 가능하다. 그렇다면 보는 바위보다 상위에 있으므로 2라는 숫자로 대체할 수 있다. 문제는 다시 가위는 보의 상위에 있다는 것이..

알고리즘 (x - r)^2 + (y - r)^2 = r^2 알고리즘은 간단하다. 위와 같은 원의 공식을 사용한다. 원의 모양을 예측해 보면 (r, r)의 중심점을 가지는 반지름이 r인 원이 그려진다. 이 포스트에서는 반지름 이내의 범위의 어떤 좌표 (x, y)에 있는 점은 검은색 상자 (■)로 표시하고, 그렇지 않은 점은 빈 상자(□)로 표시할 생각이다. 간단히 생각해 보면 이중 반복문을 돌려서 삼항연산자든 if문이든 걸어서 범위 체크만 해주면 끝이라고 생각 할 수 있다. 하지만 실제로 그를 토대로 그려보면, 뭔가 좌우 대칭이 잘 맞지 않는다. 접근 방법 텍스트만 가지고 원을 그리려면, 픽셀 단위의 드로잉을 생각해야만 한다. 어떤 도장이 있다. 도장은 가로세로 1cm의 크기를 갖는 정사각형 모양을 찍어낸..

알고리즘 퀵 정렬의 기본 아이디어는, 기준이 되는 숫자를 정해서 그것보다 큰 원소들과 작은 원소들로 편을 갈라놓고 정렬하자는 것이다. 이 아이디어를 따라가기 위해서는 기준이 되는 숫자를 어떻게 정할 것인가, 그리고 큰 원소들과 작은 원소들을 어떻게 분리해 둘 것인가 하는 것이 주요 목표가 될 것이다. 백마디 설명 보다는 역시 예제를 하나 꺼내는 것이 좀 더 설명하기 쉬울 것 같다. 45, 39, 98, 15, 52, 44, 33, 28, 40, 38, 77, 68, 11, 43 기준이 되는 숫자를 Pivot 이라고 부르는데, 맨 앞에 있는 숫자를 Pivot으로 삼을수도 있고, 정 가운데 있는 숫자를 Pivot으로 삼을 수도 있다. 사실 어떤 숫자를 Pivot으로 하든 상관이 없다. 이 예제에서는 임의로 ..

알고리즘 Array를 반씩 쪼갠다. 한번 쪼개면 두개의 큰 덩어리가 나올 것이다. 이렇게 나온 덩어리를 또 다시 쪼갠다. 이렇게 덩어리를 계속 쪼개다 보면, 결국 한 개의 원소가 하나의 덩어리가 된다. 이 상태에서 다시 덩어리를 뭉치는데, 그냥 뭉치는 것이 아니라 각각의 원소를 비교해 가면서 원소를 차례로 배열한다. 이런 식으로 덩어리를 계속 뭉쳐가다 보면 원래의 Array가 정렬된다. 이것이 합병 정렬의 기본 아이디어다. 코드 #include #define LEN 9 void merge_sort(int num[],int start, int end); void merge(int num[], int start, int mid, int end); void tracer(int num[],int len); in..

알고리즘 쉘 정렬은 삽입 정렬의 단점을 보완하기 위해서 Donald Shell이 1958년 고안한 방법이다. 삽입 정렬은 Array 전체에 대해서 정렬을 수행하게 된다. 최악의 경우, 다시말해서 오름차순 정렬을 해야하는데, Array가 내림차순 정렬이 되어있는 경우 연산이 많아지게 될 수 밖에 없다. 쉘 정렬의 기본적인 아이디어는 삽입 정렬을 하기 전에 정리를 해놓자는 것이다. 그렇다면, 어떻게 정리할 것인가? 삽입 정렬은 모든 원소에 대해서 검사를 하지만, 쉘 정렬의 경우, 앞에서 구한 어떠한 간격만큼 떨어진 원소에 대해서 삽입정렬을 먼저 수행하고, 그 간격을 점점 줄여 계속 삽입정렬을 하는 방법을 취한다. 간격은 결국 1이 될 것이며, 1이 되는 때는 곧, 삽입 정렬을 수행하는 것과 동일하다. 하지만..

알고리즘 사실 최적화라고 하기 민망할 정도로 버블정렬과 큰 차이가 없으며 실제 코드상으로도 단 2글자만 추가되었을 뿐이다. 최적화된 버블 정렬의 주된 아이디어는, 맨 마지막 원소는 이미 정렬 되어있어서 또 검사해줄 필요가 없다는 것이다. 즉, 버블 정렬의 첫번째 패스를 눈여겨 살펴보면, 가장 큰 값이 항상 맨 끝으로 이동된다. 어찌보면 당연한 결과라고 할 수 있다. 가장 큰 값은 if문에 발각되어 계속 Swap 되기 때문에, 맨 뒤까지 질질 끌려간다. 결론적으로, 두번째 패스에서는 마지막 원소를 검사해줄 필요가 없다. 세번째 패스에서는 마지막 원소와 마지막에서 두번째 원소 역시 검사해줄 필요가 없다. 마지막 패스에서는 두번째 원소와 첫번째 원소만 검사해주면 된다. 코드 #include void op_bu..