자료구조 강의 1장

해당 포스팅은 pc에서 작성

건국대학교 KOCW 자료구조 강좌를 들으면서 필기

1강~4강 약 30분까지

Data Structures

문제의 해법을 다양한 단계의 복잡도를 통해 개선

가능한 해법들을 열거

가능한 모든 해법에 대해 생각할 수 있게 해 줌

 

변수

자세한 설명은 생략

시스템에 의해 정의된 데이터형(int, float, double, string 등 +오버플로우 이슈) 

사용자 정의 데이터형(struct, class 등)

 

데이터 구조

효율적으로 데이터를 사용하기 위해 컴퓨터에 데이터를 저장하고 정리하는 방법

항목 정리 방법에 따라,

선형 데이터 구조: 리스트, 스택, 큐

비선형 데이터 구조: 트리, 그래프

 

추상 데이터형(Abstract Data Type, ADT)

문제를 푸는 과정을 단순화하기 위해 데이터 구조와 연산을 합쳐놓은 것

데이터의 선언, 연산의 선언 두 부분으로 구성

예) 리스트, 큐, 우선순위 큐, 스택, 이진트리, 집합, 해시 테이블, 그래프 등

 

스택 : LIFO (Last In First Out, 후입선출) 나중에 들어간 것은 먼저 나오게끔

사방이 막혀있는 상자에 위에서부터 짐을 넣고 뺄 때는 위에서부터 빼는 것이라 생각하면 편함

스택 만들기, 항목 집어넣기(push), 항목 꺼내기(pop), 맨 위의 항목 찾기(top), 항목 갯수 찾기 등을 주로 사용

 

알고리즘

주어진 문제를 해결하기 위한 단계별 지시사항들

좋은 알고리즘: 기준에 따라 시간, 공간적으로 가장 효율적인 것 (수행 시간 적게, 메모리 덜 먹게끔)

 

문제(입력)의 크기(n개) 증가에 따라 처리 시간(f(n))이 얼마나 증가하는지 분석

 

증가율: 함수 입력의 크기 증가에 따라 수행 시간이 증가하는 비율

예) 어떤 함수에서 각각의 비용이 n^4, 2n^2, 100n, 500이라 하면

n이 아주 커질 때 다른 비용은 n^4에 비해 증가량이 미미하므로 전체의 비용은 n^4에 근사

f(n) = n^4 + 2n^2 + 100n + 500 ≒ n^4

 

1 < logn < n < nlogn < n^2 < n^3 < 2^n

그래프를 겹쳐 보면 어느 것이 n이 증가함에 따라 f(n) 값이 작은지 시각적으로 이해하기 쉽다

 

 

분석의 종류

알고리즘은 어떤 입력에 대해 더 적은 시간(최선의 경우)이 걸리고,

어떤 입력에서 더 오랜 시간(최악의 경우)이 걸릴 수 있음

 

알고리즘을 분석하기 위해 점근적(Asymptotic) 분석/표기법의 기초를 이루는 일종의 문법이 필요

주어진 함수 f(n)에 대해 n의 값이 클 때 f(n)에 근접한 다른 함수(곡선) g(n)을 찾으려고 한다

수학에서는 이러한 곡선을 점근선(Asymptote)라 부른다.

 

세 가지 종류의 분석

최선, 평균, 최악의 경우에 대한 수식이 있을 때 이 모두에 대한 상한과 하한을 찾아야 한다

 

빅-오 표기법

함수에 대한 상한(Upper bound)을 찾게 해준다

일반적으로 f(n) = O(g(n))으로 표현

n의 값이 클 때, f(n)의 상한이 g(n)의 상수배

 

정의

n>= n0인 모든 n에 대해, 0 <= f(n) <= c*g(n) 을 만족하는 양의 상수 c와 n0가 존재

n이 작을 때는 중요치 않으므로 생략

 

기호가 많이 등장하지만 간단히 말하면

충분히 큰 n에 대해 f(n)보다 항상 이상인 함수 c*g(n)이 존재

 

예) f(n) = n^4 + 2n^2 + 100n + 500 = O(n^4) ≒ n^4 = g(n)

f(n)의 가장 높은 차수인 n^4보다 높은 차수는 다 사용 가능하나(n^5, n^6 등)

f(n)에 근사한 차수 상한을 유효한 값으로 주로 씀

 

오메가 표기법

알고리즘에 대해 하한(lower bound)을 찾게 해주며 f(n) = Ω(g(n)) 으로 표현

n이 충분히 클 때, f(n)의 하한이 g(n)의 상수배

예) f(n) = 100n^2 + 10n + 50 = Ω(n^2)

 

정의

n>= n0인 모든 n에 대해, 0 <= c*g(n) <= f(n) 을 만족하는 양의 상수 c와 n0가 존재

 

세타 표기법(Tight bound)

알고리즘의 평균 수행 시간은 항상 하한과 상한 사이에 존재

상한(O)과 하한(Ω)이 같다면 세타(θ) 표기법 역시 같은 증가율

 

예) f(n) = 10n^2+n 일 때, 상한은 O(n^2), 하한은 Ω(n^2)

최선의 경우, 최악의 경우의 증가율이 동일하므로

결과적으로 tight bound도 이와 동일 θ(n^2)

일반적으로 f(n)의 최고차항의 상수를 뗀 값을 θ라 부름 = n^2

 

θ(g(n)) 정의

n >= n0인 모든 n에 대해, 0 <= c1*g(n) <= f(n) <=c2*g(n)을 만족하는 양의 상수 c1, c2와 n0가 존재

 

 

복잡한 설명 다 떼고 아주 간단히 정리하면

해당 알고리즘을 수행하여야 할 횟수 n, 

그 구조에 따라 알고리즘의 수행 시간을 나타내는 방정식 f(n)

 

함수의 극한과 개념이 같다

 

n이 아주 커질 때,

낮은 차수 항의 크기 증가량은 최고차항에 비해 미미하므로

f(n)의 최고차항의 복잡도가 수행 시간을 판별하는데 유의미하다

 

예) n=1극 (10^48) , f(n) = 2n^2 + 3n

라고 하면 1극의 제곱에 비해 1극에 고작 상수를 곱한 1차항의 크기는 아주 작아서 오차 정도로 보일 뿐이다

 

따라서, n이 아주 커질 때 f(n)와 같은 기울기로 증가하는 그래프를 그릴 수 있게

f(n)의 최고차항과 같은 복잡도인 항 하나(g(n))에

상수 배수(c)만 곱한 식으로 이에 근사한 그래프를 그릴 수 있다.

 

알고리즘에 걸리는 시간, 효율을 구하기 위해 f(n) 전체 항을 구해서 더할 필요 없이

간단하게 c*g(n)만으로 근사한 결과값을 구할 수 있다는 이야기이다.

 

 

점근적 분석 가이드라인

1) 루프: 수행 시간은 루프 내 구문들의 수행 시간(조건문 포함) 곱하기 반복 횟수가 최댓값

for(int i =0; i < n; i++)
{
	// 일정한 시간 c가 걸림
	m += 2;
}

전체 걸리는 시간 = c*n = cn = O(n)

 

2) 중복 루프 : 안쪽에서 바깥쪽 순서로 분석. 전체 수행 시간은 각각의 루프 수행 시간의 곱

// 바깥 루프 n회 실행
for(int i=0; i<n; i++)
{
	// 안쪽 루프 n회 실행
	for(int j=0; j<n; j++)
    {
    	// 일정한 시간 c가 걸림
    	k+=1;
    }
}

전체 걸리는 시간 = c*n*n = c*n^2 = O(n^2)

 

3) 연속된 구문들 : 각 구문의 복잡도를 더하기

// 일정한 시간 c0
x +=1;

// 바깥 루프 n회 실행
for(int i=0; i<n; i++)
{
	// 일정한 시간 c1
	m+=2;
	// 안쪽 루프 n회 실행
	for(int j=0; j<n; j++)
    {
    	// 일정한 시간 c2
    	k+=1;
    }
}

전체 걸리는 시간 = c0 + c1*n + c2*n^2 = O(n^2)

 

4) if-then-else 구문 : 조건문 수행이 오래 걸리는 쪽 시간을 고려하는 게 맞는데 강의에서는 더하는 것을 제시했다

예)

if 구문의 수행 시간 f(n) = 2n^3

else 구문의 수행 시간 g(n) = 3n^4

둘을 더해도 2n^3 + 3n^4

 

n이 아주 커진다면 작은 차수 항은 무시하고 점근선인 O(n^4)로 판정할 수 있게 된다

따라서, 더한다 할지라도 최고차항의 차수가 변하는 게 아니기에 유효하다

 

if(a==0)
{
	// then 부분 상수 c0만큼 시간 소요
	return false; 
}
else
{
	// 상수 c1
	a+=1;
    for(int i=0; i<n; i++)
    {
    	// 상수 c2
    	b+=1
        if(!list[n].equals(otherList[n]))
        	// 상수 c3
        	return false;
    }
}

전체 걸리는 시간 = c0 + c1 + (c2 + c3)*n = O(n)

 

5) 로그형 복잡도

알고리즘 문제의 크기를 일부(보통 1/2) 줄이는데 일정한 시간이 걸린다면 O(logn)

for(int i=1; i<=n; )
{
	i *= 2;
}

i의 값이 1씩 더해지는 게 아니라 매번 2배가 되는 루프

n=1000일 때,

i = 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024(1000을 초과해 루프를 빠져나옴)

log2(1000) = 9.96578428…

따라서 총 10번만 돈다

 

예) 이진 검색: 사전(n페이지)에서 단어 찾기

사전의 중앙 (n/2 페이지) 찾기

단어가 중앙의 왼쪽인가? 오른쪽인가?

 

그 절반 페이지 찾기(왼쪽 = n/4, 오른쪽 = n*3/4)

단어가 그 페이지의 왼쪽인가 오른쪽인가?

.

.

.

해당 단어를 찾을 때까지 과정 반복(트리)

이를 응용하여 특정 숫자를 기준으로 트리 형태로 정렬하기도 한다

 

 

예를 들어 36이라는 숫자를 찾으려 할 때

배열에 저 숫자들을 다 넣어뒀다면 찾기 시작하는 인덱스(보통 처음이나 끝)로부터 36이 나올 때까지 찾아야 한다.

하지만 트리 형태로 규칙성 있게 구성해뒀다면 층(f)에 따라 2^f-1 = 2^3-1(예시에서는 3층)로 끝나서 훨씬 적은 수로 검가능