알고리즘- 정보과학의 문제

• 정보과학의 문제는 다음과 같은 문제들을 다룬다.

1. 결정문제    2. 탐색문제     3. 카운팅문제    4.최적화문제    5.함수형문제

• 결정문제(decision problem)

결정문제는 예(yes) 또는 아니오(No) 중 하나의 답을 얻는 문제를 말한다. 

예를 들어 "폐구간 [a,b]에서 소수는 존재하는가? "

  "N개의 원소로 이루어진 집합의 부분집합들 중 그 원소의 합이 K인 부분집합이 존재하는가?"

위의 두 가지 질문이 결정문제의 예라고 할 수 있다. 

• 최적화문제(optimization problem)

계산결과로 얻어낸 가능한 후보해들 중에서 가장 좋은 해를 찾는 문제를 의미한다. 

예를 들어 "N개의 원소를 가지는 집합 S의 원소를 오름차순으로 나열하고, 그 최댓값을 구하시오. "

  "좌표평면상에 N개의 점 중 한점에서 출발하여 모든 점을 지나고 출발점으로 돌아오는 경로의 길이가 가장 짧은 길이는 얼마인 가?"

위의 두 가지 질문이 최적화 문제에 해당된다 

• 다음으로 탐색

한개 이상의 자료들이 구조화된 형태로 모여잇는 집합에서 특정 자료를 찾는 모든 작업을 의미하며, 탐색의 대상이 되는 자료구조의 종류에 따라 선형 구조(배열, 연결리스트)를 가지고 있으면 선형탐색, 비선형 구조(트리, 그래프)를 가지고 있으면 비선형탐색이 된다.

[참고]

• 배열(Array)
  배열은 데이터를 논리적 순서에 따라 순차적으로 데이터를 입력하며, 물리적 주소 또한 순차적이다. 그리고 인덱스를 가지고 있어서 원하는 데이터를 한번에 접근이 가능하기 데이터 접근 속도가 매우 빠르다. 그러나 배열은 데이터의 삽입/삭제에는 취약하다. 배열 특성상 데이터 삽입/삭제가 이루어지면 삽입/삭제가 이루어진 위치의 다음부터 모든 데이터의 위치를 변경해야 하기 때문이다.
  
  

• 위의 그림을 보면 K라는 데이터가 3번째 위치에 삽입됨에 따라 C, D, E, F의 위치가 바꼈다. 삭제의 경우에도 위와 마찬가지로 반대로 처리된다. 지금은 데이터의 수가 적기 때문에 큰 문제는 없지만, 만약에 배열 데이터의 수가 10000개라고 하고 삽입/삭제가 빈번하게 일어난다고 가정을 하고 생각을 하면 프로그램은 데이터 삽입/삭제때마다 데이터의 위치를 바꾸는데만 많은 리소스를 사용할 것이다. 이것은 매우 비효율적이다.

• 연결리스트(LinkedList)

연결리스트는 데이터를 논리적 순서에 따라 데이터를 입력한다. 하지만 물리적 주소는 순차적이지 않다. 인덱스를 가지고 있는 배열과는 달리 연결리스트는 인덱스 대신 현재 위치의 이전 및 다음 위치를 기억하고 있다. 때문에 한번에 데이터 접근이 가능하지 않고 연결되어 있는 링크를 따라가야만 접근이 가능하고, 배열에 비해 속도가 떨어진다. 하지만 데이터 삽입/삭제는 논리적 주소만 바꿔주면 되기 때문에 데이터 삽입/삭제는 용이하다.

위의 그림과 같이 삽입/삭제가 이루어지는 데이터의 링크만 변경하면 되므로 배열같이 다른 데이터에 영향을 많이 주지 않는다. 

출처: http://one-zero.tistory.com/entry/배열과-연결리스트-Array-LinkedList [One & Zero]

• 트리(Tree)
  

• 앞에서 설명된 선형 구조(배열 , 연결리스트란) 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태를 의미한다. 이와는 달리 트리와 그래프는 비선형 구조이다. 이때, 비선형 구조는 선형구조와는 다르게 데이터가 계층적(혹은 망)으로 구성되있다. 

선형구조와 비선형구조는 형태 뿐 아니라 용도에서도 차이를 보인다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있다. 그렇다면 트리는 무엇을 표현하기 위해 사용될까?

그것을 이해하기 위해서는 컴퓨터의 directory 구조를 예로 활욜 가능하다. 우리는 파일 시스템에서 폴더와 파일로 구성된 트리 구조를 통해 원하는 파일을 찾을 수 있다. 트리는 아래와 같은 요소들로 구성되어 있다.

• 구성요소

• Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드
• Node : 트리의 구성요소에 해당하는 A,B,C,D,E,F,G,H,I,J와 같은 요소
• Edge : 노드와 노드를 연결하는 연결설
• Terminal Node(Leaf Node) : 밑으로 또 다른 노드가 연결되어 있지 않은 H,I,J,F,G와 같은 노드
• Sub-Tree : 큰 트리(전체)에 속하는 작은 트리
• Level : 트리에서 각 층별로 숫자를 매김
• Height : 트리의 최고 레벨 (3)

• 트리의 종류

• 이진트리 : "이진 트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의서브트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진트리이어야 한다." 
  
• 포화 이진 트리(Full Binary Tree) : 모든 레벨이 꽉 찬 이진 트리
• 완전 이진 트리(Complete Binart Tree) : 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 틈 없이 노드가 채워진 이진 트리

출처 : http://monsieursongsong.tistory.com/6

• 그래프

현실세계의 사물이나 추상적인 개념 간의 연결 관계를 표현 
ex)  여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계


 

그래프의 경로와 싸이클

• 경로

정점 1에서 5로 가는 경로

1 -> 2 -> 4 -> 5

• 싸이클

정점 1에서 4로 가는 사이클

1 -> 2 -> 4 -> 3 -> 1

• 그래프 구성요소

• 정점 (Node, Vertex)

• 간선 (Edge)

• 정점간의 관계 나타냄 (비용, 개수 등등) 

• G(V, E) 

• 그래프는 Vertex와 Edge들의 집합 

출처: http://manducku.tistory.com/21 [Manducku`s Code]