🌟CS:: 알고리즘 및 자료구조 (초딩 수준) 기초

자료구조 資料構造 / data structure

요약) 컴퓨터에서 자료를 효율적으로 관리하고 구조화시키는 방법.

 

의미)

 프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론, 혹은 과목.  컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미. 더 정확히 말해, 자료 구조는 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미한다. 신중히 선택한 자료구조는 보다 효율적인 알고리즘을 사용할 수 있게 한다. 이러한 자료구조의 선택문제는 대개 추상 자료형의 선택으로부터 시작하는 경우가 많다. 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.

 

 대부분의 컴퓨터 프로그램은 알고리즘 + 자료구조의 형태로 이루어진다. 알고리즘이 특정한 목적을 달성하기 위한 절차라고 한다면 자료구조는 알고리즘에 필요한 데이터의 집합이다. 다양한 프로그램을 설계할 때, 어떠한 자료구조를 선택할지는 가장 우선적으로 고려되어야 한다. 이는 큰 시스템을 제작할 때 구현의 난이도나 최종 결과물의 성능이 자료구조에 크게 의존한다는 것을 많은 경험이 뒷받침하기 때문이다. 일단 자료구조가 선택되면 적용할 알고리즘은 상대적으로 명확해지기 마련이다. 동일한 알고리즘이라도 자료구조가 달라지면 전혀 다른 프로그램이 될 수 있기 때문에 자료에 알맞은 자료구조를 만드는 것이 매우 중요하다. 때로는 반대 순서로 정해지기도 하는데, 이는 목표로 하는 연산이 특정한 알고리즘을 반드시 필요로 하며, 해당 알고리즘은 특정 자료구조에서 가장 나은 성능을 발휘할 때와 같은 경우이다. 어떠한 경우든, 적절한 자료구조의 선택은 필수적이다.

 

 컴퓨터의 메모리는 1차원 구조이기 때문에[1] 현실 세계의 다차원 데이터를 다루기 위해서는 이것을 1차원인 선 형태로 바꾸는 것이 필요하다. 대학교 1학년 과정에서 배우는 기초 알고리즘들은 바로 이 방법을 학습한다. 2차원 배열, 이진 트리, 그래프 등의 자료구조가 2차원 데이터를 1차원으로 욱여넣는 방법을 배우는 것이다. 더 나아가 3차원 데이터를 다루고, 더 지나면 3차원 데이터 이상의 다차원 데이터를 처리하는 자료구조를 만날 수 있다. 컴퓨터과학에서 알고리즘과 함께 가장 중요한 기초이론이다. 이것을 공부하지 않고 상위 과목을 공부하는 건 사실상 불가능하다. 영어로 치면 알파벳을 모르는 상태로 독해를 공부하겠다는 것과 마찬가지로 볼 만큼 프로그래밍에서 중요한 부분이다.

 

 리스트, 스택, 큐, 환형 큐, 힙, 트리, 그래프 7가지 개념을 숙지하면 자료구조 대부분 이해한 것이라 보면 된다.

 

 

분류)

 자료의 특성과 크기, 주요 사용법과 수행하는 연산의 종류, 구현에 필요한 기억 공간 크기에 따라 여러 가지 종류의 자료구조 중 하나를 선택할 수 있다. 자료구조의 종류로는 자료형의 따라 분류하는 단순 구조와 자료 간 관계가 1 대 1인 선형 구조, 1 대 다 혹은 다 대 다 구조인 비선형 구조, 마지막으로 파일 구조가 있다.

단순구조는 정수, 실수, 문자, 문자열 등 자료의 형태를 말한다. 선형 구조는 자료 간의 연결 관계가 [1:1] 관계를 가지는 형태로 자료들이 기다란 선처럼 연결되어 있는 구조이다(예를 들어, 엑셀로 각 과목 점수를 정리하는 표를 만들 때 사용하는 자료구조는 선형구조 중에서 '리스트'라는 구조. 리스트는 순서가 정해져있는 목록의 자료구조임.) 비선형구조는 자료 간의 연결 관계가 [하나 : 여러 개] 또는 [여러 개 : 여러 개] 의 관계를 가지는 형태로, 나뭇가지 모양이나 그물 모양처럼 얽혀 있는 구조이다(지하철 노선도를 정리할 때 사용하는 자료구조는 비선형 구조의 '그래프'라는 구조. 다양하고 복잡한 연결 구조들을 표현할 때 사용.)

 

구현에 따라

• 배열 - 가장 일반적인 구조이다. 메모리 상에 같은 타입의 자료가 연속적으로 저장된다. 자료값을 나타내는 가장 작은 단위가 자료를 다루는 단위이다.
• 튜플 - 둘 이상의 자료형을 묶음으로 다루는 구조이다.
• 연결 리스트 - 노드를 단위로 한다. 노드는 자료와 다음 노드를 가리키는 참조값으로 구성되어 있다. 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝이다.
• 원형 연결 리스트 - 각 노드는 다음 노드를 가리키고, 마지막 노드가 처음 노드를 가리키는 연결 리스트이다.
• 이중 연결 리스트 - 각 노드는 이전 노드와 다음 노드를 가리키는 참조값으로 구성된다. 처음 노드의 이전 노드와 마지막 노드의 다음 노드는 없다.
• 환형 이중 연결 리스트 - 처음 노드가 이전 노드로 마지막 노드를 가리키고, 마지막 노드가 다음 노드로 처음 노드를 가리키는 이중 연결 리스트이다.
• 해시 테이블 - 개체가 해시값에 따라 인덱싱된다.

 

형태에 따라

선형 구조

• 스택 - 스택 자료구조에 먼저 저장된 것이 꺼내어 쓸 때는 제일 나중에 나온다. 반대로, 가장 최근에 저장된 것이 꺼내어 쓸 때는 제일 먼저 나온다. 만약, 자료들의 나열 순서를 바꾸고 싶다면 스택에 집어 넣었다가 꺼내면 역순으로 바뀐다.
• 큐 - 스택과 반대로 큐 자료구조에 먼저 저장된 것이 제일 먼저 나온다. 반대로, 가장 나중에 저장된 것이 꺼내어 쓸 때는 가장 나중에 나온다.
  • 환형 큐 - 한정된 길이 안에서 부수적인 작업 없이 읽고 쓰기를 할 수 있는 큐이다.
• 덱 - 양쪽에서 넣기와 빼기를 할 수 있는 일반화된 선형 구조이다.

 

비선형 구조

• 그래프 - 꼭짓점과 꼭짓점을 잇는 변으로 구성된다.
  • 유향 그래프, 무향 그래프 - 변이 방향성을 갖는지 갖지 않는지에 따른 그래프의 분류이다.무향 그래프의 경우, 순환이 없는 연결 그래프를 뜻한다. 유향 그래프의 경우 변의 방향은 보통 부모를 가리키도록 구현된다.
• 트리 - 뿌리와, 뿌리 또는 다른 꼭짓점을 단 하나의 부모로 갖는 꼭짓점들로 이루어진 구조. 부모 자식 관계는 변으로 표현된다.
  • * 이진 트리 - 자식이 최대 두 개인 트리.
  • 힙 - 이진트리의 일종으로 이진트리에 어떤 특성을 부여한 것이라 할 수 있다.

---

알고리즘 Algorithm

요약) 어떤 문제를 해결하기 위한 절차, 방법, 명령어들의 집합

의미)

 알고리즘(algorithm)은 주어진 문제를 논리적으로 해결하기 위해 필요한 절차, 방법, 명령어들을 모아놓은 것. 넓게는 사람 손으로 해결하는 것, 컴퓨터로 해결하는 것, 수학적인 것, 비수학적인 것을 모두 포함. 

 

 e.g.) 명희가 이렇게 물음. "이번주 학원 숙제 다 했어?" 이에 영희는 "응. 다 했어."라고 대답. 명희가 한 문장으로 간단하게 물어봤지만 영희는 그 말속에 '수학 문제 풀어오기, 국어 글짓기, 영어 단어 외워오기'가 포함되어 있음을 알고 있음. 이처럼 사람은 그 말속에 포함되어 있는 의미까지 이해할 수 있음. 하지만 컴퓨터는 그렇지 못함... 정확하게 무엇을 해야 할지 처리 내용과, 처리 순서를 모두 구체적으로 알려 주어야만 제대로 명령을 수행. 그렇기 때문에 프로그램에 알고리즘이 필요.

 이 명령을 수행한 다음에는 무슨 일을 처리하고, 그 다음에는 어떤 파일들을 모아서 어떻게 처리해야 할지, 구체적으로 명령의 내용과 순서, 처리 방법을 모아놓은 것. 알고리즘은 어떻게 구성하는가에 따라 같은 문제를 풀더라도 오래 걸릴 수도 있고, 오류가 생길 수도 있으므로 효율적이고, 명확하게 만드는 것이 중요.

 프로그램을 만드는 전체 과정에서 볼 때, 알고리즘을 짜는 것은 [계획]단계라고 할 수 있습니다. 프로그램이 어떻게 행동할지를 결정해 주는 이 계획이 완성되면(알고리즘 계획) 그것을 프로그램 언어로 작성하여 소프트웨어를 완성하는 것.

 

 대부분의 알고리즘은 유한한 수의 규칙에 따라 구별 가능한 기호들을 조작하여 입력 정수에서 출력 정수를 생성하기 위한 일반화된 작업을 정의한다. 다음은 좋은 알고리즘의 특징.

• 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다.
• 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다.
• 타당성 : 구현할 수 있고 실용적이어야 한다.
• 입력 : 정의된 입력을 받아들일 수 있어야 한다.
• 출력 : 답으로 출력을 내보낼 수 있어야 한다.
• 유한성 : 특정 수의 작업 이후에 정지해야 한다.
• 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다.

 

분류)

• 구현 : 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등.
• 설계 : 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한정법, 확률적 알고리즘, 리덕션, 백트래킹 등.
• 최적화 문제 : 선형 계획법, 동적 계획법, 탐욕 알고리즘, 휴리스틱 함수 등.
• 이론적 분야 : 검색 알고리즘, 정렬 알고리즘, 수치 알고리즘, 그래프 알고리즘, 문자열 알고리즘, 암호학적 알고리즘, 기계 학습, 데이터 압축 등.

 

시간 복잡도 Time Complexity) 

 알고리즘의 소요 시간을 정확히 평가할 수는 없으므로, 자료의 수 n이 증가할 때 시간이 증가하는 대략적인 패턴을 시간 복잡도라는 이름으로 나타내게 된다.[8] 이를 Big-O 표기법(Big O notation)으로 주로 나타낸다. 예를 들어 입력 자료의 크기 nn에 대하여 \mathcal{O}(n)O(n)의 시간복잡도를 가진 알고리즘은 대략 크기 n에 비례하는 수의 연산을 수행한다고 보면 된다.

 알고리즘의 종류에 따라 시간 복잡도의 평가기준도 다양하다. 일반적으로는 \mathcal{O}(n)O(n)의 시간 복잡도를 가지면 좋은 알고리즘으로 취급하며[9][10], \log nlogn의 지수승이 붙는 정도로 막으면(\mathcal{O}(n \log n)O(nlogn)) 등) 매우 바람직한 결과이다. \mathcal{O}(n^3)O(n3) 정도만 돼도 큰 자료수에선 급격히 느려진다.

 검색 알고리즘의 경우 \mathcal{O}(1)O(1)이나 \mathcal{O}(\log n)O(logn)의 시간 복잡도를 가지는 알고리즘을 선호하고, 정렬 알고리즘의 경우 \mathcal{O}(n \log n)O(nlogn)의 시간 복잡도를 가지는 알고리즘을 선호한다. 여기에 각각 해당되는 자료구조/알고리즘에는 해시 테이블과 퀵 정렬 등이 있다.

 이런 식으로 시간 복잡도가 n의 다항식 이하가 되는 알고리즘들을 다항 시간 알고리즘(polynomial time algorithm)이라고 한다. 여기까지만 보면 다항식과는 넘사벽[11]의 증가속도를 자랑하는 \mathcal{O}(2^n)O(2n) 또는 \mathcal{O}(n!)O(n!) 같은 알고리즘은 매우 막장인 것처럼 보이지만, 세상에는 이런 알고리즘밖에 방법이 없는 어려운 문제들이 수두룩하다. 이런 경우에는 정답을 포기하고 근사해를 구해주는 알고리즘을 찾게 된다. 더 자세한 이야기는 P-NP 문제 참고.

 

 

 

공간 복잡도 Space Complexity)

 공간 복잡도 역시 앞서 언급한 시간 복잡도처럼 Big-O 표기법(Big O notation)을 주로 사용한다. 현실에서는 시간 복잡도보다 중요도는 떨어지는데, 시간이 적으면서 메모리까지 지수적으로 증가하는 경우는 없기 때문이고, 다항 시간 내에서 나타나는 메모리 문제들은 보통 알고리즘 자체보다는 알고리즘의 구현에서 발생하는 문제이기 때문이다.

 다만 동적 계획법의 경우에는 메모리가 상당히 많이 필요하기 때문에 (즉, 공간복잡도가 크기 때문에) 입력 값의 범위가 넓으면 사용하지 못하는 경우가 많다. 또한 임베디드, 펌웨어 등 하드웨어 환경이 극도로 한정되어 있을 경우 공간 복잡도도 상당히 중요하게 보게된다. 이론적으로는 n에 대한 다항식만큼의 공간으로도 해결이 안 되는 정말 어려운 문제들[12]을 생각하기도 한다.