연재 차례
1. C언어 소개
2. 형태, 연산자, 표현
3. 제어 흐름
4. 함수와 프로그램 구조
5. 포인터와 배열
6. 구조체
7. 알고리즘 소개
8. 소팅을 통한 알고리즘 분석
9. 스택(Stack) 실습
10. 큐(Queue) 실습
11. 리스트(List) 실습
12. 트리(Tree) 실습
13. 해싱(Hash) 실습
14. 알고리즘 설계 및 분석기법
15. 진보된 알고리즘 소개
알 고리즘(Algorithms)은 잘 정의된 계산적인 절차이며 효율적인 절차를 통하여 입력 값들에서 출력 값들을 산출하는 방법이다. 또한 알고리즘은 입력을 출력으로 변환하는 일련의 계산단위를 기술하는 순서이며 잘 지정된 계산적인 문제를 해결하는 도구라는 관점으로 해석할 수도 있다. 계산적인 문제들은 입력과 출력간의 관계를 제시하고 알고리즘은 이렇게 제시된 입출력간의 관계를 계산적인 절차로 해석하여 적절한 해답을 산출한다.
예를 들어, 입력된 숫자들을 크기 순서대로 정렬하는 문제가 있다고 할 때, 이러한 정렬 문제의 입력과 출력간의 관계를 다음과 같이 기술할 수 있다.
입력 : 숫자 n개가 a1, a2, a3, ..., an 으로 나열됨.
출력 : 숫자 n개가 b1 <= b2 <= b3 ... <= bn 인 관계로 정렬됨.
입력 (n = 8개) : 31, 41, 59, 26, 15, 41, 12, 58
출력 (n = 8개) : 12, 15, 26, 31, 41, 41, 58, 59
정 렬은 컴퓨팅 분야에서 기본적인 필수 동작이며 많은 프로그램에서 정렬을 사용한다. 그동안 훌륭한 정렬 알고리즘들이 개발되어왔으며, 정렬 알고리즘의 효율성 평가는 정렬하고자 하는 대상의 개수와 분포에 따라 달라진다. 또한 메모리나 디스크와 같은 저장 장치의 종류에 의존한다.
각각의 입력에 대해서 올바른 출력 결과가 나온다면 해당 알고리즘은 정확하다고 말할 수 있다. 알고리즘은 영어로 표현할 수도 있고, 컴퓨터 프로그램 혹은 하드웨어 설계로도 기술할 수 있지만, 무엇보다 명확한 기술적인 절차를 통하여 주어진 문제를 해결하도록 표현하는 것이 중요하다.
필자는 C언어 프로그램을 통하여 알고리즘을 표현한다. 또한 데이터 구조(Data Structure)에 대해서도 실습하도록 내용을 구성한다. 데이터 구조는 데이터를 저장소에 보관(구성)하는 방식이며 이것에 접근하는 방법(입력, 수정, 삭제)은 알고리즘으로 기술하므로 데이터 구조와 알고리즘은 서로 밀접하게 연관되어 있다. 앞으로 C언어 코드를 통하여 이들을 상세히 실습해 보도록 하자.
다양한 알고리즘들을 실습하기 전에 선행 학습해야 하는 몇 가지 중요한 C언어 코딩기법들이 있는데, 반복(Loop), 재귀(Recursion), 포인터(Pointer)이다. 이들은 알고리즘을 C언어로 코딩 할 때 필수적으로 등장하는 것이므로 선행학습 하는 것이 필요하다.
반복(Loop)
C언어에서 반복을 수행하는 제어문으로 for, while, do가 있다. 이들은 모두 반복을 수행하기 위한 제어변수를 가지고 있으며 제어변수의 초기값, 증감, 종료 판단에 따라 반복회수가 결정된다.
알고리즘에서 반복이 수행되는 회수는 중요한 수치이며, 알고리즘의 수행시간은 반복 회수에 비례하므로 반복 회수를 줄이면 알고리즘의 효율성은 증가한다. 먼저 for문으로 작성된 다음의 C언어 코드를 보자.
그럼,오른쪽의 C언어 코드를 보자.
다음으로, 아래의 C언어 코드를 보자.
다음으로, 아래의 C언어 코드를 보자.
재귀(Recursion)
재귀(Recursion)도 반복 실행되는 것이다. for문과 같은 루프는 for문 하단에 지정된 블록 안의 명령문을 반복 수행하는 것에 비해서, 재귀는 호출한 함수 내부의 전체 코드를 또 다시 수행한다. 재귀는 호출 조건을 만족하면 해당 함수를 계속 호출한다.
함수를 재호출 할 때마다 이 함수에서 사용되는 내부 변수들은 메모리(스택)에 순서대로 적재되고, 호출한 함수로 다시 복귀하는 주소 또한 관리된다. 재귀는 함수 내부변수들과 복귀주소를 추가적인 메모리로 관리해야 하는 부담이 있지만(이것은 컴파일러가 생성한 내부 코드에서 처리됨), 해당 함수의 코드들을 재사용할 수 있어서 프로그램 코드가 함축적으로 짧아지는 장점이 있으므로 알고리즘에서 많이 사용한다.
또한, 알고리즘상 동일한 논리를 반복적으로 수행하는 것이 많으므로 재귀를 이해하는 것은 중요하다. 다음의 C언어 코드를 통하여 함수의 재귀호출 실행을 이해해보자.
그럼, 아래의 C언어 코드를 보자.
다음으로, 아래의 C언어 코드를 보자.
지금까지 알아본 반복과 재귀함수의 반복회수를 테이블로 정리하면 다음과 같다.
알고리즘에서 재귀호출은 코드의 함축성을 높여서 코드길이를 짧게 해줄 수 있으나 재귀호출의 회수(호출 깊이)가 커지면 알고리즘의 실행 시간(비용)이 기하급수적으로 증가한다. 재귀호출의 이러한 양면성 때문에 이것의 특징을 잘 살려서 활용하는 것은 무엇보다 중요하다.
다음의 그래프는 입력 자료수 n과 알고리즘 효율성(실행시간)간의 상관관계를 표현한 것이다.
컴 퓨터 메모리는 일련번호가 매겨진 주소로 관리된다. 메모리에 접근하기 위해서 이러한 주소를 사용하는데, 포인터는 메모리 주소를 보관하고 있는 변수이다. 따라서, C언어는 포인터 변수에 보관되어 있는 주소를 통하여 메모리에 접근하며 메모리에 있는 데이터들을 효율적으로 관리하기 위해서는 적절한 포인터 변수를 사용해야 한다.
C언어는 변수, 함수, 구조체와 같은 자료들을 포인터에 담아서 관리할 수 있다. 특히, 함수는 전역적인 자료형의 일종으로 포인터를 통하여 변수처럼 전달 및 호출할 수 있다. 이러한 특징을 활용하면 프로그램 코드를 좀더 효율적으로 작성할 수 있다.
다음의 C언어 코드를 통하여 함수 포인터를 실습해보자.
맺음말
필자는 이번 연재에서 C언어로 알고리즘을 이해하기 위해서 필수적으로 선행 학습해야 하는 반복(Loop), 재귀(Recursion), 포인터(Pointer)에 대해서 기술했다. 이것들은 알고리즘을 효율적으로 코딩 하기 위해서 필요한 핵심 요소들 이므로 잘 익혀 두도록 하자. 다음 연재부터 알고리즘들이 본격적으로 기술되니 독자 여러분들의 꾸준한 관심 있기를 바란다.
필 / 자 / 소 / 개
※ 본 내용은 (주)테크월드(http://www.embeddedworld.co.kr)의 저작권 동의에 의해 공유되고 있습니다.
Copyright ⓒ Techworld, Inc. 무단전재 및 재배포 금지
번호 | 제목 | 작성 | 조회수 |
---|---|---|---|
15 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ② (15) | 2012-08-17 | 2063 |
14 | [C언어와 알고리즘] 진보된 알고리즘 소개- 인공지능 ① (14) | 2012-08-17 | 2323 |
13 | [C언어와 알고리즘] 해싱(Hash) 실습 (13) | 2012-08-17 | 2930 |
12 | [C언어와 알고리즘] 트리(Tree) 실습 (12) | 2012-08-17 | 3996 |
11 | [C언어와 알고리즘] 리스트(List) 실습 (11) | 2012-08-17 | 5621 |
10 | [C언어와 알고리즘] 큐(Queue) 실습 (10) | 2012-08-17 | 4878 |
9 | [C언어와 알고리즘] 스택(Stack) 실습 (9) | 2012-08-17 | 4081 |
8 | [C언어와 알고리즘] 소팅을 통한 알고리즘 분석 (8) | 2012-08-17 | 2468 |
7 | [C언어와 알고리즘] 알고리즘 소개 (7) | 2012-08-17 | 2117 |
6 | [C언어와 알고리즘] 구조체 (6) | 2012-08-17 | 3969 |
0개 댓글