[기술영역][01 소프트웨어 개발] 3. 자료구조와 알고리즘

학습 목표

1. 자료구조의 정의와 분류에 대하여 설명하고, 선형/비선형구조를 활용할 수 있다.
2. 알고리즘의 역할을 이해하고 상황에 따라 적합한 알고리즘을 선택할 수 있다.

핵심 키워드

• 배열, 리스트, 스택, 큐, 데크, 트리, 그래프, 알고리즘의 정의, 알고리즘 성능 분석, 정렬/탑색 알고리즘

01 자료구조(Data Structure)

가. 정의

• 자료구조란 자료를 컴퓨터의 기억장치 내에 저장하는 방법으로 다양한 자료를 효율적으로 표현하고 활용할 수 있도록 자료의 특성과 사용용도를 고려하여 조직적, 체계적으로 정의한 것이다.

나. 분류

• 선형구조와 비선형 구조로 나눌 수 있다.

다. 스택과 큐

1. 스택(Stack)

• 스택은 선형리스트의 하나의 데이터가 입력된 순서로 기억공간에 저장되어 출력을 하게 되는 자료구조이다.
• 즉 스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하여 top 위치에서만 원소를 삽입하고 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 출력되게 된다.

2. 큐(Queue)

• 스택과 유사하게 삽입과 삭제의 위치가 제한되어 있지만 스택과는 달리 데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료 구조이다.
• 큐는 뒤에서만 삽입되고 앞에서는 삭제만 할 수 있는 구조로 삽입된 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제된다.

3. 스택과 큐의 연산 비교

라. 트리와 그래프

1. 트리(Tree)

• 원소들 간에 계층관계를 가지는 계층형 자료구조로 상위원소에서 하위원소로 내려가면서 확장되는 나무모양의 구조를 가지고 있으며 원들 간에 1:다 관계를 가진다

2. 그래프(Graph)

• 연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다.
• 전기회로분석, 최단거리 검색, 인공지능 등과 같이 여러가지 복잡한 문제들을 해결할때 쓰임

• 그래프는 수행하는 기능이나 응용방법에 따라 다양한 구현방법으로 메모리 내 표현된다.
  • 인접행렬(Adjacency Matrix): 순차 자료구조를 이용한 그래프 구현 방식으로 행렬에 대한 2차원 배열을 사용하여 그래프의 두 정점을 연결한 간선의 유무를 행렬로 저장하는 방식
  • 인접리스트(Adjacency List): 연결 자료구조를 이용한 구현방식으로 각 정점에 대한 인접 정점들을 연결하여 만든 단순 연결 리스트로 각 정점의 차수만큼 노드를 연결하는 방식

마. 자료구조의 선택 기준

1. 자료의 처리 시간
2. 자료의 크기
3. 자료의 활용 빈도
4. 자료의 갱신 정도
5. 프로그램의 용이성

바. 자료구조의 활용

• 데이터의 정렬(Sort),검색(Search),파일 편성 및 인덱스 등에서 주로 활용된다.

1. 리스트: 배열의 구현, DBMS 인덱스, 탑색이나 정렬과 같은 문제
2. 스택 : 인터럽트 처리, 재귀 프로그램의 순서 제어, 서브루틴의 복귀 번지 저장, 후위 표기법으로 표현된 수식의 연산, 텍스트 에디터 Undo기능
3. 큐: 운영체제의 작업 스케줄링, 대기 행렬의 처리, 비동기 데이터 교환, 키보드 버퍼 이용, 스풀 운용
4. 데크: 스택과 큐의 장점만 활용한 자료구조로 스택과 큐 관련 분야에서 활용
5. 트리: 탐색이나 정렬과 같은 문제, 문법의 파싱, 허프만 코드, 결정 트리, 게임 등

02 알고리즘(Algorithm)

가. 알고리즘 개요

1. 알고리즘의 정의

• 알고리즘이란 주어진 문제를 해결하기 위한 일련의 처리 절차를 단계적으로 기술한 것으로 문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서이다.

2. 알고리즘의 조건

나. 알고리즘 분석 기준

1. 정확성(Correctness)
2. 작업량(Amount of Work Done)
3. 기억 장소 사용량(Amount of Space Used)
4. 최적성(Optimality)
5. 단순성(Simplicity)

다. 알고리즘 표현 방법

라. 알고리즘 성능 분석

• 실행에 필요한 공간 측면에서 분석하는 공간 복잡도와 실행에 소요되는 시간 측면에서 분석하는 시간 복잡도를 추정하여 일반적인 평가를 한다.

1. 공간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하기 까지 필요한 총 저장공간을 의미한다.

2. 시간 복잡도

• 알고리즘을 프로그램으로 실행하여 완료하는 데 걸리는 시간이다.

마. 정렬 알고리즘

1. 정렬의 분류

• 내부정렬: 소량의 데이터에 대해 주기억 장치에 올려서 정렬하는 방식이다. 정렬속도는 빠르나 주기억 장치의 용량에 의해 정렬할 수 있는 데이터의 양이 제한됨
• 외부정렬 : 대량의 데이터에 대해 보조 기억 장치에서 정렬하는 방식으로 대량의 데이터를 몇 개의 서브 파일로 나누어 내부 정렬을 한 후 보조기억장치에서 정렬된 각 서브 파일들을 병합하는 방식으로 속도가 느림

바. 검색 알고리즘

1. 검색 알고리즘 개요

• 데이터의 정렬 여부에 따라 구분 한다.
• 해싱: 특정 함수에 따라 키 값을 게산하여 데이터를 검색한다.

2. 검색 알고리즘의 분류

사. 그래프 탑색 알고리즘

1. 그래프 탐색(Graph Search)

• 그래프의 가장 기본적인 연산으로 하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한 번씩 방문하여 처리하는 연산이다.

2. 깊이 우선 탐색(DFS, Depth First Search)

3. 너비 우선 탐색(BFS, Breadth First Search)

• 큐

아. 최소 신장 트리(Minimum Spanning Tree)

1. 최소 신장 트리

2. 크루스칼(Kruskal)알고리즘

• 정점에 연결된 간선 가운데 가중치가 최소인 간선을 선택하고 추가된 간선이 사이클을 만드는지 체크하는 방식으로 처리한다.
• 가중치가 가장 낮은 간선을 선택한 후 정점과 연결이 되어 있지 않더라도 가중치가 작은 간선을 순서대로 선택하는 방법이다.

3. 프림(Prime) 알고리즘

• 분석대상 그래프에서 임의의 한 정점을 선택하여 각 반복과정마다 그때까지 구성된 최소 신장 트리 부분에 방문하지 않은 새로운 정점과 간선을 선택하여 확장해나가는 방법이다.