C언어 예술가

그리스 수학자 에라토스네테스가 고안해 낸 소수를 찾는 알고리즘입니다. 다른 알고리즘에 비해서 논리가 상당이 심플하기 때문에 어렵지 않게 접근할 수 있습니다. 우선 소수의 정의는 1과 자기 자신 외에 약수를 가지지 않는 수 입니다. 따라서 1이 아닌 어떤 수를 n(n > 1)배 했을 때 소수가 나올 수는 없습니다. 이것이 이 알고리즘의 핵심입니다. 소수가 아닌 수는 합성수입니다. 1과 자기 자신 이외에 약수를 가지는 수가 합성수죠. 알고리즘을 간단히 설명하겠습니다. 예를들어 2부터 100까지의 수 중에서 소수를 구한다고 해봅시다. 앞서 예기한 것처럼 1이 아닌 어떤 수(여기서는 2부터 100까지의 수를 차례대로)를 2배, 3배, ... 해서 100을 넘기기 전까지의 배수를 구합니다. (아래 그림) 위 그림..

쉘정렬은 지금까지 배운 정렬과 좀 다른 방식으로 생각해 봐야 한다. 쉘 정렬은 다양한 해석이 있는데, 그 이유는 내부에 사용되는 알고리즘으로 삽입정렬을 많이 사용하는데, 버블정렬이나 선택정렬 등도 사용 해도 되기 때문이다. 보통 삽입정렬로 설명하는데, 그 이유는 효율이 좋기 때문에 그렇다. 어떻게 내부에서 선택되는 알고리즘이 다양해 질 수 있는지 알기 위해서 쉘정렬의 구조를 파악해야 하는데 개념 자체는 어렵지 않다. 개인적인 의견으로는 이런 구조로 인해서 쉘정렬이라고 하면 어떤 형식의 알고리즘이 사용되었는지 기술해 주는 정도는 필요하다고 생각한다. 쉘 정렬 위 배열은 14개의 요소를 지닌 배열이다. 쉘정렬은 주어진 자료를 다음과 같은 형식으로 나누어 생각한다.(나누는 방식은 다양할 수 있다. 여기서 나누..

알고리즘 공부는 마치 벽을 넘는 것과 같다. 이해하지 못하면 정말 답답하지만 원리를 알고 나면 고개를 끄덕이게 된다. 물론 이해한다는 것이 구현할 수 있다는 것을 뜻하지는 않지만, 알고리즘 공부에서 가장 중요한 것은 원리를 알고 있느냐는 것이다. 특히 정렬 알고리즘의 구현 과정은 단순하면서도 논리적으로 매우 정밀한 부분들이 복합적으로 조직화 되는 과정이므로 통 암기를 하면 모를까, 이해->구현으로 과는 과정은 오랜 경험이 필요하다. 병합정렬(merge sort) vs 퀵정렬(quick sort) 2014/11/24 - [프로그래밍/알고리즘] - 퀵정렬 알고리즘(Quick sort) 병합정렬은 퀵정렬(quick sort)과 마찬가지로 분할점령의 방법을 쓴다. 분할 점령은 원래의 문제를 같은 형식의 두 개 ..

Big-oh 또는 Big-O notation이라고 한다. 어느 표기법이 정확한지는 모르겠지만, 여기서는 Big-O표기법이라고 하겠다. https://en.wikipedia.org/wiki/Big_O_notation http://web.mit.edu/16.070/www/lecture/big_o.pdf 위 문서나 해외 문서들 또는 번역서들을 보면 Big-oh라고 언급되는 경우는 거의 없었던 것 같다. 반면에 한국의 네이버 검색의 경우 Big-oh라고 사용되는 비중이 높은 듯 싶다. 이런 편중적인 현상은 검색의 힘인가? 아무튼 Big-O 표기법은 알고리즘이 얼마나 효율적인지를 판단하는 대표적인 표기법이다. (전산)수학에서 사용되는 이 표기법은 실제로 프로그래밍을 하는 기법은 아니다. 그러나, 자신이 사용할 자..

다익스트라 알고리즘에 대한 글을 쓴지 2년이 지났네요. 그동안 이 알고리즘을 사용할 일은 없었습니다. 그리고 최근 제가 쓴 글을 다시 보는 순간 나의 글이 너무 나도 허접해 보였습니다. 공부를 해갈수록 "아는 만큼 보인다" 라는 말이 뼈속 깊이 느껴지네요. 그 당시에 제가 쓴 글은 제 머리 속 생각만 쓰기 급급했습니다. 그래서 비록 아직도 한참 모자라지만, 다익스트라 알고리즘의 핵심을 재해석 해보려 합니다. 다익스타라 알고리즘 이 알고리즘의 핵심은 토탈 가중치에 있습니다. 사실 토탈 가중치는 가중치와 같은 의미로도 쓰이지만, 토탈 가중치는 최초 시작점으로 부터의 가중치라는 뜻입니다. 어떤 사람이 A의 위치에 있고 갈 수 있는 경로가 A->B->C->D 라고 하면 각각의 경로는 가중치가 있습니다. 가중치는..

미로찾기 알고리즘의 종류는 여러가지가 있다. 이 글은 그 중에서 가장 기본이 되는 재귀(recursive) 알고리즘에 관한 글이다. 재귀의 특징은 직관적으로 알아보기 쉽다는 이점이 있다. 재귀는 Stack을 사용하기 때문에 깊이가 깊어지면 overflow 에러가 날 가능성이 높아진다. 하지만, 간단한 문제에 대해서는 재귀의 유혹을 뿌리치기 힘들다. 이전에 알아봤던 깊이 우선 탐색은 미로찾기 알고리즘(재귀)의 원형이 된다. 2014/02/26 - [프로그래밍/알고리즘] - 하노이탑 재귀호출 알고리즘 2013/06/05 - [프로그래밍/알고리즘] - 탐색-깊이우선탐색, 너비우선탐색 오래전 포스팅한 내용이라... 예를 들어보면. 위와같은 길이 있다고 하자. 1.어두운 블럭은 벽으로 막혀 있다고 가정하고, 하얀..

마방진의 풀이 여러가지가 있다. 대표적인 풀이방법은 홀수차와 짝수차에 따라 다르고 짝수차는 4의 배수와 아닌 수에 따라 달라진다. 예를들어 3차 마방진은 3x3의 정방행렬형태다. 가장 간단한 형태는 홀수 마방진이고, 짝수차 중 4의 배수가 아닌 마방진 형태가 가장 복잡하다. 여기서는 간단히 홀수 마방진을 푸는 방법과 알고리즘을 c언어로 작성해 보겠다. 마방진의 정의 우리에게 친숙한 김홍도의 작품 씨름이다. 이 그림에는 마방진의 원리가 숨어있다. x자 마방진이라고 하는 이 마방진은 대각선에 늘어선 사람의 합이 12명이 된다. 우리가 흔히 말하는 마방진은 규격은 다음과 같다. N차 마방진의 경우 1부터 NxN까지의 자연수를 NxN칸에 나열 했을 경우 가로와 세로 대각선의 어느 방향으로도 수의 합이 같아야 한..

퀵정렬(Quick Sort) - 찰스 앤터니 리처드 호어(1934~)에 의해서 고안된 정렬로 매우 빠른 정렬입니다. 퀵정렬의 이해는 재귀와 분할정복(divide and conquer)에 대한 이해를 기초로 합니다. 분할정복은 재귀를 푸는 방식인데, 큰 덩어리의 문제를 작은 덩어리로 나누어 해결하는 방식입니다. 작은 덩어리로 나눌 때는 큰 덩어리와 작은 덩어리가 구조적으로 같아야 합니다. 2014/02/26 - [알고리즘] - 하노이탑 재귀호출 알고리즘 본론에 앞서 워밍업을 해봅시다. 위 영상은 퀵정렬의 키가 되는 아이디어를 보여주지만, 너무 자세히 보진 마시기 바랍니다. 제가 설명하는 방법과는 약간의 차이가 있기 때문입니다. 위 방법으로 가능하겠지만, 비효율적인 듯 보여지네요.. 아무튼.,,위 영상에서 ..

삽입정렬(insertion sort) - 삽입정렬 알고리즘을 설명하기 전 자료를 정렬된 목록과 정렬되지 않은 목록으로 자료를 나눌 필요가 있습니다. 삽입정렬은 배열의 경우 처음 첫 번째 요소를 정렬된 목록으로 간주한 후 루프를 시작합니다. 정렬되지 않은 목록의 제일 첫 번째 요소부터 정렬된 목록과 비교하여 적절한? 위치에 삽입해 나갑니다. 정렬되지 않은 목록 끝까지 위 작업을 반복하면 모든 요소가 정렬된 부분으로 바뀌게 됩니다. 삽입정렬 알고리즘의 아이디어도 어렵지는 않지만 삽입되는 과정을 차근차근 분석할 필요가 있습니다. 위 영상은 이해는 되지만 위 영상만 보고 코드로 작성하려면 먼가 부족하거나 헷갈릴 수가 있습니다. 삽입정렬에 대한 아이디어는 알려주지만, 알고리즘의 세세한 부분이 정확하지 않다는 것을..

선택정렬(selection sort) - 선택정렬은 일반적으로 사람이 어떤 것을 크기 순서대로 정렬할 때 사용하는 방법과 유사한 방법입니다. 나열된 것 중에 가장 작은 또는 가장 큰 것을 선택하여 앞 또는 끝으로 보내는 작업을 반복하면 최종적으로 크기 순서대로 정렬이 되는 방식입니다. 다음 영상은 선택정렬에 대한 이해를 도와줍니다. 사람이 정렬을 할 경우 비슷한 과정을 거치지만 일반적인 사람의 경우 직관에 따라 몇몇 숫자의 위치를 정하고 그를 기준으로 수를 정렬하기 때문에 컴퓨터 입장에서 정렬하는 법을 위 영상을 보며 생각해볼 필요가 있습니다. 다음 그림은 선택정렬을 간략화한 그림입니다. 컴퓨터 입장에서 알고리즘이 실행될 때 두 수를 교환하는 과정 전에 더 많은 비교가 있습니다. 위 그림은 직관적으로 알..