소프트웨어 개발 _ 03 자료구조와 알고리즘

 

01 자료구조 (Data Structure) 

 

가) 정의

• 자료구조(Data Structure)란 자료를 컴퓨터의 기억장치 내에 저장하는 방법으로 다양한 자료를 효율적으로 표현하고 활용할 수 있도록 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의한 것.
• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨.
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
• 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 해 자료구조에 대한 이해가 중요

 

나) 분류

 

자료구조의 분류 : 선형구조와 비선형 구조

분류	간략한 설명	설명	종류
선형구조 (Linear)	자료가 일렬로 연결되어 있는 형태로 구성하는 방법	- 원시 코드로부터 정보를 추출하여 물리적 설계 정보저장소에 저장 - 물리적 설계자료들이 직선 형태로 나열되어 자료들 간의 순서를 고려한 구조로 전후/인접/선후 자료들 간의 1:1 관계로 나열됨. - 데이터가 연속적이고 순차적으로 배열되는 구조. 각 요소는 이전 요소와 다음 요소가 있으며, 특정 순서에 따라 배치됩니다.	배열, 선형리스트, 연결리스트, 스택, 큐, 데크 등
비선형구조 (Nonlinear)	자료의 구성이 계층구조나 망구조의 특별한 형태를 띠는 구조	- 한 자료 뒤에 여러 개의 자료들이 존재하는 구조로 인접/전후 자료들 간의 1:다 또는 다:다 관계로 배치됨 - 데이터가 계층적이거나 네트워크처럼 배열된 구조. 데이터 요소들이 여러 경로로 연결될 수 있습니다. 순서에 구애받지 않고 다양한 방식으로 접근할 수 있습니다.	트리와 그래프 등

 

자료구조 형태에 따른 구조

 

정적 자료구조(Static) : 프로그램 실행 중에 크기가 고정되어 있는 자료구조
- 배열은 정적 자료구조의 대표적인 예로 선언시 배열의 크기가 정해지고 이후에 변경 불가
- 미리 할당된 메모리 공간에 데이터를 저장하기 때문에 데이터 추가, 삭제, 크기 변경 등이 제한적
  
동적 자료구조(Dynamic) : 프로그램 실행 중 크기가 동적으로 조정될 수 있는 자료구조
- 필요에 따라 메모리에서 유연하게 공간을 할당하고 해제헤 데이터를 저장할 수 있어
- 데이터 추가, 삭제, 크기 변경 등이 가능함
- 대표적인 예: ArrayList, LinkedList, Queue, Stack 등이 있음

 

 

 

순차자료구조와 연결자료구조의 비교

구분	순차자료구조 (Sequential Data Structure)	연결자료구조 (Linked Data Structure)
메모리 저장 방식	메모리저장 시작위치부터 빈자리없이 자료를 순서대로 연속적으로 저장하는 방식	메모리에 저장된 물리적 위치나 순서에 상관없이 링크에 의해 논리적인 순서를 표현하는 방식
논리/물리 순서 일치 여부	논리적인 순서와 물리적인 순서가 일치하는 방식	논리적 순서와 물리적 순서가 일치하지 않음
연산특징	삽입.삭제 연산을 해도 빈자리가 없기 때문에 자료가 순서대로 연속하여 저장	삽입.삭제 연산으로 논리적인 순서가 변경되어도 링크 정보만 변경되어 물리적 순서는 변경되지 않음
프로그램 기법	배열을 이용한 구현	포인터를 이용한 구현

 

 

**노드(Node)란**

• 자료구조에서 하나의 단위를 의미한다. 노드를 어떤 데이터를 담고 있는 상자라고 이해할 수 있다.
• 노드에는 데이터(data)와 포인터(pointer)가 있다. 포인터는 주로 연결 자료 구조에서 사용되고, 순차 자료 구조에서는 필요하지 않다.

 

**순차 자료 구조(Sequential Data Structure)란**

• 순차 자료 구조는 배열을 생각하면 된다. 배열, 데이터를 메모리에 차례대로 저장하는 방식. 
• 배열의 가장 큰 특징은 연속적인 공간을 사용한다는 점. 즉, 메모리에서 데이터가 연속적으로 나열되어 있다.
• 배열에서 데이터를 찾을 때는 인덱스로 접근 할 수 있어서 빠르게 찾을 수 있지만, 배열의 중간에 데이터를 삽입하거나 삭제하려면 나머지 데이터를 이동시켜야 하는 번거로움이 있다.
• 선형 리스트(Linear List)와 같은 개념

 

** 연결 자료 구조(Linked Data Structure)란**

• 연결 자료 구조는 배열과 달리 연속된 공간에 저장하지 않고, 각각의 노드가 서로를 가리키며 연결이 되어있다. 이때, 데이터를 담고 있는 노드가 다음 노드를 가리키는 포인터를 갖고 있다.
• 연결 자료 구조는 중간에 데이터를 쉽게 삽입하거나 삭제할 수 있지만, 특정 위치의 데이터를 찾으려면 처음부터 차례대로 노드를 따라가야 하므로 속도가 느릴 수 있다.
• 연결 리스트(Linked List)는 연결 자료 구조의 대표적인 예시

 

**간단한 예시:

• 배열(순차 자료 구조):
  [10, 20, 30] (연속된 메모리 공간에 데이터가 순차적으로 저장됨)
• 연결 리스트(연결 자료 구조):
  [10] → [20] → [30] (각 노드가 데이터를 가지고, 다음 노드를 가리키는 방식)

 

연결 리스트의 종류

 

 

다) 스택과 큐

 

1) 스택(Stack)

 

**스택이란**

- 스택은 선형리스트(순차 자료 구조)의 하나로 데이터가 입력된 순서로 기억공간에 저장되어 후입선출하는 자료구조.

- 스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하여 top 위치에서만 원소를 삽입하고 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 출력되게 됨.

- LIFO(Last In First Out) : 후입선출 구조

스택의 개념도

 

 

** 스택의 연산의 종류 **

top()	스택의 맨 위에 있는 데이터 값을 반환한다.
push()	스택에 데이터를 삽입한다.
pop()	스택에서 데이터를 삭제하여 반환한다.
isempty()	스택에 원소가 없으면 true 값을 반환, 원소 있으면 false 값을 반환한다.
isfull()	스택에 원소가 없으면 false 값을 반환, 원소 있으면 true 값을 반환한다.

 

 

※ 스택이 비었다는 것은?

스택이 비었다는 것은, 더 이상 스택 안에 쌓여 있는 데이터(원소)가 없다는 것을 의미합니다. 마치 그릇 안에 아무것도 들어 있지 않은 상태를 생각해보면 이해하기 쉽습니다.

stack = []
//스택에 아무것도 넣지 않은 상태

 

예시를 보자.

stack = [1, 2, 3]  # 스택에 원소가 있음

if not stack:  # 스택이 비었는지 확인
    print("스택이 비었습니다.")  # 이 메시지는 출력되지 않음
else:
    print("스택에 원소가 있습니다.")  # 스택에 원소가 있으니 이 메시지가 출력됨

 

 

 

 

 

 

2) 큐(Queue)

 

** 큐(Queue)란 **

- 스택과 유사하게 삽입과 삭제의 위치가 제한되어 있지만 스택과는 달리 데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료구조.

- 큐는 뒤에서만 삽입되고 앞에서는 삭제만 할 수 있는 구조로 삽입된 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제된다. 

- FIFO (First In First Out) 선입선출 구조

큐의 개념도

 

 

** 큐의 연산 종류 **

enQueue()	큐에 데이터를 삽입한다. rear를 움직여 큐의 공간을 확보한 후 데이터를 삽입한다.
deQueue()	큐에서 데이터를 삭제한다. front를 움직여 가장 오래된 데이터를 다음 번째 데이터로 넘기게 된다.

 

 

 

3) 스택과 큐 연산 비교

 

 

 

 

 

라) 트리와 그래프 

 

1. 트리 (Tree)

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

- 트리의 시작노드를 루트노드(root node)라고 하고 노드를 연결하는 선을 간선(edge)이라고 한다. 같은 부모 노드를 가진 자식 노드들을 형제노드(sibling node)라고 하고 부모노드와 연결된 간선을 끊었을 때 생성되는 트리를 서브트리(subtree)라고 한다.

 

 

 

 

2. 그래프 (Graph)

 

연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조로 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다. 그래프 자료구조는 전기회로분석, 인공지능 등과 같이 여러가지 복잡한 문제들을 그래프로 나타내어 그래프이론을 기반으로 문제를 해결하는 경우가 많다.

 

 

 

 

마) 자료구조의 선택 기준

• 자료의 처리 시간
• 자료의 크기
• 자료의 활용 빈도
• 자료의 갱신 정도
• 프로그램의 용이성

 

 

바) 자료구조의 활용

 

 

 

 

 

02 알고리즘(Algorithm)

 

 

가) 알고리즘 개요

 

1) 알고리즘의 정의

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

- 알고리즘의 목표 : 단순히 원하는 결과를 얻을 수 있는 알고리즘이 아닌, 처리시간이나 기억장소 사용 측면에서 효율적인 알고리즘을 개발하는 것이다.

 

 

 

2) 알고리즘의 조건

 

입력, 출력, 명확성, 유한성, 효과성

 

 

 

나) 알고리즘 분석 기준

 

정확성, 작업량, 기억 장소 사용량, 최적성, 단순성

 

 

 

 

 

다) 알고리즘 표현 방법

표현 방법	설명
자연어 기술	일상적으로 사용하는 말이나 글을 이용하여 표현하는 방법으로 알고리즘 표현
순서도 표현	순서도(Flowchart)나 NS(Nassi-Shneiderman)차트와 같은 그래픽적인 방법으로 알고리즘 표현
의사코드(Pseudo Code)	자연어 기술방법보다 간략한 알고리즘을 프로그래밍 언어와 유사한 형태로 작성한 코드로 알고리즘 표현

 

 

출처 : https://booksr143.tistory.com/10

 

 

 

라) 알고리즘 성능 분석

 

1) 공간 복잡도

공간 복잡도 = 고정 공간량 + 가변 공간량

 

• 고정 공간량 : 프로그램, 변수 및 상수들과 같이 프로그램의 크기나 입출력 횟수에 상관없이 고정적으로 필요한 저장 공간
• 가변 공간량 : 프로그램의 수행과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간

 

 

2) 시간 복잡도

시간 복잡도 = 컴파일 시간 + 실행 시간

 

• 컴파일 시간 : 프로그램 특성과 관련이 적은 고정적인 시간으로 일단 컴파일이 되면 프로그램의 수정이 일어나지 않는 한 일정하게 유지
• 실행 시간 : 프로그램의 실행시간으로 컴퓨터의 성능 등에 의존하므로 실제 정확한 실행 시간을 측정하기 보다는 명령문의 실행 빈도수를 구하여 계산

 

 

 

 

알고리즘 간의 비교 시에는 주로 실행 시간을 사용하여 시간 복잡도를 나타낼 빅-오(Big Oh) 표기법을 사용하여 O(n)로 표기한다. 알고리즘에 따라 logn, n, nlogn, n^2, n^3, 2^n 등의 실행 시간 함수가 있다. 

가장 작은 값의 시간 복잡도를 가지는 알고리즘을 선택하는 것이 좋다.

 

 

 

 

 

 

 

출처 : https://cordcat.tistory.com/75

 

 

마) 정렬 알고리즘

 

1) 정렬의 분류

• 정렬 장소에 따라 내부정렬(Internal Sort)과 외부정렬(External Sort)로 분류할 수 있다.
• 정렬 방법은 사용하는 시스템의 특성, 데이터의 양과 상태, 정렬에 필요한 기억 공간 및 실행 시간 등의 조건을 고려하여 선택한다.

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

 

 

2) 내부 정렬 알고리즘의 분류