[엘리스 AI 트랙 2기] 2주차-자료구조(06/29)

자료의 출처는 '엘리스 AI 트랙 2기 (https://aitrack.elice.io/)' '자료구조' 강의이며, 학습 후 정리한 내용입니다.

⚡️올바르지 않은 내용이 있을 경우 댓글로 남겨주시면 감사하겠습니다.⚡️

---

실습

1. 자료구조란?

01. 자료구조의 의미

자료구조란?

자료를 저장하는 구조로, 여러 가지 종류가 있으며 저장된 자료에 대해 접근하는 방법 등의 차이가 존재

 

형태에 따라 장단점이 존재하며 구현하고자 하는 프로그램의 성능을 고려하여 알맞은 자료구조를 선택

 

프로그램에 필요한 자료를 효율적으로 담기 위해 자료구조를 배우며,

프로그램에서 특정 알고리즘을 구현하기 위해 적절한 자료구조를 사용해야 좋은 성능을 낼 수 있다.

02. 추상적 자료형

추상적 자료형이란?

자료형: 

자료형은 어떤 자료가 식별되는 방법을 정의하고 자료에 적용할 수 있는 연산을 결정한다.

자료를 특정 분류에 따라 올바르게 표현하기 위한 정의와, 그구현이 바로 자료형

 

자료형의 중요성 - 값의 해석 방법 명시

65

예를 들어, 65라는 자료가 있다.
컴퓨터는 이 자료가 수를 나타내는 65인지, 아니면 알파벳 'A' 를 나타내는 값인지 자료형을 모르는 경우에는 해석할 수 없다.

 

자료형의 중요성 - 연산 방법 제공

(컴퓨터는 내부적으로 unicode라고 불리는 숫자를 문자에 대입하는 방식으로 각 문자를 식별하고, 65는 'A'에 해당)

또, 수를 나타내는 자료형은 덧셈, 뺄셈 등을 비롯한 연산이 가능

 

추상적 자료형:

자료를 담는 방법과, 자료에 대한 연산에 대한 정의가 담긴 것, 구현 방법은 정의되어 있지 않다.

추상적 자료형은 구현 방법을 명시하고 있지 않다는 점이 특징

 

그릇을 추상적 자료형이라고 한다면, 그릇이 보관하는 자료와, 그 자료에 해당하는 연산의 정의를 포함해야 한다.

 

            자료                                                           연산

그릇은 음식을 보관하고, 그릇에 담긴 음식을 먹을 수 있다.

 

이때 음식을 어떻게 먹을 수 있는지, 즉 어떻게 자료에 접근할 수 있는지는 주어지지 않는다.

 

추상적 자료형과 자료구조

'그릇' 이라는 추상적 자료형이 있고,

그릇에 음식을 어떻게 담을 것인지, 그릇을 이용하여 어떻게 음식을 먹을 수 있는지 명확히 구현된 것을 자료구조라고 할 수 있다.

 

정리

추상적 자료형: 자료들과, 그 자료들에 대한 연산들을 개념적으로 정의만 한 것

자료구조: 자료를 저장하는 방법과 자료에 적용할 수 있는 연산을 구체적으로 제공한것

추상적 자료형을 구체적으로 구현한 결과 => 자료구조

03. 배열과 연결 리스트

리스트(List)

리스트라는 이름의 추상적 자료형이 있다.

 

리스트가 담는 자료

순서가 존재하며, 일렬로 나열된 값들이 들어있다.

 

리스트가 담는 자료에 적용되는 연산

조회 : 임의의 위치의 자료가 무엇인지 알아본다.

삽입 : 임의의 위치에 자료를 추가한다.
삭제 : 임의의 위치의 자료를 제거한다.

 

이외에도 다양한 연산이 있다.

# 리스트라는 추상적 자료형을 구현한 대표적인 두 가지 자료구조: 배열, 연결 리스트

배열(Array)

리스트라는 추상적 자료형을 구현한 대표적인 예시가 바로 '배열'이다.

(Python에서는 배열을 리스트라는 이름으로 제공한다.)

 

배열 - 조회

배열에 저장되는 값들은 순서를 나타내는 번호를 가진다.

이번호를 인덱스라고 부른다.

인덱스는  1이 아닌 0부터 시작하며, 100개의 인덱스가 존재할 때, 인덱스는 0~99까지 존재한다.

배열내의 특정 순서의 값을 조회하고자 할 때 단번에 찾아낼 수 있다.

5번 인덱스의 값은? 2

배열 - 삽입

자료를 추가할 땐 조금 번거롭다.
새로운 자료가 추가되면서, 자료들의 순서를 변경해주어야 하기 때문이다.

3번 인덱스에 10을 추가하자.

 

우선, 새로운 자료가 들어갈 공간을 마련해주어야 한다.

배열에 들어갈 자료가 하나 늘었으므로 공간도 하나 더 만들어준다.

추가될 자료가 들어갈 공간을 비워주기 위해 기존 자료들은 한 칸씩 밀려나게 된다.

마련된 빈 자리에 추가될 값을 넣어준다.

배열 - 삭제

자료를 제거할 때는 이와 반대로 진행하면 된다.

제거할 인덱스의 자료를 비운다.

자료가 줄어들었으므로, 빈자리를메꾸기위해자료들이한칸씩당겨진다.

배열이 담고 있는 자료가 하나 줄었으므로 남는 공간도 제거한다.

연결 리스트(Linked List)

배열은 각 자료에 인덱스를 붙여 저장하는 반면,
연결 리스트는 여러 개의 '노드'를 저장하는 방식으로 구현한다.

노드는 자료와 포인터를 가진다. 

자료는 저장하는 값 자체를 의미하고, 포인터는 자신의 다음 순서의 노드를 가리킨다.

연결 리스트 단점: 조회

연결 리스트 장점: 자료의 추가, 삭제

 

인덱스를 이용하여 절대적인 순서를 표현하는 배열과는 달리,

연결 리스트는 자신의 다음 노드를 가리키는 상대적인 순서를 표현한다.

연결리스트 - 조회

이러한 특성 때문에, 연결 리스트에서 특정 위치의 자료를 찾는 것이 번거롭다.

 

배열은 찾는 자료의 위치와 관계없이 항상 단번에 값을 찾을 수 있지만,
연결 리스트는 찾는 자료의 위치가 시작점으로부터 멀수록 연산 횟수가 많아진다.

 

3번째 값의 자료는? 2

연결 리스트 - 삽입

조회 연산과 마찬가지로 연결 리스트 상에서 n번째 위치를 찾아야 하는 과정은 동일

3번째 위치에 10을 추가하자

추가할 위치의 이전 노드의 포인터를 새로운 노드로, 새로운 노드의 포인터를 이전 노드가 가리키던 노드로 설정한다.

연결 리스트 - 삭제

4번째 위치의 자료를 제거하자

제거할 노드의 이전 노드의 포인터가 제거할 노드가 가리키던 노드를 가리키도록 설정

배열 vs. 연결리스트

	배열	연결리스트
장점	특정 위치의 자료 탐색	자료의 삽입과 삭제
단점	자료의 삽입과 삭제	특정 위치의 자료 탐색

배열과 연결리스트의 장단점이 서로 교차한다.

리스트(추상적 자료형): 값들이 일렬로 저장되어 있으며 리스트 연산을 제공

리스트 (추상적 자료형)
값들이 일렬로 저장되어 있으며 리스트 연산을 제공
배열	구현	연결 리스트
일렬로 저장된 값들이 인덱스라는 번호를 가진다. 특정 위치의 자료를 탐색하는 데 유리하다.		일렬로 저장된 값들이 노드의 형태로 저장되어 있다. 각 노드는 자신의 다음 순서의 노드를 가리키며 자료의 삽입, 삭제에 유리하다.

04. 자료구조의 구현 방법

자료구조의 구현 방법

자료구조는 추상적 자료형에 명시된 표현 및 연산 방법을 구현한다.

 

객체지향 프로그래밍에서 추상적 자료형은 인터페이스

자료구조는 클래스로생각할수있다.

 

자료구조를 만드는 데에는 클래스가 탁월하다.

클래스가 갖고 있는 '필드'(멤머변수)가 자료에 해당하고, '메서드'가 자료에 적용할 수 있는 연산이다.

 

인터페이스: 객체지향 구조에서 추상 메서드만으로 이루어진 설계용 클래스로,

구현 부분이 비어있는 메서드를 추상 메서드라고 하며 상속받는 클래스에서 이를 구현하여 사용한다.

즉, '리스트'라는 인터페이스에는 "삽입과 삭제를 지원해야 한다"라는 명세만 주어지고

실제 동작 부분은 리스트를 상속받은 배열 클래스, 연결 리스트 클래스에서 구현

class MyInterface(metaclass=ABCMeta) : 추상 클래스로 만들기 위한 메타클래스 정의(Abstract Class Meta) 
	@abstractmethod 추상 메서드임을 나타내는 데코레이션
	def func() :
    	pass

(Java 등 다른 언어와는 달리 Python에서는 인터페이스 기능을 직접 지원하지는 않으므로 별도의 클래스를 만들어 사용)

 

자료구조의 구현 예시

import queue
q = queue.Queue()

파이썬 기본 라이브러리 중, '큐'라는 자료구조를 구현한 Queue 클래스도 있다.

큐 자료구조의 자료 저장 및 연산 방법을 갖추고 있다.

 

# 컨테이너란?

리스트, 튜플, 딕셔너리 등을 비롯한 하나 이상의 요소를 담을 수 있는 것.

내부적으로 Container 클래스를 상속받은 sub class에 해당

문제 해결하기

좋은 해법인지 생각해보기

좋은 해법힌지 판단하는 기준은 여러 가지가 있다.

(코드가 간결한가? 얼마나 빠른가? 리소스를 얼마나 차지하는가? 구현 시간이 짧은가?...)

 

수행하는 명령의 수가 적을수록 시간이 덜 걸린다

시간 복잡도

알고리즘이 문제를 해결하는 데 걸리는 시간을 정량화하여 나타낼 수 있는 방법

일반적으로, 문제에서 주어지는 최악의 경우에 대한 소요 시간을 나타내는 데 사용

(최악의 경우: 문제 해결 시 가장 오래 걸리는 경우)

 

Big-O Notation(𝑂()): 최악 조건의 시간 복잡도를 의미

자료구조를 공부해야하는 이유

작성하고자 하는 프로그램의 목적을
가장 효율적으로 달성할 수 있는 자료구조를 사용하기 위해서

 

각 자료구조의 특성과 동작 방법을 제대로 이해하고 있어야 한다.

문재 해결

1. 문제를 파악한다. 
   (=어떤 자료를 담을지, 자료에 어떤 의미가 있는지 파악)
2. 자료구조에 필요한 기능을 파악한다. 
   ( = 자료를 어떻게 사용하는지 파악)
3. 문제를 효율적으로 해결하는 자료구조를 설계 및 사용한다. 
   (=목적에 맞는 자료 구조로 문제를 해결)

조회 활용하기

연결리스트

연결 리스트의 특정 노드를 삭제하기 위해서 그 특정 노드에 접근하는 과정이 필요

연결 리스트의 특성에 의해 특정 원소에 접근하기 위해서는 시작 원소부터 하나씩 따라가야 한다.

연결 리스트는 어떤 노드를 삭제하기 위해서 그 노드의 이전 노드와 다음 노드가 무엇인지 알고 있어야 하기 때문

딕셔너리 활용

이 단점을 개선하기 위해 연결 리스트 내에 딕셔너리를 두고, 모든 노드들의 정보를 저장하고 있도록 한다.

 

딕셔너리는 내부적으로 해시 테이블이라는 자료구조로 동작하며,

어떠한 key에 대한 value를 𝑂(1)의 시간 복잡도로 접근할 수 있다.

 

이중 연결 리스트 활용

삭제할 노드를 알아냈다고 해서 끝이 아니다.

삭제할 노드의 다음 노드와 이전 노드를 알아야 하는데,

현재로서는 이전 노드에 접근할 방법이 없다.

노드에 포인터가 두개가 있고
각각 이전 노드와 다음 노드를 가리키는

형태의 연결 리스트를 이중 연결 리스트라고 한다.

이중 연결 리스트를 이용하여 노드를 간편하게 삭제할 수 있다.

조회

배열이든 연결 리스트든,

번호가 주어졌을 때 해당 번호가 몇 번째인지 알기 위해서는

맨 첫 번째 주문부터 하나씩 확인해봐야 한다.

 

배열이 조회가 빠른 이휴

배열의 요소들은 컴퓨터에서 물리적으로 가깝기 때문이다.

연결 리스트는 각각 별도의 객체들을 임의로 연결하는 방식으로 구현되지만

배열의 경우, 각 요소들이 컴퓨터 내부에서 매우 가깝게 위치하고 있다.

자료를 메모리에 저장하는 방법 - 배열

메모리 상 인접하고 있으니까, 0 번쨰 인덱스에서 1번째 인덱스로 바로 옆칸으로만 이동하면 된다 -> 인덱스 간 이동이 매우 빠르다! 

자료를 메모리에 저장하는 방법 - 연결 리스트

포인터에 의해 마음대로 엮어준 것 뿐이다. 별도의 객체를 찾으러 나가기 때문에 배열보다 오래걸릴 수 있다.

 

따라서 전체 요소를 순회하는 연산 또한 배열이 더 유리하다.

 

주문 관리 시스템이 처리하는 주문의 양이 같더라도, 주문조회가 많을 때, 적을 때 유리한 자료구조가 각각 있다.

알고리즘이 같더라도 데이터의 처리에 따라 성능이 다르다.

따라서 데이터의 입출력과 문제 상황을 잘 파악하여 적절한 자료구조를 선택해야 한다.

---

해쉬 테이블

해쉬 테이블

각 데이터(value)를 고유한 key에 대응하도록 저장하는 개념

배열의 index를 key로 이용하기

장점
(운 좋으면) 자료의 쓰기 연산이 빠르다.

자료의 읽기 연산이 빠르다.

 

단점

“자료가 없다”를 표현하는 것이 쉽지 않다. 공간이 지나치게 낭비될 수 있다.

key와 value를 각각 배열에 저장하기

장점

공간의 낭비가 없다.

자료가 없는 경우를 표현할 수 있다.

단점

자료의 읽기(조회) 연산이 느리다.

자료의 쓰기(입력 등) 연산도 느리다.

해쉬(hash)

해시란 임의의 데이터에 해시 함수를 이용하여
고정된 길이의 데이터(문자열 등)으로 변환하는 것을 의미

 

변환하는 과정 자체를 해싱(hashing), 변환된 값을 해시 값(hash value) 라고도 부른다.

 

해시를 이용하여 Key-Value Store를 구현할 수 있다.

 

해시를 이용하여 구현된 Key-Value Store를 해시 테이블(Hash Table),

또는 딕셔너리(Dictionary)라고 한다.

해시 함수의 충돌: 비둘기집의 원리

좋은해시함수는중복되는해시값이최대한없도록하여 되도록 충돌이 발생하지 않는 함수이다.

그러나 해시 함수의 반환값의 경우의 수는 유한하고,

입력값의 경우의 수는 무한하기 때문에 비둘기집의 원리에 의해 충돌은 어쩔 수 없이 발생한다.

해시 - 충돌 해결 방법: 개별 체이닝

Key-Value Store의 각 인덱스를 '연결 리스트'로 만들어서 동일한 인덱스의 값들을 연결하는 방법이다.

해시 - 충돌 해결 방법: 오픈 어드레싱

충돌이 발생했을 때 자료를 저장하기 위해 빈 공간을 탐색하는 방식

따라서 모든 원소가 자신의 해시 값과 일치하는 인덱스에 저장된다는 보장은 없다.

위 예시에서는 Dodo 자료를 저장하기 위해 가장 가까운 빈 공간을 탐색하였고, 그 결과 인덱스 2에 저장하였다.

 

오픈 어드레싱에서 빈 공간을 찾는 방법은 여러 가지가 있지만

가장 간단하고 대표적인 방법은 '선형 탐사 방식'이다.

앞서 살펴 본 것 처럼,원래 인덱스의 다음 인덱스부터 탐색하여 가장 가까운 빈 공간을 찾는 방법

 

Python에서는 딕셔너리의 해시 값 충돌이 발생하였을 때 오픈 어드레싱 방식으로 해결하도록 구현되어 있다.

---

2. 스택과 큐

01. 스택, 큐의 개념

대표적인 자료구조의 예시

선형 구조		비선형 구조
스택 (Stack)	큐 (Queue)	트리 (Tree)	그래프 (Graph)

선형구조: 자료가 순서를 가지고 연속되어 있음

비선형 구조 : 선형 구조에 해당하지 않는 자료구조

스택

한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조  스택이 지원하는 연산 목록  • push: 스택에 자료를 넣는연산 • pop: 스택에서 자료를 빼는연산 • top: 스택의 가장 위에 있는 자료를 반환하는 연산  • empty: 스택이 비어있는지 여부를 반환하는 연산

나중에 들어간 자료가 먼저 출력되기 때문에 Last In First Out(LIFO)(후입선출) 자료구조라고도 한다. 

파이썬의 리스트는 append, pop 등의 연산을 지원하므로 리스트를 이용하여 스택을 구현할 수 있다.

큐

입구와 출구가 각각 한 쪽 끝에 존재하는 자료구조  큐가 지원하는 연산 목록  • push:큐에 자료를 넣는 연산 • pop: 큐에서 자료를 빼는 연산 • front: 큐의 가장 앞에 있는 자료를 반환하는 연산  • back: 큐의 가장 뒤에 있는 자료를 반환하는 연산  • empty:큐가 비어있는지 여부를 반환하는 연산

선형 자료구조이기 때문에 배열을 이용하여 구현이 가능하기는 하지만 여러 문제가 존재한다.

배열로 구현된 크기가 6인 큐가 있다.
head와 rear는 인덱스를 나타내며, 큐에 포함되어있는 내용은 head 이상 rear 미만의 인덱스들이다.

 

 

 

push - rear 위치에 자료를 추가하고 rear를 1 증가시킴

pop - head 위치의 자료를 제거하고 head를 1 증가시킴

 

마지막 그림의경우 크기가 6인 큐에 자료가 4개 들어있고, 빈 공간이 2개 있는 상태

그러나, 위의 경우에는 rear가 가리키는 인덱스가 6이기 때문에 자료를 추가할 수 없다.

인덱스가 배열의 크기를 초과했기 때문이다.

 

배열로 큐를 구현하였을 때의 문제점을 보완하기 위한 자료구조 => '원형 큐'

원형 큐

원형 큐의 경우, rear나 head가 큐의 끝에 도달하면 큐의 맨 앞으로 보내어 문제를 해결

링크드 큐 (Linked Queue)

연결 리스트로 구현한 큐를 '링크드 큐' 라고 한다.

삽입과 삭제가 제한되지 않는 점과, 크기의 제한이 존재하지 않는 점이 편리

import queue
q = queue.Queue()

큐를 실제로 사용하고자 할 때는 파이썬 기본 라이브러리의 queue 모듈의 Queue 클래스를 사용

정리

스택과 큐는 선형 구조고, 선형 구조는 자료들이 순서를 가지고 연속된 자료구조이다.

스택은 나중에 들어온 자료가 먼저 출력되고, 큐는 먼저 들어온 자료가 먼저 출력된다.

 

파이썬의 리스트(배열)를 사용하여 구현할 때 스택은 간편하게 구현이 가능하지만 큐의 경우는 여러 문제점이 발생

큐를 배열로 구현하였을 때의 문제점을 해결하는 방법은 원형큐,링크드큐 등 존재

스택과큐를실제로사용하고자할때 스택은 그냥 파이썬의 리스트를, 큐는 queue 모듈의 Queue 클래스를 사용

02. 스택, 큐의 의미

스택과 큐의 의미

스택과 큐는 컴퓨터 내에서 중요한 역할을 갖고 있기 때문이다.

그리고 스택과 큐는 가장 기본적인 형태의 자료구조 중 하나이며

스택과 큐로 해결할 수 있는 문제인지 알기 위해서는 스택과 큐의 의미를 알고 있어야 한다.

스택이 활용되는 대표적 예시

콜 스택(Call Stack): 컴퓨터 프로그램에서 현재 실행 중인 함수(서브루틴)을 저장하는 역할

 

스택은 의존관계가 있는 상태를 저장한다.

어떤 일보다 더 먼저 처리되어야 하는 일이 있다면, 스택에 저장할 수 있다.

 

팩토리얼 연산의 정의를 코드로 옮긴 factorial 함수

이 함수는 재귀함수, 즉 자기 자신을 호출하는 함수이다

 

# 𝑛!를 구하기 위해서는 (𝑛−1)!를 먼저 구해야 했던 것처럼 여러 작업들 사이에 의존관계가 있을 때
스택을 이용하여 표현할 수 있다.

큐가 활용되는 대표적 예시

스케줄링(Scheduling)

운영 체제가 프로세스를 관리하는 기법으로
동시에 실행되는 여러 프로세스에 CPU 등의 자원 배정을 적절히 함으로써 성능을 개선할 수 있다.

 

여러프로세스를동시에수행할수있게하기위한기법인

시분할 시스템을 비롯하여 운영체제의 스케줄링 알고리즘은 매우 다양하지만

대체로 '큐'를 기반으로 스케줄링을 관리하고 있다.

 

어떤 작업이 병렬적으로 이루어져도 괜찮을 때, 작업들 사이에 의존관계가 없다면 큐에 저장하여 관리할 수 있다.

정리

스택	큐
어떤 작업이 다른 작업보다 먼저 이루어져야만 하는 경우	여러 작업들이 동시에(병렬적으로) 이루어져도 상관없는 경우
의존관계가 있는 경우	의존관계가 없는 경우

---

3. 트리

01. 비선형구조와 트리

대표적인 자료구조의 예시

선형 구조		비선형 구조
스택 (Stack)	큐 (Queue)	트리 (Tree)	그래프 (Graph)

선형구조: 자료가 순서를 가지고 연속되어 있음

비선형 구조 : 선형 구조에 해당하지 않는 자료구조

그래프

트리는 그래프의 특수한 형태 중 하나이다.

 

정점(vertex)과 간선(edge)으로 이루어져 있는 자료구조

정점(vertex): 자료, 상태 등 뭔가를 담고 있음 (정점은 '노드'라고도 함)

간선(edge): 정점 간의 관계를 나타냄

어떤정점에서간선을통해다른정점으로이동할수있다.
어떤 정점에서 다른 정점으로 이동하기 위해 거치는 모든 정점을 경로라고 한다.

예를 들어 정점 4에서 정점 6으로 이동하는 경로들 중 하나는 4→5→3→6이 될 수 있다.

유향 그래프

그래프의 간선은 방향이 있을 수도, 없을 수도 있다.

위와 같은 그래프에서 정점 1에서 2로 이동할 수 는있지만, 2에서 1로 이동할 수 는없다.

방향이 있는 간선을 포함한 그래프를 유향 그래프라고 한다.

 

사이클

어떤 정점에서 출발하여 자기 자신으로 돌아오는 경로가 있을 수 있다.

이와 같이 처음 시작한 정점으로 다시 돌아오는 경로를 '사이클' 이라고 한다.

예를 들어 3→6→7→3은 사이클이다.

트리

그래프 중 아래의 특별한 성질을 갖는 그래프를 트리라고 한다.

트리의 여러 성질은 다음과 같다.

• 트리의 간선들은 모두 방향성을 갖는다.
• 어떤 정점을 가리키는 정점의 개수는 최대1개이다.
• 어떤 정점에서 다른 정점으로 이동할 수 있는 경로는 1개다.

• 트리는 사이클을 갖지 않는다.

 

트리에서 다른 어떠한 정점도 가리키지 않는 정점을

루트 노드(Root Node) 라고 한다.
정점 1이 루트 노드에 해당한다.
또, 루트 노드로부터의 거리를 깊이라고 한다.

임의의정점𝐴가다른정점𝐵을가리킬때 𝐴를 𝐵의 부모 노드(Parent Node)라고 하고,

𝐵를 𝐴의 자식 노드(Child Node)라고 한다.

예를들어 정점 2는 정점 5의 부모노드이고, 정점3 은 정점 1의 자식노드이다.

가리키는 정점이 없는 정점들을 리프 노드(Leaf Node)라고 한다.

정점 4,5,6,7이 리프노드에 해당

 

트리는 계층적인 구조로 되어 있는 자료구조이다.

운영체제에서 파일을 분류하기 위해 사용하는 디렉터리(폴더)는 트리 구조의 대표적인 예시이다.

이진 트리

각 정점들이 자식 노드를 최대 2개까지만 갖는 트리를 이진 트리라고 한다.

이진 탐색 트리 등 유용하게 활용되는 트리 중에는 대부분 이진 트리를 응용한 것이 많다.

포화 이진 트리

리프노드를 제외한 모든 정점이 항상 자식을 2개씩 갖고 있으면서

모든 리프노드의 깊이가 동일한 트리를 포화 이진 트리라고한다.

포화이진트리의높이를h라고할때, 정점의 개수는 항상 2! − 1개이다.

 

완전 이진 트리

마지막 깊이를 제외하고 모든 정점이 완전히 채워져 있으며,

마지막 깊이의 정점들은 가능한 한 왼쪽에 있는 트리를
완전 이진 트리라고 한다.

또는 포화 이진 트리에서 마지막 깊이의 정점이 오른쪽에서부터 일부 제거된 트리라고 볼 수 있다.

완전 이진 트리의 높이가 h일때
정점의 개수는 2^(h-1)개 이상 2^h − 1개 이하이다.

정 이진 트리

정 이진 트리는 리프노드를 제외한 모든 노드들이

두 개의 자식노드를 갖고 있는 이진트리이다.

즉, 모든 정점은 0개 또는 2개의 자식노드를 갖는다.

02. 트리의 표현 방법

트리의 표현 방법

 class TreeNode :
    def __init__(self) :
        self.left = None
        self.right = None

이진 트리의 각 노드는 왼쪽 또는 오른쪽 자식을 갖고 있으므로 위와 같은 클래스로 표현할 수 있다.

 

완전 이진 트리의 경우, 배열을 이용하여 간단하게 구현이 가능하다.

아래와 같은 완전 이진 트리가 존재 할 때 각 정점에 순서대로 번호를 붙일 수 있다.

어떤 정점의 번호가 𝑛이면 왼쪽자식은2𝑛,오른쪽자식은2𝑛+1이다.

따라서 배열로 완전 이진 트리를 표현할 수 있게 된다.

# index를 2로 나눔으로써 부모에 접근할 수 있다는 것도 완전 이진 트리의 하나의 특성이다! 

0번은 사용하지 않는다.

또, 트리는 그래프의 일종이므로 그래프를 표현할 때 사용하는 인접 행렬, 인접 리스트, 간선 리스트를 사용할 수도 있다.

03. 트리 순회하기

트리 순회하기

트리 순회란 트리의 모든 노드를 방문하는 순서이다.

트리에 들어있는 자료에 접근하기 위해 순회를 해야 한다.

배열, 연결리스트 등 선형구조는 각 자료가 순서를 가지지만

비선형 구조에 해당하는 트리는 정해진 순서가 존재하지 않는다.

 

트리의 모든 노드를 방문하는 순서 두가지 종류: 

DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)

트리 순회하기 - 깊이 우선 탐색(DFS)

1.전위순회 2.중위순회 3.후위순회

 

DFS는 재귀 호출을 사용하는 알고리즘으로,
DFS를 이해하기 위해서는 트리의 재귀적 특성을 알아야 한다.

재귀 호출은 스택의 특성을 이용하므로 스택을 이용한다고 볼 수 있다.

(재귀 호출 사용 않고 스택 구현 방법 있으나 권장 x)

이 트리에서 루트 노드를 제외하면 두 개의 작은 트리가 만들어진다.

이와 같이 기존 트리에서 하위의 트리구조를 서브트리라고 한다.

 

DFS의 세 가지 방법은 정점을 언제 방문하는지에 따라 순서가 달라지며

재귀 호출을 이용한다는 기본적인 개념 자체는 동일

 

전위순회 : 루트방문 → 왼쪽서브트리순회 → 오른쪽서브트리순회

중위순회 : 왼쪽서브트리순회 → 루트방문 → 오른쪽서브트리순회

후위순회 : 왼쪽서브트리순회 → 오른쪽서브트리순회 → 루트방문

전위 순회

전위 순회의 경우 정점을 방문하는 순서

루트 → 왼쪽 → 오른쪽

중위 순회

중위 순회의 경우 정점을 방문하는 순서

왼쪽 → 루트→오른쪽

하위 순회

하위 순회의 경우 정점을 방문하는 순서

왼쪽 →오른쪽→루트

트리 순회하기 - 너비 우선 탐색(BFS)

너비 우선 탐색의 경우 정점을 방문하는 순서

트리(그래프)의 BFS는 큐 자료구조를 이용하여 구현한다.

현재 정점과 이웃한 정점일수록 먼저 방문해야 하므로

FIFO 자료구조인 큐를 이용해야 한다.

 

queue = []

방문한 노드: 1 2 3 4 5 6 7

04. 트리의 활용

정렬된 상태를 유지하는 배열의 시간 복잡도

임의의 자료들을 담고 있는 자료구조 𝐴가 있다고 가정할 때,

𝐴는 항상 정렬된 상태를 유지해야 한다고 생각해보자.

만약 𝐴가 배열이라면 자료의 추가, 삭제, 탐색은 다음과 같다.

 

4를 새로 추가한다.

정렬을 유지해야 하기 때문에
4가 들어갈 공간을 마련해주어야 한다.

정렬이 유지되도록 새로운 자료를 추가한다.

이번에는 1을 삭제하는 경우이다.

배열의 비어있는 인덱스를 채워야 하므로,
1이 삭제되고 생긴 빈자리를 채우기 위해 당겨와야 한다.

정렬된 상태를 유지하는 배열의 삭제는 일반 배열의 삭제와 동일하다.

정렬된 상태를 유지하는 배열의 추가와 삭제 연산은 1장에서 배운 배열의 특성대로 𝑂(𝑛)의 시간 복잡도를 가진다.

 

정렬된 자료구조에서 사용할 수 있는 탐색 알고리즘인 이진 탐색을 이용하면

정렬된 배열 내에서의 자료 탐색을 𝑂(𝑙𝑜𝑔𝑛)만에 수행할 수 있다.

 

정렬된 배열의 중간값과 찾는 값의 크기를 비교하고,

중간값보다 작은 경우에는 중간값을 기준으로 좌측,
중간값보다 큰 경우에는 중간값을 기준으로 우측을 대상으로 다시 탐색한다.

 

1부터 𝑛까지의 자연수 중 상대방이 생각하고 있는 숫자를 맞히는

'업 다운 게임'에서 최적의 전략으로써 사용할 수 있다.

예를 들어 이진 탐색을 사용하여 1부터 100까지 자연수 중

상대방이 생각하고 있는 숫자를 맞히기까지 걸리는 횟수는

𝑂(𝑙𝑜𝑔100) = 6.64. . . 이므로 최악의 경우 7회이다.

 

따라서 정렬된 배열의 삽입, 삭제, 탐색의 시간 복잡도는 다음과 같다.

삽입	삭제	탐색
O(n)	O(n)	O(logn)

이진 탐색 트리

컴퓨터에서 트리를 활용하는 예시는 대표적으로 이진 탐색 트리가 있다.

 

정렬된 상태를 유지해야 하는 자료구조 𝐴가 트리로 구현되어 있다면 더 효율적으로 연산이 가능하다.

 

이진 탐색 트리는 항상 정렬된 상태를 유지하는 자료구조이며

어떤 정점의 왼쪽 서브 트리는 그 정점보다 같거나 작은 정점들로만,

오른쪽 서브 트리는 그 정점의 값보다 큰 정점들로만 이루어져 있다.

 

이진 탐색 트리에서 각 요소를 오름차순으로 탐색하기 위해서 중위순회를 이용할 수 있다.

 

이진 탐색 트리의 삽입, 삭제 시간복잡도는 트리의 높이에 비례

삽입	삭제	탐색
O(logn)	O(logn)	O(logn)

이진 탐색 트리의 문제점

한쪽으로 편향된

이진탐색트리도 존재할수있다.

이를 편향 이진 트리라고 부른다.

 

이 경우 이진탐색트리의

장점을 살리지 못한다는 문제점이 존재한다.

 

 

 

 

 

 

실제로 많이 활용되는 이진 탐색 트리는 자가 균형 이진 탐색 트리라고도 불리는 '레드블랙 트리'를 사용한다.

트리 실습

트리의 높이

트리를 DFS로 순회하다 보면 언젠가 리프 노드에 도달하게 되는데,

이때 각 노드가 루트 노드로 부터 얼마나 떨어져 있는지 계산할 수 있다.

 

모든 리프노드에 대해 깊이를 구하고,

가장 큰 값에 1을 더해 출력해주면 된다.

트리의 너비

주어진 트리의 너비가 가장 큰 레벨과 그 레벨의 너비를 계산해야 한다.

레벨이란, 깊이가 같은 노드들의 집합을 의미하며 루트 노드부터 1로 시작한다.

 

트리의 각 정점을 격자로 정리하여 풀이 과정을 이해해보자.

같은 레벨의 노드는 같은 행에 위치해야 하고, 한 열에는 하나의 정점만 위치해야 한다

 

또, 한 정점의 왼쪽 서브 트리의 정점들은 모두

그 정점보다 왼쪽의 열에 위치해야 하며

오른쪽 서브 트리의 정점들은 모두
그 정점보다 오른쪽의 열에 위치해야 한다.

 

이러한 규칙으로 트리를 격자에 넣어보면 다음과 같은 모양으로 정리된다.

이때 가장 너비가 긴 레벨은 2이고, 그 너비는 4이다.

 

정점의 행은 각 정점의 깊이를 구하면서 구할 수 있다.

그런데 열은 어떻게 계산해야 할까?

 

어떤 정점 𝐴의 왼쪽 서브트리의 정점들의 열이 모두 확정되었다면

비로소 𝐴의 열도 확정지을 수 있다.
그리고서 오른쪽 서브 트리의 정점들의 위치를 계산하면 된다.

 

왼쪽 서브 트리를 먼저 확정 짓는다 = 왼쪽 서브 트리를 먼저 방문한다.

즉 중위순회를 이용하여 트리의 너비를 구할 수 있다.

---

4. 우선순위 큐와 힙

01. 우선순위 큐의 구현 방법과 힙

우선순위 큐란?

우선순위가 높은 원소가 먼저 출력되는 추상적 자료형

 

출력 연산 시 가장 우선순위가 높은 원소를 출력한다.

 

우선순위 큐를 단순한 접근 방법으로 구현한 경우

입력 : 𝑂(1)

출력 : 𝑂(𝑛)

힙이란?

최솟값 또는 최댓값을 빠르게 찾기 위해 고안된 완전 이진 트리

최대 힙(Max Heap)

부모노드는 항상 자식노드 보다 큰 값을 갖고있다.

최소 힙(Min Heap)

부모노드는 항상 자식노드 보다 작은 값을 갖고있다.

 import heapq

파이썬의 heapq 모듈로 최소 힙을 사용할 수 있다.

 

최대 힙이 필요한 경우에는 값을 저장할때 -1을 곱한값을 저장하면 된다.

-1을 곱함으로서 최댓값과 최솟값이 반전된다는 점을 이용

단, 이 방법은 힙이 저장하는 값이 수(number)일 때만 유효

 

# 설명 기준은 최소 힙이다.

힙: 자료 입력하기 

힙은 완전 이진 트리의 특성을 유지해야 한다.
따라서 입력된 자료는 항상 마지막 레벨의 가장 오른쪽 자리에 채워진다.

# 입력된 값보다 부모 노드의 값이 더 클경우 자리를 바꾼다.

부모노드가자신보다더작은값이될때까지 계속 자리를 변경한다.

 

부모 노드와의 대소관계와

완전이진트리의 특성을 유지한 채 자료를 입력하면 된다.

 

최악의 경우는 새로운 최솟값이 입력되는 경우이고,

루트 노드까지 거슬러 올라가게 된다.

이때 발생하는 연산 횟수는 트리의 높이와 비례하므로

𝑂(𝑙𝑜𝑔𝑛)의 시간 복잡도를 가진다.

힙: 자료 출력하기

힙에서 출력되는 자료는 무조건 루트 노드!

 

루트 노드를 출력할 경우

루트노드의 빈자리는 마지막 노드가 대신한다.

자식 노드와 값을 비교하며 자리를 바꾼다.

 

최악의 경우는 힙의 맨 마지막 원소가 가장 큰 값을 가진 경우이다.

이 때 자리를 바꾸는 연산의 횟수는 트리의 높이만큼 이루어지므로

마찬가지로 𝑂(𝑙𝑜𝑔𝑛)의 시간 복잡도를 가진다.

우선순위 큐의 구현

	단순한 구현	힙으로 구현
입력	O(1)	O(logN)
출력	O(n)	O(log N)

02. 힙을 이용한 문제 풀이

최소 힙 구현하기

heapq 라이브러리를 사용하지 않고, 최소 힙을 구현해보자.

완전 이진 트리는 배열로 구현될 수 있으므로 힙도 배열로 구현할 수 있다.

최대 힙 구현

절댓값이 가장 작은 원소가 먼저 출력되는 '절댓값 힙'을 구현

힙 정렬 구현하기

힙을 출력할 때는 저장하고 있는 자료 중 최솟값을 반환하므로

주어진 정수를 정렬하기 위해서는 모든 정수를 힙에 입력하고, 힙의 모든 정수를 출력하면 된다.

 

𝑛개의 정수가 있다고 할 때,
모든 정수를 힙에 입력하는 연산은 𝑂(𝑛𝑙𝑜𝑔𝑛),

힙에서 모든 정수를 출력하는 연산도 𝑂(𝑛𝑙𝑜𝑔𝑛)이다.