프로그래밍을 통해 문제를 해결할 때에는, for문, while문 등의 기본적인 함수들만을 이용해 프로그램을 작성할 때도 있고, 동적 계획법 등의 알고리즘을 이용해 프로그램을 작성할 때도 있다. 기본적인 문제를 해결하기 위한 프로그램을 작성할 때에는 주로 배열을 이용하지만, 배열 이외의 다른 자료 구조를 사용하면 더 쉽게 해결할 수 있는 문제들도 있다. 이 글에서는, 여러 가지 자료 구조의 종류와 이런 자료 구조들을 이용해 문제를 해결하는 방법에 대해 논의해 보겠다.
먼저, 리스트가 있다. 리스트에는 첫 번째 수에 해당하는 Head 값이 있고, 리스트를 구성하는 각각의 수에는 그 수의 값과 다음 수를 가리키는 포인터가 저장되어 있다. 따라서, 구조체를 이용하여 구현하는 것이 편리하다. 예를 들어, Next가 다음 수를 가리키는 포인터라고 하고, 첫 번째 수를 나타내는 변수를 Head라고 하면, Head->Next는 두 번째 수를 나타낸다. 그러면, 리스트와 배열(배열의 이름을 a라 하자.)에 각각 수들이 저장되어 있고, 10번째 수를 출력하는 문제를 생각해 보자. 만약 수들을 배열에 저장했다면 a[9]를 출력하면 된다.(C++ 언어로 프로그래밍을 할 경우 a[0]에 첫 번째 수를 저장하는 것이 보통이다.) 하지만, 리스트에 수를 저장한 경우, 변수 Temp에 Head 값을 저장한 후, Temp = Temp -> Next 명령문을 10번 반복해서 수행해야 10번째 수를 찾을 수 있다. 즉, 리스트에 수를 저장한 경우, 배열에 수를 저장한 경우에 비해 프로그램 실행 속도가 느릴 것이다. 그러면 리스트를 사용하는 이유가 무엇일까? 그 이유는, 리스트는 크기가 정해져 있지 않기 때문이다. 배열의 경우, 처음에 int a[1000]; 처럼 선언을 하는데, 이 때, 배열에 입력될 수 있는 수의 최대 개수는 1000개로 제한된다. 하지만, 리스트의 경우, 새로운 수가 입력될 때, 마지막 수의 Next 포인터에 새롭게 입력되는 수를 저장하면 되기 때문에, 몇 개의 수가 입력될 수 있는지 몰라도 된다. 즉, 리스트는 입력될 수 있는 수의 최대 개수가 얼마인지 모를 때 사용하면 효과적인 자료구조이다.
또한, 스택(stack)이 있다. 스택은, 간단히 말해서 수들을 벽돌처럼 쌓아 정리한 구조이다. 스택을 구현할 때에는, 수들을 저장할 배열(배열 이름을 a라 하자.)과 top 변수가 필요하다. 먼저, top의 값은 처음에 0으로 초기화시켜야 한다. 이 때, 변수 top에는 스택에 저장되어 있는 수들 중 가장 위에 있는 원소 다음의 index 번호가 저장되어 있다. 예를 들어, a[0]부터 a[3]까지 수가 저장되어 있는 상황에서는 top=4이어야 한다. 스택을 이용해 문제를 해결할 때 보통 사용하는 연산에는 push(새로운 수를 입력하는 연산), pop(가장 위에 있는 수를 빼는 연산), 스택이 비어있는지 확인하는 연산이 있다. 먼저, push 연산을 할 때에는, a[top++]=n 명령문을 실행시키면 된다. 즉, 현재 top 값에 새로운 수를 입력한 후, top을 1 증가시키면 되는 것이다. pop 연산을 할 때에는 top을 1 감소시키면 된다. 마지막으로, 스택이 비어있는지 확인하는 연산은 top 값이 0인지 확인해 보면 된다. top 값이 0이면 스택이 비어 있는 것이고, 0이 아니면 스택에 1개 이상의 수가 입력되어 있는 것이다.
지금까지 프로그램 작성에 활용할 수 있는 다양한 자료 구조들과, 자료 구조들을 문제 해결에 활용하는 방법에 대해 논의해 보았다. 이 글에서 설명한 자료 구조 외에 트리(Tree) 등 다른 자료 구조들도 있는데, 이런 자료 구조들을 구현하는 방법을 충분히 익히고, 문제를 해결할 때 어떤 자료 구조를 활용해야 효과적으로 문제를 해결할 수 있을지 충분히 고민을 한다면, 문제를 해결할 수 있는 효율적인 알고리즘을 찾을 수 있을 것이다.
HOME > 
