1. 자료구조의 정의

❓ 자료구조란?

🔥 컴퓨터 메모리에 효율적으로 데이터를 저장하는 방식을 의미합니다.

자료구조는 컴퓨터 프로그램을 실행하는데 필요한 메모리를 절약할 뿐만 아니라 프로그램의 수행 시간을 최소화하는 기능을 합니다.

❓ 알고리즘이란?

🔥 문제를 효율적으로 풀어내가는 방법(푸는 방식)을 의미합니다.

효율적인 알고리즘을 작성하기 위해서는 먼저 데이터를 효율적으로 저장하는 방식인 자료구조를 배운 후 추가로 알고리즘을 배우는 것이 효과적입니다.

2. 자료구조의 분류

프로그램에서 저장하는 자료를 형태로 분류하면 아래의 그림과 같이 크게 단순 구조, 선형 구조, 비선형 구조, 파일 구조로 구분되게 됩니다.

1. 단순구조

❓ 단순 구조란?

🔥 정수, 실수, 문자, 문자열 등 프로그램에서 제공하는 기본적인 데이터 타입을 의미합니다.

2. 선형 구조

❓ 선형 구조란?

🔥 선형 구조란 앞 뒤의 데이터들이 일대일(1:1)관계인 경우를 의미합니다.

대표적으로 리스트, 스택, 큐, 덱이 있습니다.

선형구조를 그림으로 살펴보면 다음과 같은 형태를 띄게 됩니다.

3. 비선형 구조

❓ 비 선형 구조란?

🔥 비 선형 구조란 앞 뒤의 데이터들이 일대일 구조가 아닌 계층 구조 혹은 망 구조를 갖는 관계를 의미합니다.

대표적으로 트리, 그래프가 있습니다.

4. 파일 구조

❓ 파일 구조란?

🔥 파일 구조란 보조 기억장치(하드 디스크,SSD)에 저장되는 파일에 대한 자료구조를 의미합니다.

선형, 비선형 구조는 컴퓨터 주 기억장치(RAM)에 저장된다는 사실을 기반으로 한 반면 파일 구조는 보조 기억장치(하드디스크, SSD)에 저장되는 구조입니다.

3. 추상 자료형(Abstract Data Type, ADT)

❓ 추상 자료형이란?

🔥 추상 자료형이란 자료구조를 표현하는 방법 중 하나입니다.

😳 추상 자료형이 왜 필요할까?

❗먼저 추상 자료형이 알기위해서는 정보 은닉을 알고 있어야 합니다.

❓정보 은닉이란?

🔥 정보은닉이란 프로그래밍에서 중요하게 사용되는 개념 중 한가지로 중요한 정보만을 나타내고, 중요하지 않은 정보는 숨기는 것을 의미합니다.

다음의 그림을 살펴봅시다.

위의 그림에서 개발자 A가 라이브러리를 구현하였고 이를 오픈 소스로 공개하게 되었습니다.

그리고 개발자 B는 개인 프로젝트를 하던 도중 깃허브 사이트를 방문하여 해당 라이브러리를 발견했습니다.

그리고 이를 개인이 개발하는 프로젝트의 기능 구현에 사용하려고 합니다.

❓ 과연 이 때 개발자 B는 개발자 A가 구현한 라이브러리의 내부 구조를 모두 자세하게 알아야 할까요?

→ 아닙니다. 단지 해당 라이브러리의 기능을 구현하는지에 대한 설명과 어떻게 사용하는지에 대해서 알아봐야 합니다.

🔥 이처럼 추상 자료형은 정보 은닉의 개념을 이용하여 자료구조를 간략하게 표현하는 것을 의미합니다.

1) 자료, 자료형

추상 자료형을 살펴보기전 그림을 통해 자료(Data)와 자료형(Data Type)에서 알아봅시다.

자료형은 자료(Data)와 자료를 처리하기 위한 명령 혹은 연산(Operation)을 합친 것을 의미합니다.

❓자료란?

🔥 프로그램내에서 처리되는 대상으로 특정한 값을 의미합니다.

다음의 예를 통해 더 자세히 이해해 봅시다.

자료형	구분	예시
정수자료형	자료(data)	-2,-1,0,1,2,3,….
	연산(Operation)	더하기(+) 빼기(-) 곱하기(*) 나누기(/) 나머지 연산(%)

다음과 같이 정수 자료형의 자료(Data)는 정수로 이어져 있고 연산은 자료를 처리하기 위한 연산으로 되어 있는 것을 확인할 수 있습니다.

2)추상 자료형

❓ 추상 자료형이란?

🔥 추상적이란 추상적으로 정의된 자료형을 의미합니다.

다음의 예를 통해서 이해해봅시다.

ex) 현재 위치를 알려주는 GPS 프로그램을 가정한다고 합시다.

GPS 프로그램에서 저장해야 하는 정보: x좌표와 Y좌표

위치 자료를 처리해야하는데 필요한 연산: 1. 위치 자료의 변경, 2. 위치 자료 사이의 거리 계산, 3. 두 개의 위치 자료 사이의 비교 연산

이를 추상 자료형으로 나타내면 다음과 같습니다.

GPS 프로그램의 추상 자료형

자료

X좌표의 위치를 나타내는 정수
Y좌표의 위치를 나타내는 정수

연산

이름	입력(Input)	출력(Output)	설명
변경(Modifiy())	1. 위치 자료 p 2. X축 변경 거리: x 3. Y축 변경 거리: y	없음	위치 p에서 X축으로 x만큼, Y축으로 y만큼 변경
위치 사이 거리 계산(distance())	1. 위치 자료 p1 2. 위치 자료 p2	두 위치 사이의 거리	두 위치 p1, p2 사이의 거리를 구합니다.
위치 비교(equal())	1. 위치 자료 p1 2. 위치 자료 p2	참(True) 또는 거짓(False)	두 위치 p1, p2가 같은 위치인지 조사합니다.

4. 알고리즘

앞 부분에서 알고리즘에 대해서 알아봤습니다.

알고리즘을 어떻게 표현하는지에 대해서 알아보겠습니다.

1. 알고리즘의 표현

종류	내용	특성
자연어	사람이 사용하는 일반적인 언어로 표현합니다.	기술하는 사람에 따라 일관성과 명확성이 달라지기 때문에 알고리즘 표현으로는 부적절합니다.
순서도	알고리즘을 그림으로 도식화해서 표현합니다.	알고리즘 각 단계를 직관적으로 표현할 수 있는 장점이 있으나, 복잡한 알고리즘을 나타내기에는 비효율적입니다.
의사코드	특정 프로그래밍 언어가 아닌 가상의 언어로 표현합니다.	프로그래밍 언어보다는 덜 엄격한 문법이나, 자연어보다는 더 체계적으로 기술이 가능합니다.
프로그래밍 언어	프로그래밍 언어로 표현합니다.	알고리즘을 구체적인 구현 소스를 통해 나타내기 때문에 추가 구현 단계가 없다는 장점이 있으나, 너무 엄격하게 기술하여 비효율적인 경우가 많습니다.

현재 알고리즘의 표현 방법으로는 주로 순서도와 의사코드를 사용하고 있습니다.

2. 순서도와 의사코드

주로 알고리즘을 표현하는 방법인 순서도와 의사코드에 대해서 알아보겠습니다.

순서도

순서도에서 사용되는 기호는 다음과 같습니다.

다음으로 의사코드에 대해서 알아보겠습니다.

의사코드

(1) 지정문

🔥 지정문이란 변수에 특정한 값을 대입하는 명령을 의미합니다.

🚨 지정문의 연산자(←) 화살표 방향은 오른쪽에서 왼쪽입니다.

(2) 조건문

🔥 조건문이란 조건식을 만족하는지에 따라 흐름이 결정되는 명령을 의미합니다.

대표적으로 if-then-else문과 switch-case문이 있습니다.

조건문의 순서도

(3) 반복문

🔥 반복문이란 특정 명령을 여러 번 반복적으로 수행하는 명령을 의미합니다.

대표적으로 for문과 while문, 그리고 do-while문이 있습니다.

for문

🔥 for문은 초기값을 설정하고 나서 조건식이 만족할 때까지 명령문을 실행합니다.

순서도

while문

🔥 while문은 반복 횟수에 상관없이 조건이 만족할 때까지 반복하는 명령문입니다.

순서도

do-while문

🔥 do - while문은 먼저 do안의 명령문을 수행한 후 조건식을 검사하는 명령문입니다.

순서도

3. 알고리즘의 성능 분석

(1) 알고리즘의 분석 기준: 공간 복잡도와 시간 복잡도

앞서 알고리즘은 “문제를 효율적으로 풀어내는 방법”이라고 알아봤었습니다.

이 알고리즘을 평가 및 분석하는 기준에는 공간 복잡도와 시간 복잡도가 있습니다.

❓ 공간 복잡도란?

🔥 공간 복잡도란 알고리즘 실행에 필요한 저장공간(메모리 혹은 디스크)가 얼마만큼 필요한지 나타낸 것입니다.

❓ 시간 복잡도란?

🔥 시간 복잡도란 알고리즘 실행에 시간이 얼마만큼 걸리는지를 나타낸 것입니다.

💡 보통 알고리즘의 성능을 평가 및 분석하는 기준에서 시간 복잡도가 공간 복잡도보다 더 중요한 평가 기준이 됩니다.

❓ 왜 일까?

왜냐하면 대부분 프로그램이 실행되는 환경에서 공간에 대한 비용보다 시간에 대한 비용이 더 크기 때문입니다.

시간복잡도를 기반으로 알고리즘의 성능을 분석하는 것에 초점을 두고 효율을 분석합시다.

(2) 시간 복잡도: 입력 값에 따른 실행 연산의 빈도수

앞서 시간 복잡도에 대해서 알아봤습니다.

이번에는 시간 복잡도를 측정하는 방법을 알아봅시다.

시간 복잡도를 측정하는 방법

시간 복잡도를 측정하는 방법은 1) 실제 걸리는 시간을 측정하여 구하는 경우와 2)실행되는 명령문의 개수를 계산하는 방법, 두가지 방법이 있습니다.

1) 실제 걸리는 시간을 측정하여 구하는 경우

시간 측정 명령어를 통해서 비교적 간단하게 측정할 수 있지만 컴퓨터마다 성능에따라 달라질 수 있다는 단점이 있습니다.

따라서 동일한 알고리즘이더라도 컴퓨터의 성능에 따라 차이가 발생하는 문제가 있어 객관성 측면에 약점이 있습니다.

이에 알고리즘 시간 복잡도는 일반적으로 2)실행되는 명령문의 개수를 계산하는 방법을 통해 측정합니다.

다음의 두가지 알고리즘을 살펴봅시다.

알고리즘1

CalSum(n){
		i<-start; //1번
		sum<-0; //1번
		
		for(;i<=n;i<-i+1){ //1+1번
			sum<-sum + i; //1+1번
	}
		return sum;
}

시간복잡도 계산:

지정문 2번 사용
n번의 반복문 안에서 각각4번의 연산이 필요합니다.

변수 i 비교(i<= n), 변수 i의 증가(i ←i+1), 더하기 연산(sum ← sum +i) 번

알고리즘 빈도 수 계산: 2 + n 3 = 3n +2

ex) n이 1~10까지 합을 구하는 경우 : n = 10,32번의 연산이 필요합니다 n이 10,000이라면 모두 30,002번의 연산이 필요합니다.

알고리즘2

CalcSum(n){
	count<-n;
	sum<-1 + n;
	sum<-sum *count;
	sum<- sum/2
	return sum;
}

시간복잡도 계산:

n 값에 상관없이 5번의 연산이 필요합니다.

지정문 1번(count←n)
더하기 연산 1번
지정문 1번(sum← 1+n)
곱하기 연산 1번(sum←sum * count)
나누기 연산 1번(sum←sum/2)

알고리즘의 빈도 수 계산: 5

n의 값이 증가해도 5번의 연산만 진행됩니다.

(3) 시간 복잡도 = 빅오 표기법

앞서 시간 복잡도를 살펴봤습니다.

시간 복잡도는 입력 값 또는 입력 개수 n에 의해 결정됩니다.

따라서 알고리즘의 시간 복잡도는 시간 복잡도 함수 중에서 가장 큰 영향을 주는 n에 대한 항만을 표시하는 것이 일반적입니다.

이러한 방법을 빅오 표기봅이라고 부르며 일반적으로 계수는 생략하여 표시합니다.

ex) 알고리즘의 시간 복잡도 함수 = 3n + 2인 경우

n에 대해서 가장 큰 영향을 주는 항은 3n입니다. 그리고 계수를 생략하여 n이 되게 됩니다.

따라서 알고리즘1의 시간 복잡도는 빅오 표기법에 따라 다음과 같이 계산됩니다.

알고리즘2의 빅오 표기법은 다음과 같습니다.

빅오 표기법의 정확한 정의는 다음과 같습니다.

두 개의 함수 f(n)과 g(n)이 주어졌을 때, 모든 n≥n0에 대해 |F(n) <= c|g(n)| 을 만족하는 2개 상수 c와 n0가 존재하면 f(n) = O(g(n))이다.

위의 정의 결과로 빅 오 표기법은 최고 차항만 남기고 다른 낮은 항들과 상수는 제가할 뿐만 아니라, 최고 차항의 계수도 버려, 결국 최고 차항의 차수만을 사용한다는 것입니다.

다음은 시간 복잡도에서 가장 많이 사용되는 최고 차항들을 표시한 것입니다.

단 n이 증가됨에 따라 위 값들의 크기는 다음 순서로 커집니다.

이를 그림으로 살펴보면 다음과 같습니다.

📒 Reference

프리렉 - 열혈강의 자료구조

저작자표시

1. 자료구조의 정의

2. 자료구조의 분류

1. 단순구조

2. 선형 구조

3. 비선형 구조

4. 파일 구조

3. 추상 자료형(Abstract Data Type, ADT)

1) 자료, 자료형

2)추상 자료형

GPS 프로그램의 추상 자료형

4. 알고리즘

1. 알고리즘의 표현

2. 순서도와 의사코드

3. 알고리즘의 성능 분석

📒 Reference

검색 태그

티스토리툴바