안녕하세요, caution입니다.
부스트캠프도 끝났고 일본여행도 갔다왔겠다 할 일 없는 백수는 오늘부터 자료구조 공부를 시작합니다.
책은 파이썬과 함께하는 자료구조의 이해 를 선택했습니다. 그 이유는 파이썬 코드가 의사코드와 유사해서 자료구조와 알고리즘을 익히는데 도움이 될 것이라고 생각해서입니다.
비교적 얇은 책이니 후루룩 읽고 후루룩 흡수해보겠습니다.
그럼 시작합니다!
01 자료구조를 배우기 위한 준비
1.1 자료구조와 추상데이터 타입
Q. 자료구조 란?
A. 일련의 동일한 타입의 데이터를 정돈하여 저장한 구성체
Q. 왜 데이터를 정돈하는가?
A. 프로그램에서 저장하는 데이터에 대해 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행하기 위해서 이다. 그래서 자료구조를 설계할 때에는 데이터와 관련된 연산들을 고려하여 설계해야 한다.
Q. 추상데이터 타입 ?
A. Abstract Data Type : 데이터와 데이터에 대한 추상적인 연산들의 관계를 나타내는 개념. 추상적이기 때문에 구체적으로 구현되는 방식을 적은 것은 아니다. 자료구조는 이를 실제 프로그램으로 구현한 것을 의미한다.
자주 사용되는 자료구조로는 리스트, 연결리스트, 스택, 큐, 트리, 해시테이블, 그래프 등이 있으며 이를 사용하여 특정 문제를 해결하기 위한 알고리즘 을 설계할 수 있다. 이를 위해서는 데이터 X 연산 의 관계를 개념적으로 정립하는 추상데이터 타입을 만들고 이를 기반으로 자료구조를 만들어야 효율적인 알고리즘의 설계가 가능하다.
추상 데이터 타입 -> 자료구조 -> 알고리즘
1.2 수행시간의 분석
Q. 자료구조의 효율성은 어떻게 측정할 수 있을까?
A. 연산의 수행시간으로 효율성을 측정할 수 있다. 이는 알고리즘의 성능을 측정하는 방식과 동일하다.
- 시간복잡도 : 알고리즘이 실행되는 동안에 사용된 기본적인 연산 횟수를 나타낸다.
- 공간복잡도 : 알고리즘이 수행되는 동안 사용되는 메모리 공간의 크기를 나타낸다.
대부분의 경우 시간복잡도를 사용하여 효율성을 측정한다. 그 이유는 주어진 문제를 해결하기 위한 대부분의 알고리즘이 비슷한 크기의 메모리 공간을 사용하기 때문이다.
Q. 왜 실제 측정된 시간이 아니라 횟수로 시간 복잡도를 계산하는가?
A. 실제 측정된 시간으로는 객관적으로 평가하는데에 그 한계가 있다. 사용되는 언어, 컴퓨터의 성능 등 얼마든지 달라질 수 있기 때문이다.
시간복잡도 분석 방법
- 최악경우 분석 : 어떤 입력이 주어지더라도 수행시간은 이 이상을 넘지 않는다.
- 평균경우 분석 : 입력이 무작위로 주어진다고 가정했을 때(균등분포)의 평균 시간
- 최선경우 분석 : 가장 빠른 수행시간을 분석하는 것으로 최적 알고리즘 을 찾는데 활용한다.
출퇴근을 한다고 가정했을 때, 지하철역까지는 5분, 지하철을 타면 회사까지 20분, 엘리베이터를 타고 사무실 까지 가는데 5분이 걸린다.
최선 경우는 집을 나와서 바로 지하철을 타고 바로 엘리베이터를 탔을 때 30분이 걸리는 경우이다. 최악경우는 지하철을 눈 앞에서 놓치고, 엘리베이터에 사람이 너무 많아서 다음 엘리베이터를 기다려야 하는 경우이다. 지하철 배차가 5분이고, 엘리베이터를 타는데 추가로 5분이 소요되었다면 최악경우는 10분이 추가된 40분이다. 평균시간은 최선과 최악의 중간으로 가정했을 때 35분이 된다.
흔히들 “회사에 지각하지 않으려면 늦어도 40분 전에는 출발해야 한다.”라고 최악의 경우를 말하는 것처럼, 알고리즘의 수행시간도 대부분 최악 경우로 표현한다.
1.3 수행시간의 점근표기법
수행시간 : 입력크기(N)이 주어졌을 때 알고리즘이 수행하는 기본 연산 횟수
이는 대부분 다항식으로 표현될 수 있으며 이 다항식을 다시 함수로 표현하기 위해서 점금표기법 이 사용된다.
대표적인 점근 표기법
- O : Big-Oh 표기법
- Ω : Big-Omega 표기법
- 𝛩 : Theta 표기법
Big-Oh(O) 표기법
c > 0 이며, 모든 N > N₀에 대해서 f(N) ≤ c*g(N) 이 성립하면 f(N) = O(g(N)) 이다.
O-표기가 나타내는 수행시간은 상한시간, 즉 최악 경우를 나타낸다.
EX) 어떤 알고리즘의 수행시간이 2N² + 3N + 5 라면?
- 양의 상수 c = 4
- g(N) = N²
- 모든 N에 대해 2N² + 3N + 5 ≤ 4N² 이 성립한다.
- 따라서 2N² + 3N + 5 ≤ O(N²)
양의 상수 c를 정할 때 그 값을 만족하는 가장 작은 값을 구하려하지 않아도 된다. 상수가 얼마냐가 중요한 것이 아니라, f(N) ≤ c * g(N) 을 성립하는 양의 상수이기만 하면 된다.
물론 2N² + 3N + 5 ≤ O(N³) 도 성립하고, 2N² + 3N + 5 ≤ O(2ᴺ) 도 성립하지만 가장 차수가 낮은 함수를 선택하는 것이 바람직하다.
앞선 예에서 출퇴근 시간은 최대 40분 소요되는데, 이를 “100시간 내로는 간다.”도 맞는 말이고 “10시간은 안 걸린다.”도 맞는 말이지만, “1시간 넘게는 안 걸린다.”가 더욱 정확한 표현이기 때문이다.
O-표기를 찾기 위해 직접 양의 상수 c 와 N₀를 계산해서 g(N)을 찾을 수도 있지만, 간단하게는 다항식에서 최고 차수 항만을 취한뒤 그 항의 계수를 제거하여 g(N)을 정하면 된다.
Big-Omega(Ω) 표기법
c > 0 이며, 모든 N > N₀ 에 대해서 f(N) ≥ c*g(N) 이 성립하면 f(N) = Ω(g(N)) 이다.
와. O-표기법과 비교연산자의 방향만 바뀌었다. O-표기법은 최악의 경우를 나타내고, Ω-표기법은 최선의 경우(하한)를 나타내는 걸 알 수 있다. 마찬가지로 양의 상수 c의 값은 중요하지 않고 최고 차수 항만을 취하여 g(N)을 정할 수 있다.
EX) 어떤 알고리즘의 수행시간이 2N² + 3N + 5 라면?
- 양의 상수 c = 1
- g(N) = N²
- 모든 N에 대해 2N² + 3N + 5 ≥ N² 이 성립한다.
- 따라서 2N² + 3N + 5 ≥ Ω(N²)
마찬가지로 정확한 표현을 나타내기 위해서 g(N)을 선택할 때에는 정의를 만족하는 가장 높은 차수의 함수를 선택하는 것이 바람직하다. 2N² + 3N + 5 ≥ 0 또한 성립하고, 2N² + 3N + 5 ≥ Ω(N) 또한 성립하지만 2N² + 3N + 5 ≥ Ω(N²)을 선택하는 것이 좋다.
Theta(𝛩) 표기법
c₁, c₂ > 0 이며, 모든 N > N₀ 에 대해서 c₁g(N) ≥ f(N) ≥ c₂g(N) 이 성립하면 f(N) = 𝛩(g(N)) 이다.
𝛩-표기는 수행시간의 O-표기와 Ω-표기가 동일한 경우에 사용한다. 앞선 예에서 알고리즘의 수행시간은 2N² + 3N + 5 였는데, O(N²), Ω(N²)이므로 𝛩(N²) 이다. 이는 곳 이 알고리즘의 수행시간이 N²과 유사한 증가율을 가지고 있다는 뜻이다.
자주 사용되는 O-표기
알고리즘의 수행시간은 주로 O-표기를 사용하며, 보다 정확한 표현을 위해서 𝛩-표기를 사용하기도 한다.
| O-표기 | 이름 |
|---|---|
| O(1) | 상수 시간 |
| O(logN) | 로그 시간 |
| O(N) | 선형 시간 |
| O(NlogN) | 로그선형시간 |
| O(N²) | 제곱 시간 |
| O(N³) | 세제곱 시간 |
| O(2ᴺ) | 지수 시간 |
O(1) < O(logN) < O(N) < O(NlogN) < O(N²) < O(N³) < O(Nᵏ) < O(2ᴺ)
1.4 파이썬 언어에 대한 기본적인 지식
클래스와 메소드
파이썬 언어는 객체지향 프로그래밍 언어로써 Class를 선언하여 객체에 데이터를 저장하고 Method를 선언하여 객체들에 대한 연산을 구현한다.
class Student:
def __init__(self, name, id):
self.name = name
self.id = id
def get_name(self):
return self.name
def get_id(self):
return self.id
best = Student('caution', 101)
print(best.get_name())
print(best.get_id())
-
def 를 통해 함수를 정의할 수 있다. 클래스 내부에 정의하면 메소드, 클래스 외부에 정의하면 함수이다.
-
객체 생성자는 클래스 내부에 선언하며 init 으로 정의한다.
-
self 는 클래스 인스턴스를 의미하며 모든 메소드의 첫 번째 인자로 self를 받는다.
- 인스턴스 인자의 이름을 self 대신 다른 이름을 써도 무방하지만 관례상 self를 쓴다.
-
self를 쓰지만 실제 함수를 호출할때는 이를 생략한다.
- best.get_name() => get_name(best)
리스트 선언 및 관련 연산 수행
a = [] # 비어있는 리스트 a 선언
b = [None] * 10 # 크기가 10이고 각 원소가 None으로 초기화된 리스트
c = [40, 10, 70, 60] # 크기가 4이고 4개의 정수로 초기화된 리스트
print(c[0]) # 40
print(c[-1]) # 60
c.pop() # 리스트 마지막 항목인 60 제거
c.pop(0) # 리스트 0번째 항목인 40 제거
c.append(90) # 리스트 맨 뒤에 90 추가
print(len(c)) # len() -> length 3
- 리스트는 동적 배열로 새 항목이 추가되거나 삭제되는 자동으로 리스트의 크기를 조절한다. *
조건문
if 조건식:
명령문
elif 조건식:
명령문
else:
명령문
반복문
for 조건식 in 리스트:
명령문
for 변수 in range(N):
명령문
while 조건식:
명령문
- range(start, N, step)
- range(10) : 0…9
- range(5, 10) : 5…9
- range(0, 10, 2) : 0, 2, 4, 6, 8
- range(10, 1, -1): 10, 9, … 2
난수값을 가지는 배열 만들기, 시간 측정하기
import random
import time
random.seed(time.time()) # 난수 생성을 위한 초기값은 현재 시간으로 한다.
a = []
for i in range(100): # 100번 난수를 생성해서 넣을거양
a.append(random.randint(1, 1000)) # 1과 1000 사이의 난수를 생성하여 배열에 추가
start_time = time.time()
# 여기에 측정이 필요한 알고리즘을 넣는다.
print("-- %s second ---", (time.time() - start_time))
내장 함수
- ord(‘문자’) : 문자의 Unicode 값을 리턴
- list(reversed(리스트)) : 역순으로 된 리스트를 리턴한다.
- 리스트.revers() : 리스트를 역순으로 만든다.
lambda
함수의 이름도 return 도 없이 수행되는 함수로, 간단한 함수를 대신할 수 있다.
lambda 인자(arguements): 수행식(expression)
filter() 혹은 map() 함수의 인자로 많이 사용된다.
lambda와 filter, map
a = [1, 5, 4, 6, 8, 11, 3, 12]
even = list(filter(lambda x: (x%2 == 0), a))
print(even) # [4, 6, 8, 12]
ten_times = list(map(lambda x: x * 10, a))
print(ten_times) # [10, 50, 40, 60, 80, 110, 30, 120]
b = [[0,1,8], [7,2,2], [5,3,10], [1,4,5]]
b.sort(key = lambda x: x[2])
print(b) # [7, 2, 2], [1, 4, 5], [0, 1, 8], [5, 3, 10]
1.5 순환 : 재귀호출
함수의 실행 과정 중 스스로를 호출하는 것을 말한다. 팩토리얼, 조합을 계산하기 위한 식의 표현, 무한한 길이의 숫자 스트림 만들기, 트리 자료구조, 프랙털 등의 기본 개념으로 사용한다.
무한 호출을 방지할 수 있도록 스스로의 호출을 중단시킬 수 있는 조건문을 넣어주어야 한다.
- 기본 case : 더 이상 스스로를 호출하지 않는 부분
- 순환 case : 스스로를 호출하는 부분
무한 호출을 방지하기 위해 선언한 변수 혹은 수식의 값이 호출이 일어날 때마다 순환 case에서 변동되어 최종적으로는 if-문의 조건식에서 기본 case를 실행하도록 짜야 한다.
def recurse():
print(' *')
recurse()
recurse() # RecursionError가 발생한다.
def recuser(count):
if count <= 0: # 0보다 작거나 같을 경우 .을 찍어준다. 이 경우가 기본 case
print('.')
else: # 0보다 클 경우 : 순환 case
print(count, ' *') # count와 *을 찍어준다.
recurse(count-1) # count - 1 을 인자로 자기자신을 호출한다.
recurse(5)
팩토리얼 예제
1) 순환으로 풀기
def factorial(n):
if n <= 1:
return 1 # 기본 case
else:
return n*factorial(n-1) # 순환 case
print(factorial(4))
2) 반복문으로 풀기
factorial = 1
for i in range(1, 5):
factorial *= o
print(factorial)
반복문을 이용한 계산은 함수 호출로 인해 시스템 스택을 사용하지 않으므로 순환을 이용한 계산보다 간단하며 메모리도 적게 사용한다.
함수의 마지막 부분에서 순환하는 것을 꼬리 순환 이라고 하며, 이는 반복문으로 변환하는 것이 수행 속도와 메모리 사용 측면에서 효율적이다. 하지만 모든 꼬리 순환을 반복문으로 바꾸기 어렵거나 적합하지 않은 경우도(트리 전체 탐색 등) 존재한다.
트리 탐색 예제
섬의 구조가 트리 형태로 연결되어 있다고 할 때, 이 나라의 관광청에서는 모든 섬을 방문할 수 있는, 순서가 다른 3 개의 관광코스를 만들었다.
- A 코스 : 시작 섬을 관광하고, 왼쪽 섬으로 관광을 진행한다. 왼쪽 방향의 모든 섬을 방문하면 오른쪽 섬을 관광한다.
- B 코스 : 시작 섬은 관광하지 않고, 왼쪽의 모든 섬 관광을 진행하고 나서 시작 섬을 관광한다. 이후에 오른쪽 섬의 관광을 진행한다.
- C 코스 : 시작 섬은 관광하지 않고, 왼쪽의 모든 섬 관광을 진행하고 오른쪽의 모든 섬 관광을 진행한다. 이후 시작 섬을 관광한다.
class Island:
def __init__(self, name, left=None, right=None):
self.name = name
self.left = left
self.right = right
def initMap():
n1 = Island('H')
n2 = Island('F')
n3 = Island('S')
n4 = Island('U')
n5 = Island('E')
n6 = Island('Z')
n7 = Island('K')
n8 = Island('N')
n9 = Island('A')
n10 = Island('Y')
n11 = Island('T')
n1.left = n2
n1.right = n3
n2.left = n4
n2.right = n5
n3.left = n6
n3.right = n6
n4.left = n7
n4.right = n8
n5.left = n9
n7.right = n10
n9.right = n11
return n1
def A_course(n):
if n is not None:
print(n.name, '->', end='') # 섬 방문
A_course(n.left) # 왼쪽 섬 방문
A_course(n.right) # 오른쪽 섬 방문
def B_couser(n):
if n is not None:
B_course(n.left) # 왼쪽 섬 방문
print(n.name, '->', end='') # 섬 방문
B_course(n.right) # 오른쪽 섬 방문
def C_couser(n):
if n is not None:
C_course(n.left) # 왼쪽 섬 방문
C_course(n.right) # 오른쪽 섬 방문
print(n.name, '->', end='') # 섬 방문