Intro

자료구조

  • 데이터 베이스는 보조기억장치에서 저장하고, 자료구조는 주기억장치에 데이터를 가져온다.
  • 데이터를 구조적으로 표현하는 방식

알고리즘

  • 문제해결을 위한 절차/방법
  • 어떠한 문제를 해결하기 위한 여러 동작들의 모음

자료구조

데이터를 주기억장치로 가져와야 한다. 메모리는 공간이 협소하기 때문에 어떤 형태로 자료를 가져오고 관리할 것인가에 대한 고민이다.

하나의 객체를 저장하기 위해 변수들을 이용했다. 비록 이런 독립 변수들은 거의 모든 프로그래밍 언어에서 널리 사용되고 있지만, 복잡한 문제를 보다 효과적으로 해결하기 위해서는 적합하지 않다.

자료구조(data structure)는 특정 자료의 집합이며 집합 원소들 사이에 존재하는 상호 관계에 대한 설명을 포함하여 나타낼 수 있다.

생김새에 따라

  • 원시구조 : 메모리에 덩그라니 있는 형태
    • 정수, 실수, 문자, …
  • 선형구조 : 배열, 연결 리스트, 스택, 큐, 덱
  • 비선형구조 : 트리, 그래프

실체화에 따라

  • 물리적구조 : 주소대로
    • 정수, 실수, 문자, 배열, 연결 리스트
  • 추상적구조 : 떨어져있지만 연결됨
    • 스택, 큐, 덱, 트리, 그래프

배열

방대한 양의 데이터를 처리하기 위해 배열(array)과 같은 자료구조를 사용한다. 배열은 고정된 크기, 동일한 타입을 갖는 데이터들의 순차적인 집합이다. 루프문(loop)을 통하여 배열에 원소들을 쉽게 저장하거나 읽을 수 있으며, 연산을 하는 것도 가능하다.

  • 장점 : 쉽게 빠르게 원하는 것을 찾아올 수 있다.
  • 단점 : 추가/삭제가 불가능하다. 공간 크기가 가변적이지 않다.

배열에는 일차원 배열(one-dimensional array), 이차원 배열(two-dimensional array), 다차원 배열(multi dimensional array)가 있다.

연결 리스트

연결 리스트(linked list)란 정렬된 데이터들의 집합을 의미하며, 각 데이터들은 다음 데이터에 대한 위치 정보를 가지고 있다. 연결리스트에서 원소는 일반적으로 노드(node)라고 부른다. 연결 리스트의 각 원소들은 데이터와 연결부분(link)으로 구성된다. 연결 부분은 리스트의 다음 원소 위치를 가르키는 포인터(point, 주소)를 가지고 있다. 마지막 원소의 link에는 마지막임을 나타내는 null point를 가지게 된다.

  • 장점 : 삽입/삭제가 자유롭다.
  • 단점 : 연결부분(link)을 위한 공간이 추가적으로 필요하다. 원하는 것을 찾아가려면 첫번째부터 검색해야하므로 느리다.

연결 리스트 종류

  • 단순연결리스트 : 각 노드에 자료공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가르킴
  • 이중연결리스트 : 포인터 공간이 두 개가 있고, 앞/뒤 노드를 가르킴
  • 원형연결리스트: 단순연결리스트에서 마지막 노드와 처음 노드를 연결
  • 이중원형 연결리스트 : 이중연결+원형연결

현재는 컴퓨터 성능이 좋아졌기 때문에 배열은 잘 사용하지 않는다. 대신 요즘 고급언어들은 array를 list로 구현해둔다. array를 선언해서 사용했는데 삽입/삭제가 자유롭다면, 실제로 list처럼 동작하고 있다.

스택

스택(stack)은 모든 삽입 삭제가 top이라고 불리는 한쪽 끝에서 이루어지는 제한적인 선형 리스트이다. 후입선출(LIFO, Last In First Out) 구조이다.

스택에는 push, pop, empty 세 개의 기본 연산이 있다.

  • push : 스택의 top에 항목을 추가
  • pop : 스택의 top에 있는 항목을 제거하고, 사용자에게 그것을 반환
  • empty : 스택이 비어있는지 검사한 결과 true or false 반환

큐

큐는 rear라고 불리는 한쪽 끝에서만 삽입할 수 있고, front라고 불리는 다른 한쪽 끝에서만 삭제할 수 있는 선형 리스트이다. 선입선출(FIFO, First In First Out) 구조이다.

큐에는 enqueue, dequeue, empty 세 개의 기본 연산이 있다.

  • enqueue (= put) : 새로운 항목 추가
  • dequeue (= get) : 큐의 front에 있는 항목을 제거하고, 사용자에게 그것을 반환
  • empty : 큐가 비어있는지 검사한 결과 true or false 반환

트리

탐색을 편리하게 하기 위해 트리구조를 사용한다.
배열이나 리스트는 어차피 순차적으로 검색하기 때문에 속도의 별차이가 없다.

트리(tree)는 컴퓨터 과학 분야에서 매우 크고 동적인 리스트들에 대해 탐색하고, 인공 지능 시스템(artificial intelligence system), 인코딩 알고리즘(encoding algorithm)과 같은 다양한 응요에 대해 효율적인 구조로 널리 사용된다.

트리는 노드(node)와 가지(branch)라고 하는 요소들의 유한 집합으로 구성된다. branch는 노드 간을 연결하는 사용하는 방향선(directed line)이다. 한 노드와 관련된 가지의 개수를 노드의 차수(degree)라고 한다. 가지가 그 노드로 향하고 있을 때 그것을 진입차수(indegree) 가지라고 하고, 그 노드로부터 나가는 가지를 진출차수(outdegree)가지라고 한다. 진입차수와 진출차수 가지의 합을 노드의 차수라고 한다.

가장 첫 번째 노드를 루트(root)라고 한다. 루트의 진입차수는 정의에 의해 0이다. 루트를 제외한 트래 내의 모든 노드들은 진입 차수가 정확히 1이어야 한다. 노드의 레벨은 루트부터 노드까지의 거리이다. 루트의 레벨은 0이다. 루트의 자식 노드들은 레벨 1이며 그들의 자식노드들은 레벨 2, 이와 같은 방식으로 각 노드들의 레벨이 매겨진다.

이진 트리

이진 트리(binary tree)는 어떠한 노드도 세 개 이상의 서브트리(subtree)를 가지고 있지 않는 트리이다. 다시 말해 하나의 노드는 0, 1, 혹은 2개의 서브트리를 가질 수 있다. 각각의 서브트리는 그 자체가 이진트리이다.

그래프

그래프(graph)는 취항해야 하는 공항들 중에서 정기 항로를 계획하고 결정하는 것과 같은 복잡한 라우팅(routing) 문제들에 대한 해답을 찾는데 사용될 수 있다. 비슷하게 컴퓨터 네트워크를 통해 한 노드에서 다른 노드로 메시지를 배달하는 경로를 결정하는데 이용할 수 있다.

그래프는 정점(vertex)이라고 불리는 노드의 집합과 정점들의 쌍을 연결하는 선(line)들의 집합이다. 그래프는 유향(directed)과 무향(undirected)이 있다. 유향 그래프에서는 연결 선을 아크(arc)라고 부른다. 유향그래프에서는 두 정점들간의 아크에 따른 지정된 방향으로만 허용된다. 무향 그래프에서는 연결 선을 간선(edge)라고 부른다. 어디가 시작이고 어디가 끝인지 알수 없는 구조이다.

트리 vs 그래프
- 트리 : 부모가 있고, 부모와 자식은 1:1의 관계
- 그래프 : 모두 관계를 가지고 있을 수 있다.

알고리즘

개념

알고리즘(algorithm)

문제를 풀거나 작업을 수행하기 위한 단계적인 방법

예를 들어 가장 큰 정수를 찾아야 한다면

  • 동작정의 : 각 단계에서 무엇이 실행되는지 정의
    • 1단계에서 첫 번째 정수를 Largest 값으로 설정
    • 2단계에서 두 번째 정수가 Largest 값을 비교하여 크다면 Largest 값을 변경
    • 3단계에서 세 번째 정수가 Largest 값을 비교하여 크다면 Largest 값을 변경
    • 4단계에서 네 번째 정수가 Largest 값을 비교하여 크다면 Largest 값을 변경
    • 5단계에서 다섯 번째 정수가 Largest 값을 비교하여 크다면 Largest 값을 변경
  • 세련화
    • 2단계에서 5단계의 정의 변경 : 현재 정수가 Largest 값을 비교하여 크다면 Largest 값을 변경
    • 1단계도 다른 단계와 같아지기 위해 Largest 값을 0으로 미리 초기화
  • 일반화
    • N개의 양의 정수 중에서 정수를 찾고자 한다면, 컴퓨터에게 N번 반복하도록 시킨다.

세 가지 구조

구조화 프로그램이나 알고리즘을 위해 세가지 구조(construct)를 정의하였다. 프로 그램은 단지 세 가지 구조를 조합하여 생성되어야 한다는 개념이다. 세 가지 구조는 순차, 결정, 그리고 반복구조이다.

  • 순차(sequence) 구조 : 명령어의 순차적 나열이다.
  • 결정(decision) 구조 : 어떤 문제는 단순 명령어의 나열로 해결 할 수 없다. 조건을 검사할 필요가 있다. 만약 검사의 결과가 참이라면 어떤 순차적 명령어를 따라야 한다.
  • 반복(repetition) 구조 : 어떤 문제에서 동일한 순차적인 명령어를 반복해야 한다.

알고리즘 표현

알고리즘을 표현하는 도구에는 ‘순서도’와 ‘의사코드’가 있다.

  • 순서도(flow chart) : 알고리즘을 그림으로 표현한 것이다. 큰 그림을 제공할 목적으로 알고리즘의 상세한 부분은 감춘다.
  • 의사코드(pseudocode) : 알고리즘을 영어와 비슷한 자연어로 표현한 것이다.

서브알고리즘

구조화 프로그래밍의 원리는 알고리즘이 서브알고리즘(sub algorithm)[또는 서브루틴(sub routine), 프로시저(procedure), 함수(fucntion), 메소드(method), 모듈(module)]으로 불리는 작은 단위로 나누어질 것을 요구한다.

기본 알고리즘

몇 개의 알고리즘은 컴퓨터 과학에서 널리 사용되므로 이 알고리즘들을 기본 알고리즘이라고 한다.

정렬

컴퓨터 과학에서 가장 일반적인 응용 중의 하나가 정렬(sorting)이다. 정렬은 데이터 값에 따라서 데이터를 정리하는 과정이다.

선택 정렬 (selection sort)

리스트는 가상의 변에 의해 두개의 서브리스트(정렬된 서브리스트와 정렬되지 않은 서브리스트)로 나누어진다. 정렬되지 않은 서브리스트에서 가장 작은 원소를 찾아 정렬되지 않은 리스트 시작 부분의 원소와 교환한다. 선택과 교환 후 가상의 벽은 한 개의 원소를 앞쪽으로 이동시킨다. 정렬되지 않은 리스트에서 정렬된 리스트로 원소가 이동할 때마다 한 개의 정렬패스(sort pass)를 완료한다. n개의 원소의 리스트를 정렬하기 위해 n-1번의 패스를 요구한다.

버블정렬 (bubble sort)

두개의 서브리스트(정렬된 서브리스트와 정렬되지 않은 서브리스트)로 나누어진다. 가장 작은 원소는 비정렬 리스트에서 거품처럼 올라와 정렬된 서브리스트로 이동한다. 가장 작은 원소가 정렬 서브리스트로 이동한 후에 정렬 패스가 완료된다. n개의 원소의 리스트를 정렬하기 위해 n-1번의 패스를 요구한다.

원래의 버블 정렬은 가장 큰 원소를 리스트에서 ‘아래로’ 이동시키도록 작성되었다. 효율적인 관점에서 보면 큰 원소가 위로 올라가든 작은 원소가 위로 올라가든 차이가 없다.

삽입 정렬 (insertion sort)

가장 일반적인 알고리즘의 하나이다. 두개의 서브리스트(정렬된 서브리스트와 정렬되지 않은 서브리스트)로 나누어진다. 각 패스에서 비정렬 서브리스트의 첫 번째 원소가 선택되어 정렬된 서브 리스트로 이동하여 적절한 위치에 삽입된다. n개의 원소의 리스트를 정렬하기 위해 n-1번의 패스를 요구한다.

다른 정렬 알고리즘

다른 정렬 알고리즘들이 있다. 퀵 정렬(quick sort), 셸 정렬(shell sort), 힙 정렬(heap sort), 병합 정렬(merge sort) 같은 것들이 있다. 왜 이렇게 많은 정렬 알고리즘이 있을까. 그 이유는 정렬할 데이터의 타입 때문이다. 어떤 알고리즘은 거의 정렬된 리스트에 효율적인 반면 다른 알고리즘은 완전히 비정렬 리스트에 효율적이다.

  • 퀵정렬 : 기준을 정해서 기준을 중심으로 큰값은 뒤로 작은값은 앞으로 보내는 정렬이다. 기준이 되는 중앙값을 잡는게 중요하다. 어떤상황에서도 가장 평균적인 속도를 보장한다.

탐색

컴퓨터 과학에서 일반적인 알고리즘은 탐색(searching)이다. 탐색은 객체들의 리스트 중에서 목표가 되는 객체의 위치를 찾는 것이다.

리스트에는 두 개의 기본적인 탐색으로 순차 탐색과 이진 탐색이 있다. 순차 탐색은 어느 리스트에서나 사용할 수 있지만 이진 탐색은 리스트가 정렬되어야 한다.

순서화되지 않은 리스트를 탐색하는데 사용한다. 일반적으로 작은 리스트나 탐색되지 않은 리스트에서 주로 사용되는 기술이다. 다른 경우에서 가장 좋은 접근 방법은 먼저 리스트를 정렬한 후 이진 탐색을 사용하는 것이다.

순차 탐색은 리스트의 처음 부분에서 시작한다. 리스트에서 목표 원소를 찾거나 존재하지 않는것(리스트 끝까지 도달했기 때문)을 확인할 때 까지 계속한다.

순차 탐색 알고리즘은 매우 느리다. 만약 1백만 개의 원소를 갖는 리스트라면, 최악인 경우 1백만 번을 비교해야 한다. 만약 리스트가 정렬되지 않았다면 순차 탐색이 유일한 해결법이다. 그러나 만약 리스트가 정렬되었다면 이진탐색이라고 불리는 효율적인 알고리즘을 사용할 수 있다.

이진 탐색은 중간 원소의 데이터를 검사하는 것으로 시작한다. 이것은 목표원소가 첫번째 절반에 있는지 두번째 절반에 있는지 결정한다. 만약에 두번째 절반에 있다면 첫번째 절반 부분은 더 이상 검사할 필요가 없다. 이 과정을 목표 원소를 찾거나 값이 없다는 것을 깨달을 때까지 반복한다.

재귀 (recursion)

재귀는 알고리즘이 자신을 호출하는 방법이다. 간단한 예로 factorial 계산이 있다.

시간복잡도

복잡도를 측정하는 방법은 프로그램이 실행될 때 컴퓨터에 의해 수행되는 연산의 개수를 구하는 것이다. 이러한 방법으로 측정되는 복잡도는 프로그램을 실행하는 컴퓨터의 속도와는 무관하다.

빅오 표기법

오늘날 컴퓨터 속도에 대하여, 연산의 정확한 개수보다 크기의 차수에 관심을 갖는다. 효율성의 이런 단순화를 빅오 표기법(big-O natation)이라 한다. 표기 O(n)은 프로그램이 n개의 입력에 대하여 n번의 연산을 수행한다는 것을 의미한다. 표기 O(n^2)은 n개의 입력에 대해 n^2개의 연산을 수행함을 의미한다.

정렬의 시간 복잡도

  • 선택정렬 : O(n^2)
  • 버블정렬 : O(n^2)
  • 삽입정렬 : O(n^2)
  • 퀵정렬 : O(n log2 n)
  • 병합정렬 : O(n log2 n)

탐색의 시간 복잡도

  • 선형탐색 : O(n)
  • 이진탐색 : O(log2 n)

시간복잡도 그래프

  • O(log2 n) : 가장 빠름
  • O(n) : 리스트에서 n번째 값 찾기
  • O(n log2 n) : 퀵정렬, 병합정렬
  • O(n^2, n^3) : 버블, 삽입, 선택정렬, 이중 for문