[TOPCIT] 01소프트웨어 개발_3.자료구조와 알고리즘

3. 자료구조와 알고리즘

3.1 자료구조(Data Structure)

정의

• 자료를 컴퓨터의 기억장치 내에 저장하는 방법 => 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정리

분류

• 선형구조와 비선형구조
  • 선형구조 : 자료가 일렬로 연결되어 있는 형태 ex) 배열, 선형리스트, 스택, 큐, 데크 등
  • 비선형구조 : 자료의 구성이 계층구조나 망구조의 특별한 형태 ex) 트리, 그래프 등

스택과 큐

• 스택
  • 데이터가 입력된 순서로 기억공간에 저장되어 출력 시 후입선출 되는 자료구조
  • 스택 연산
    • top() : 스택의 맨 위에 있는 데이터 값 반환
    • push() : 스택의 데이터 삽입
    • pop() : 스택에서 데이터 삭제 후 반환
    • isempty() : 스택에 원소가 없으면 true, 있으면 false 반환
    • isfull() : 스택에 원소가 없으면 false, 있으면 true 반환
• 큐
  • 뒤에서 데이터가 삽입되고, 앞에서는 삭제만 할 수 있는 선입선출의 자료구조
  • 큐 연산
    • enQueue : 큐에 데이터 삽입
    • deQueue : 큐에 데이터 삭제

트리와 그래프

• 트리
  • 원소들 간에 계층 관계를 가지는 계층형 자료 구조 => 하위 원소로 내려가며 확장되는 나무 모양 구조
  • 트리 시작 노드 : 루트 노드 (root node)
  • 노드 연결하는 선 : 간선 (edge)
  • 같은 부모 노드를 가진 자식 노드 : 형제 노드 (sibling node)
  • 자식이 없는 노드 : 단말 노드 (leaf node)
  • 부모 노드와 연결된 간선을 끊었을 때 생기는 트리 : 서브 트리 (subtree)
• 그래프
  • 연결되어 있는 원소 사이의 관꼐를 표현하는 자료 구조
  • 객체를 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합
  • 그래프 종류 : 무방향 그래프(방향성 없는 선으로 연결된 그래프), 방향 그래프(방향성을 지니는 그래프로서 순서 중요), 완전 그래프(서로 다른 정점을 연결하여 최대로 많은 간선 수를 가진 그래프), 가중 그래프(정점을 연결하는 간선에 가중치 할당한 그래프)
  • 그래프 구현 방법
    • 인접행렬 : 2차원 배열 사용
    • 인접리스트 : 연결 자료구조 이용하여 인접 정점들을 연결하는 표현 방법

1.2 알고리즘

알고리즘 개요

• 알고리즘 정의 : 주어진 문제를 해결하기 위한 일련의 처리 절차를 단계적으로 기술한 것 => 문제 해결 방법을 추상화하여 단계쩍 절차를 논리적으로 기술해 놓은 명세서
• 알고리즘의 조건 : 입력, 출력, 명확성, 유한성, 효과성이 있어야 함

알고리즘 분석 기준

• 정확성 : 타당한 입력에 대해 유한 시간 내에 올바른 결과를 산출하는지 판단
• 작업량 : 알고리즘을 수행의 횟수량 측정
• 기억 장소 사용량 : 데이터 정보 등을 저장하기 위한 컴퓨터 메모리의 사용량
• 최적성 : 알고리즘 적용할 시스템의 사용 환경 고려할 때 적합한 알고리즘인지 판단
• 단순성 : 알고리즘 표현이 얼마나 이해하기 쉽게 명확하게 작성되었는지 판단

알고리즘 표현 방법

• 자연어 기술 : 일상적으로 사용하는 말이나 글을 이용하여 표현하는 방법
• 순서도 표현 : 순서도나 NS 차트와 같은 그래픽적인 방법
• 의사코드 (Pseudo Code) : 프로그래밍 언어와 유사한 형태로 작성한 코드로 표현

알고리즘 성능 분석

• 공간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하기까지 필요한 총 저장 공간 => 공간 복잡도 = 고정 공간량 + 가변 공간량
  • 고정 공간량 : 프로그램의 크기나 입출력 횟수에 상관 없이 고정적으로 필요한 저장 공간
  • 가변 공간량 : 프로그램 수행과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행 정보 저장 공간
• 시간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하기까지 걸리는 시간 => 시간 복잡도 = 컴파일시간 + 실행시간
  • 컴파일 시간 : 고정적인 시간, 프로그램 수정이 일어나지 않는 한 일정하게 유지
  • 실행시간 : 프로그램의 실행 시간, 명령문의 실행 빈도수를 구해서 계산
  • 시간 복잡도를 나타낼 때는 빅-오(Big Oh) 표기법 사용

정렬 알고리즘

• 정렬 분류 : 내부정렬(소량의 데이터에 대해 주기억 장치에 올려서 정렬 방식)과 외부정렬(대량의 데이터에 대해 보조 기억 장치에서 정렬 방식)
• 내부 정렬 알고리즘
  • 삽입정렬 : 데이터가 정렬되어 있다고 가정하고 값을 해당 위치에 삽입하여 정렬
  • 쉘정렬 : 주어진 자료 리스트를 특정 매개변수 값의 길이를 갖는 부파일로 쪼개서, 각 부파일에서 삽입정렬을 수행
  • 선택정렬 : 최소값을 찾아 왼쪽으로 이동시키는데 데이터 크기(개수)만큼 반복하여 정렬하는 방법
  • 퀵정렬 : 임의 기준 선택 후 기준보다 작으면 왼쪽, 크면 오른쪽으로 위치 하는 것을 반복하여 정렬하는 방법
  • 버블정렬 : 인접한 데이터 간에 교환이 계속해서 일어나면서 정렬하는 방법
  • 힙정렬 : 최대 힙 트리나 최소 힙 트리 구성해 정렬하는 방법
  • 머지정렬 : 데이터 크기를 반으로 계속 나누면서 정렬해서 합치는 방법
  • 기수정렬 : 데이터의 낮은 자리 수부터 비교하여 정렬하는 방법

검색 알고리즘

• 검색 알고리즘 개요 : 데이터 집합에서 원하는 항목을 효율적으로 찾는 기법
• 검색 알고리즘의 분류
  • 선형 검색
    • 선형 탐색 : 처음부터 마지막까지 순서대로 각 레코드를 비교하면서 찾아가는 방법
  • 제어 검색
    • 이진 탐색 : 상한값과 하한값을 설정하고 그 중간값을 구한 후 키와 중간값을 계속 비교하면서 검색하는 방법
    • 피보나치 탐색 : 피보나치 순열을 이용하여 서브 파일을 형성해 가면서 검색하는 방법
    • 보간 탐색 : 탐색 대상이 있을 것으로 예상되어지는 위치를 선택하여 찾아가는 방식으로 이후 그 위치에세 선형 탐색
    • 블록 탐색 : 전체 데이터를 일정한 개수의 블록으로 구분하고 찾기를 원하는 데이터가 속한 블록을 결정한 후에 해당 블록 내의 키 값을 순차적으로 검색하는 방법
    • 이진트리 탐색 : 이진 트리를 이용하는 검색 방법
  • 특정 함수를 이용하여 접근하는 방식
    • 해싱 : 해싱 함수를 이용하여 저장되어 있는 주소를 직접 계산하여 찾아가는 검색 방법

그래프 탐색 알고리즘

• 그래프 탐색 : 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산
• 깊이 우선 탐색(DFS) : 시작 정점에서 한 방향으로 깊이 탐색하다가 더 이상 갈 곳이 없으면 마지막 갈림선 간선으로 되돌아와 다른 방향의 간선으로 탐색 반복
• 너비 우선 탐색(BFS) : 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 탐색 방법

최소 신장 트리(MST)

• 최소 신장 트리 : 신장 트리(무방향 가중치 그래프 내 모든 정점을 포함하고 서로 연결되어 있는 트리의 특수한 형태로 사이클을 포함해서는 안되는 트리)는 구성하는 가중치의 합이 최소인 트리
• 크루스칼 알고리즘 : 정점에 연결된 간선 가운데 가중치가 최소인 간선을 선택하고 추가된 간선이 사이클을 만드는지 체크하는 방식으로 처리하여 가중치가 작은 간선을 순서대로 선택하는 방법
• 프릴 알고리즘 : 구성된 최소 신장 트리 부분에 방문하지 않은 새로운 정점과 간선을 선택하여 확장하는 방법