Search

알고리즘 정리

👨🏻‍💻
코딩 테스트를 위한 알고리즘 & 자료구조 공부를 정리한 내용입니다. 또한, 대부분의 내용이 Python 언어로 정리되어 있습니다. 파이썬에 대한 정리를 확인하고 싶다면 아래 링크로 접속해주세요!
목차

🤖 정리한 강의 소개

✍🏻 프로그래머스 사이트의 [ 어서와! 자료구조와 알고리즘은 처음이지? ] 강좌를 수강하고, 개인적으로 정리한 내용이 있음을 알려드립니다.
✍🏻
실습 예시를 풀어보며 공부가 잘되기 때문에 실습 예시를 풀며 공부를 원하시거나 더 자세한 내용을 원하시면 아래 사이트에서 직접 수강을 권장드립니다.

1. 선형 배열(Linear Array)

❓ 배열이란?
원소들이 순서대로 늘어놓은 것

👨🏻‍💻 리스트 관련 메서드

리스트 길이와 실행 시간이 상관없는 메서드
list.append(iterable) : 맨 뒤에 원소로 그대로 덧붙이기
list.extend(iterable) : 맨 뒤에 원소로 추가하기
list.pop() : 맨 뒤의 원소 하나를 꺼내기
❓ append와 extend 메서드 차이
리스트 길이와 실행 시간이 비례하는 메서드 (O(n)O(n))
list.insert(index, iterable) : 특정 위치에 원소 추가
del(index)/ del list[index] : 특정 위치 원소 삭제하기
list.index(data) : 특정 값(data) 가 존재하는 위치를 돌려준다.

2. 정렬과 탐색(Sorting & Searching)

👨🏻‍💻 정렬 관련 함수 & 메서드

sorted(list,reverse=boolean) : 정렬된 리스트를 반환 (기존 list 는 변화 없음)
list.sort(reverse=boolean) : 리스트를 정렬함
key값에 lambda 식을 설정하여 원하는 정렬 조건을 지정
✍🏻
람다 사용법 : lambda 인자 : 표현식

요소의 길이를 기준으로 정렬

list1 = ['test1', 'esttest', '12test'] # 요소의 길이를 기준으로 설정 list1.sort(key=lambda x: len(x)) # ['test1', '12test', 'esttest'] print(list1)
Python

특정 레코드를 기준으로 정렬

list1 = [ {'name':'Jamie', 'age':35}, {'name':'Alfredo', 'age':15}, {'name':'Jessi', 'age':26}, ] # 'name' 레코드를 기준으로 정렬 list1.sort(key=lambda x: x['name']) # [ # {'name': 'Alfredo', 'age': 15}, # {'name': 'Jamie', 'age': 35}, # {'name': 'Jessi', 'age': 26} # ] print(list1)
Python

🔎 탐색 관련 개념

선형 탐색 & 순차적 탐색 ( O(n)O(n) )

리스트의 요소들을 처음부터 순차적으로 탐색하여 원하는 값을 찾는 방법이다.
원하는 값이 발견되지 않을 경우 배열에 있는 모든 원소를 전부 검사한다.

이진 탐색 ( O(logn)O(log_n) )

크기순으로 정렬된 성질을 이용하기 때문에 이미 정렬되어 있는 배열에서 사용할 수 있는 방법이다.
배열의 중간의 양옆 값을 확인하여, 원하는 데이터가 어디에 속하는지 점점 좁혀나가는 방법이다.
# 원하는 값이 90 # 원하는 값이 50(1차 탐색 중간 값)보다 큰 상황, 2차 탐색 시 51(lower) ~ 100(upper) 탐색 1 2 3 4 5 ... 47 48 49 50 51 52 53 ... 99 100 # 원하는 값이 75(2차 탐색 중간 값)보다 큰 상황, 2차 탐색 시 75(lower) ~ 100(upper) 탐색 51 52 53 ... 74 75 76 ... 99 100 # 원하는 값이 87 (3차 탐색 중간 값)보다 큰 상황, 2차 탐색 시 87(lower) ~ 100(upper) 탐색 75 76 ... 86 87 88 ... 99 100 ... 반복
Plain Text
배열의 크기가 커질수록 동작시간이 기하급수적으로 커지는 선형 탐색 & 순차적 탐색에 비해 이진 탐색 방식은 배열의 크기가 동작시간에 큰 영향을 주지 않는다.
하지만, 이미 정렬된 배열이 우선적으로 필요하기 때문에 일회성으로 사용되는 데이터에서 값을 찾을 때 보다 주기적으로 데이터 탐색이 필요한 데이터 목록에서 사용하면 좋다.
왜냐하면 일회성으로 탐색 후 사용하지 않는 데이터에서 굳이 정렬을 추가로 해줄 필요는 없기 때문이다.

3. 재귀 알고리즘(Recursive Algorithms)

❓ 재귀 알고리즘이란

같은 알고리즘을 반복하여 사용하며 문제를 푸는 방법이다.
특정 알고리즘 이름이 아니다. 하나의 방법을 말하는 것이다

재귀 호출의 종결 조건

재귀 알고리즘을 사용하기 위해서는 해당 호출의 종결조건(Trivial case)이 중요하다.
만약 종결조건을 지정하지 않는다면 무한하게 알고리즘을 호출하기 때문이다.
def sum(n): # 종결조건 if n <= 1: return 1 # 종결조건에 부합하지 않는 경우 재귀 호출 else: return n + sum(n-1) # 4 + 3 + 2 + 1 # 10 출력 print(sum(4))
Python
재귀 호출의 형태(Recursive version)에는 그에 대칭되는 반복적인 형태(Iterative version)이 존재합니다.
둘은 복잡도는 동일하지만, 문제에 따라 서로 효율적인 경우가 다릅니다.
하지만, 반복적으로 동일한 함수를 많이 호출하기 때문에 효율성 측면에서는 재귀 호출이 불리한 경우가 많다.

🗼 하노이의 탑

재귀 알고리즘의 대표적인 문제로, 옛날 다른나라분들이 즐기시던 놀이(?) 라고 한다.
해당 예시를 잘 숙지하면 재귀에 대한 적용법에 큰 도움이 될 것이다.
하노이의 탑을 잘 설명해주시고 알고리즘으로 적용하는 방법도 상세히 적어주신 블로그 링크를 남긴다.

4. 알고리즘의 복잡도(Complexity of Algorithms)

⏲️ 시간 복잡도(Time Complexity) : 문제를 해결하는데 걸리는 시간에 대한 복잡도
평균 시간 복잡도(Average Time Complexity) : 문제를 해결하는데 소요되는 시간의 평균
최악 시간 복잡도(Worst-case Time Complexity) : 문제를 해결하는데 가장 긴 시간
🌌 공간 복잡도(Space Complexity) : 문제를 해결하는데 사용되는 메모리 공간에 대한 복잡도

✍🏻 시간 복잡도 표기법

Big-O Notation : 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 방법
Big-O 복잡도 차트 사진
종류
O(n)O(n) : 선형 시간 알고리즘
n의 갯수에 비례한다.
O(logn)O(log_n) : 로그 시간 알고리즘
문제 해결에 필요한 과정들이 연산마다 줄어드는 알고리즘
O(n2)O(n^2) : 이차 시간 알고리즘
문제를 해결에 필요한 단계가 입력 값 n의 제곱과 같다.
예시 : 삽입 정렬
O(2n)O(2^n)
문제의 해결에 필요한 단계의 수가 2의 n 제곱 수와 같다.
O(nlogn)O(nlog_n) : 병합 정렬 알고리즘
1.
정렬된 데이터를 반씩 나누어 각각 정렬시킨다. ( O(logn)O(log_n) )
2.
정렬된 각 데이터를 두개씩 한데 합친 후, 정렬한다. ( O(n)O(n) )
👨🏻‍💻
합치는 과정에서 어떤 식으로 진행되는지 헷갈릴 수 있다. 👓 안경잡이개발자 님의 정리된 블로그 글을 보면 한눈에 이해할 수 있다. https://blog.naver.com/ndb796/221227934987

시간 복잡도 표시 예시

🔎 순차적 탐색
Average-case: O(n)O(n)
Worst-case: O(n)O(n)
순차적 탐색은 무조건 처음 ~ 끝까지 확인하기 때문에 동일하다.
⬇️ 삽입 정렬
Best case: O(n)O(n)
모두 정렬이 되어 있을 때 확인만 한다.
Worst case : O(n2)O(n^2)
모두 역순으로 정렬되어 있을 때, 매번 정렬해줘야한다.

5. 연결 리스트(Linked Lists)

각 원소들을 링크(link)로 연결하여 관리하는 방법이다.
해당 방법을 이용하여 링크를 끊어 원소를 삭제하거나 그 위치에 다른 원소를 삽입할 수 있다.
이 동작은 선형 배열보다 빠른 시간안에 원소의 삽입 / 삭제 동작을 할 수 있어 많이 사용된다.
각 원소는 하나의 Node 단위로 관리되며, Data다음 노드를 가르키는 Link(next)로 이루어져있다.
이 노드들이 모이면 연결리스트가 되며 연결리스트의 첫 Node를 Head, 맨 끝의 Node를 Tail 이라 한다.
Head, Tail, 연결리스트의 총 Node 갯수를 알아두면 연결리스트의 추상적 자료구조를 만들 수 있으며 관리에 용이하다.
이는 연속한 위치에 존재하는 일반적인 배열과 가장 큰 차이점으로, 각 연결된 Node가 임의의 위치에 존재가 가능하다는 의미로 해석할 수 있다.
위와 같은 형태의 연결리스트 뿐 아니라, 이전노드 & 다음노드를 확인할 수 있는 양방향 연결 리스트도 존재한다.
양쪽의 Head, Tail 부분은 dummy Node로 채워서 사용하면 Data가 들어있는 Node는 모두 같은 형태(prev, next가 모두 존재하는 형태)이기 때문에 관리가 훨씬 쉽다.

🔎 단방향 리스트의 특정 원소 참조 연산

✍🏻 예시로 연결리스트와 각 Node의 클래스는 아래와 같이 정의한다. (빈 연결리스트 일 때)
class Node: def __init__(self, item): self.data = item self.next = None class LinkedList: def __init__(self): # 연결 리스트의 Node 갯수 self.nodeCount = 0 # 만약 Node가 존재한다면 Node 클래스 값이 들어간다. # 즉, curr = self.head 와 같은 코드를 사용한 후 # curr.data / curr.next 등으로 Node를 사용할 수 있다. self.head = None self.tail = None
Python
getNode 함수를 만들어 연결리스트의 원하는 Node를 반환하도록 만들어 봤으며, 아래는 함수의 내용이다.
아래 getNode 함수는 별도로 연결리스트를 인자로 받지만, 연결리스트 클래스(LinkedList)의 내부 함수로 정의하여 사용해도 된다.
# LinkedList : 연결 리스트 # index : 원하는 Node 번호 def getNode(LinkedList, want_index): # 아래 조건 중 하나라도 만족하면 Node Return # 만약 원하는 인덱스 번호가 0이하 # 연결 리스트의 전체 Node 수 보다 클 때 if want_index < 1 or want_index > LinkedList.nodeCount: return None # 시작 노드 인덱스를 1로 시작 curr_index = 1 # 첫 노드 부터 시작 curr = LinkedList.head # 원하는 인덱스 값에 도달할 때 까지 Node 이동 작업 while curr_index < want_index: # 다음 노드로 넘어감 (원하는 인덱스가 아니기 때문에 데이터 조회 X) curr = curr.next # 현재 인덱스 값 +1 curr_index += 1 return curr
Python
🏃 함수의 동작 순서는 크게 아래와 같다.
1.
연결리스트의 head를 받아옴(연결리스트가 클래스일 경우 self.head)
2.
원하는 인덱스 번호의 Node 까지 이동 (curr = curr.next)
3.
원하는 인덱스 번호의 Node를 반환 (return curr)
✍🏻 함수 사용 예시
위 함수 내용을 적절히 변경하여, 각 Node의 내용을 출력하게 만들거나 while 문을 사용하여 연결리스트의 길이를 알아내는 등 여려방향으로 응용이 가능하다. 😎

6. 스택(Stacks)

스택은 데이터를 넣은 순서의 역순으로 꺼내서 사용하는 대표적인 LIFO(Last In, First Out) 형태의 자료 구조이다.
구조는 아래와 같다.

👨🏻‍💻 스택에서 만들 수 있는 메소드

size() : 현재 스택에 들어있는 원소의 갯수를 구한다.
isEmpty() : 현재 스택이 빈 스택인지 확인한다.
⚠️
python의 리스트에서 지원하지는 않으며, 아래와 같이 만들 수 있다.
def isEmpty(self): return self.size() == 0
Python
push(data) : 데이터 원소 data를 스택에 추가한다.
pop(index) : index 번째 원소를 제거 후, 반환한다.
만약 index값이 없다면 맨 마지막 값을 제거 후 반환한다.
peek() : 스택에 가장 나중에 저장된 원소를 반환한다. 하지만 pop() 과 다르게 실제로 제거하지는 않는다.

⚠️ 스택 관련 에러

스택 언더플로우(stack underflow) : 비어있는 스택에서 데이터 원소를 꺼낼 때
스택오버플로우(stack overflow) : 꽉 찬 스택에 데이터 원소를 추가하려할 때

7. 큐(Queues)

스택은 데이터를 넣은 순서대로 꺼내서 사용하는 대표적인 FIFO(First In, First Out) 형태의 자료 구조이다.
스택은 데이터를 넣을 때 한 쪽 끝에서 넣어야 하며 꺼낼 때에는 넣은 곳에서 반대 쪽에서 꺼내야한다.
이때 데이터를 넣는 작업을 인큐 연산(enqueue), 데이터를 꺼내는 연산을 디큐 연산(dequeue)이라고 한다.

👨🏻‍💻 큐에서 만들 수 있는 메소드

size() : 현재 큐에 들어있는 원소의 갯수를 구한다.
isEmpty() : 현재 큐가 빈 큐인지 확인한다.
enqueue(data) : 데이터 원소 data를 큐에 추가한다.
⚠️
python의 리스트에서 지원하지는 않으며, 아래와 같이 만들 수 있다.
def enqueue(self, data): return self.data.append(data)
Python
dequeue() : 원소를 제거 후, 반환한다.
⚠️
python의 리스트에서 지원하지는 않으며, 아래와 같이 만들 수 있다.
def dequeue(self): return self.data.pop(0)
Python
peek() : 큐에 가장 나중에 저장된 원소를 반환한다. 하지만 dequeue() 과 다르게 실제로 제거하지는 않는다.
⚠️
python의 리스트에서 지원하지는 않으며, 아래와 같이 만들 수 있다.
def peek(self): return self.data[0]
Python

8. 환형 큐(Circular Queues)

큐의 저장 공간(self.maxCount)을 정한 후, 해당 공간을 돌려가며 사용하는 방식이다.
환형 큐의 저장 공간을 컨트롤하기 위해 Rear(Rear Pointer)Front(Front Pointer) 를 지정하여 사용한다.

🔎 환형 큐 에서 데이터 추가 & 삭제

데이터 추가

환형 큐에서 데이터를 추가할 경우 Rear 을 한칸 움직인 후, 해당 포인트 자리에 데이터를 집어넣는다.
이때 Rear Pointer는 아래와 같은 식을 거쳐 변경된다.
# rear pointer 값이 0 ~ (maxCount-1) 값 범위내에서 이동하기 떄문 rear = (rear + 1) % self.maxCount
Python

데이터 삭제

환형 큐에서 데이터를 제거할 경우 Front를 한칸 움직인 후, 해당 포인트 자리의 데이터를 제거한다.
이때 Front Pointer는 아래와 같은 식을 거쳐 변경된다.
# front pointer 값이 0 ~ (maxCount-1) 값 범위내에서 이동하기 떄문 front = (front + 1) % self.maxCount
Python

👨🏻‍💻 환형 큐 에서 만들 수 있는 메소드

환형 큐에서는 저장공간(self.maxCount)이 정해져 있기 때문에, 큐의 공간이 모두 채워져 있는지 확인하는 함수를 생성한다.
isFull() : 현재 큐의 저장공간이 모두 채워져 있는지 확인한다.
⚠️
python의 리스트에서 지원하지는 않으며, 아래와 같이 만들 수 있다.
def isFull(self): return self.count == self.maxCount
Python

9. 우선순위 큐(Priority Queues)

큐의 대표적인 특징인 FIFO(First In, First Out) 를 따르지 않고, 각 원소들의 우선순위를 정하여 해당 우선 순위에 맞춰 데이터를 꺼내는 방식을 사용하는 큐

10. 트리(Trees)

root 노드에서 간선(edge)들이 뿌리처럼 뻗어나가는 구조를 가진 형태이다.

✍🏻 트리 관련 용어

Node의 수준(Level)
root 노드에서 간선을 하나씩 거칠 수록 레벨이 하나씩 증가한다.
root 노드가 0 일 경우 간선을 거칠 수록 Level 1, Level 2 ... 로 증가
Node의 높이(Height) or Node의 깊이(depth)
Node의 높이 = Node의 최대 수준(Level) + 1
부분 트리(서브 트리)
트리에서 특정 노드를 기준으로 가장 아래쪽 자식 노드까지를 묶어 부분 트리라고 한다.
Node의 차수(Degree)
자식 Node 수를 나타내며, 이때 자식 트리가 없는 Node들을 leaf Node라고 한다.

11. 이진 트리(Binary Trees)

모든 노드의 차수(자식 노드 수)가 2개 이하인 구조로 이루어진 트리이다.
이러한 구조를 가진 트리는 아래와 같이 재귀적으로 정의할 수 있다.
1.
구조가 루트 노드 + 왼쪽 서브트리 + 오른쪽 서브트리 구조이다.
이때 빈 트리도 이진 트리로 간주한다!
2.
왼쪽과 오른쪽 서브트리도 마찬가지로 이진 트리이다.

🌳 특별한 구조를 가진 이진트리

1.
포화 이진 트리
모든 차수(Level)의 노드들이 모두 2개씩 채워져 있는 이진 트리
높이가 kk 일때 노드의 개수가 2k12^k -1 인 이진트리다.
2.
완전 이진 트리
높이가 kk 일 때, 레벨 k2k-2 까지는 모든 노드가 2개의 자식을 가진 포화 이진트리 상태
높이가 kk 일 때, 레벨 k1k-1(마지막 노드 레벨)를 제외한 모든 노드들은 포화 이진트리 상태이며, 레벨 k1k-1(마지막 노드 레벨) Node들은 왼쪽부터 순차적으로 채워진다.

👨🏻‍💻 완전 이진트리 예시

✍🏻
루트 노트는 Level 0, 높이가 3 인 노드
가장 마지막 노드 레벨인 D 노드, E 노드왼쪽 부터 순차적으로 채워진 상태이다.
✍🏻
루트 노트는 Level 0, 높이가 4 인 노드
가장 마지막 노드 레벨인 H 노드왼쪽 부터 순차적으로 채워진 상태이다.

🔎 이진 트리의 자료구조 구현

이진 트리는 아래와 같이 3가지의 요소를 가진 구조이다.
이를 이용하여 아래와 같이 클래스를 정의할 수 있다.
하나의 Node에 대한 정보
class Node: def __init__(self, item): self.data = item self.left = None self.right = None
Python
data : 해당 노드의 값이 들어있는 부분
left : 자식 노드 중 왼쪽에 있는 노드
right : 자식 노드 중 오른쪽에 있는 노드

👨🏻‍💻 이진 트리에서 만들 수 있는 메소드

size() : 왼쪽 Node의 서브트리 size() + 오른쪽 Node의 서브트리 size()
⚠️
이때 자식 노드가 None 일 경우 0 반환 (종단 조건)
⚠️
python의 리스트에서 지원하지는 않으며, 아래와 같이 만들 수 있다.
class Node: def size(self): # root 노드 일 때 if self.root: return self.root.size(): else: left_size = self.left.size() if self.left else 0 right_size = self.right.size() if self.right else 0 # 자기 자신의 노드 갯수도 포함 return left_size + right_size + 1
Python
⚠️
소스코드는 해당 강의의 연습문제이기 때문에 작성 X

12. 이진 트리의 순회법(Traversal)

이진 트리에서 순회하는 법은 깊이 우선 순회(depth first traversal)와 넓이 우선 순회(breadth first traversal)로 나뉜다.

🔎 깊이 우선 순회(depth first traversal)

깊이 우선 순회에서도 어떤 노드를 먼저 순회하는지에 따라 아래 3가지로 나뉜다.

⬇️ 중위 순회(in-order traversal)

중위 순회는 왼쪽 서브트리 → 본인 노드 → 오른쪽 서브트리를 순서로 순회하는 방식이다.
⚠️
만약 서브트리의 노드가 오른쪽에만 존재한다면, 본인노드 → 오른쪽 서브트리 순서로 순회한다.
👨🏻‍💻 중위 순회에서 만들 수 있는 메소드
inorder() : 왼쪽 서브 트리 순회 결과 + 본인 노드 추가 + 오른쪽 서브 트리 순회 결과
⚠️
python의 리스트에서 지원하지는 않으며, 아래와 같이 만들 수 있다.
class Node: def size(self): # root Node일 경우 if self.root: return self.root: return self.root.inorder() # 순회 결과가 저장되는 리스트 traversal = [] # 왼쪽 서브트리 결과 추가 if self.left: traversal += self.left.inorder() # 본인 노드 추가 traversal.append(self.data) # 오른쪽 서브트리 결과 추가 if self.right: traversal += self.right.inorder() return traversal
Python

⬅️ 전위 순회(pre-order traversal)

전위 순회는 본인 노드 → 왼쪽 서브트리 → 오른쪽 서브트리를 순서로 순회하는 방식이다.
⚠️
소스코드는 해당 강의의 연습문제이기 때문에 작성 X

➡️ 후위 순회(post-order traversal)

후위 순회는 왼쪽 서브트리 → 오른쪽 서브트리 → 본인 노드를 순서로 순회하는 방식이다.
⚠️
소스코드는 해당 강의의 연습문제이기 때문에 작성 X

🔎 넓이 우선 순회(breadth first traversal)

노드의 수준(Level)이 낮은 노드를 우선으로 방문한다.
만약 같은 수준의 노드일 때는 부모 노드의 방문 순서에 따라 방문하며, 왼쪽 자식 노드를 오른쪽 자식보다 먼저 방문한다.
넓이 우선 순회는 재귀 방식으로 구현하기 어렵고, 큐를 사용하여 방문 순서를 기록하는 방식을 사용할 수 있다.

13. 이진 탐색 트리(Binary Search Trees)

이진 탐색 트리는 아래의 조건을 만족하는 이진 트리로써, 이진 탐색 알고리즘과 비슷한 성질을 가지고 있다.
왼쪽 서브트리에 있는 모든 데이터는 현재 노드의 값보다 작다.
오른쪽 서브트리에 있는 모든 데이터는 현재 노드의 값보다 크다.
하지만, 이진 탐색 알고리즘에 비해 공간 소요가 큰 단점이 있지만 데이터 원소의 관리가 편하다는 장점도 있다.
또한 이진 탐색 트리는 선형 탐색과 비슷한 모양, 즉 한쪽 방향으로 쏠린 모양 일 때는 효율적이지 못한다.
EX) 1, 2, 3, 4 ,5 순서대로 삽입일 때는 오른쪽으로 쏠린다.
EX) 5, 4, 3, 2, 1 순서대로 삽입일 때는 왼쪽으로 쏠린다.

👨🏻‍💻 이진 탐색 트리에서 만들 수 있는 메소드

⚠️
python의 리스트에서 지원하지는 않으며, 직접 만들어 사용해야한다.
insert() : 트리에 주어진 데이터 원소를 추가하는 메소드
key 값을 비교하여 왼쪽 / 오른쪽 중 적절한 위치를 정한다.
더 이상 탐색할 필요가 없을 경우 해당 위치에 추가
그 전까진 self.left / self.right 에서 insert() 메소드를 재귀적으로 호출하여 탐색
remove() : 특정 원소를 트리에서 삭제하는 메소드
삭제를 원하는 원소가 Leaf Node일 경우 고려
삭제를 원하는 원소의 자식 노드가 하나 존재할 경우 고려
삭제를 원하는 원소의 자식 노드가 두개 존재할 경우 고려
lookup() : 특정 원소를 검색하는 메소드
부모 노드(parent)를 인자로 받아 확인하는 작업이 있어야한다.
inorder() : 키의 순서로 데이터 원소들을 나열하는 메소드
min(), max() : 최소 키, 최대 키를 가지는 원소를 탐색하는 메소드
min() : 왼쪽의 노드만 찾아가면 편하게 구할 수 있다.
max() : 오른쪽의 노드만 찾아가면 편하게 구할 수 있다.

14. 힙(Heap)

은 완전 이진트리의 한 종류로 주로 정렬이나 여러 데이터들 사이에서 최소 or 최대 값을 탐색할 때 사용되며, 데이터 삽입과 삭제 시간이 빠른게 특징이다.

⚙️ 힙의 성질

1.
힙에는 최대 힙(Max Heap)과 최소 힙(Min Heap)이 존재한다.
2.
최대 힙과 최소힙은 모두 느슨한 정렬 상태이다.
느슨한 정렬이란, 좌 / 우 위치에 따라 데이터의 높고 낮음이 정해지지 않고 각 노드의 레벨에 따라서만 데이터가 정렬된 상태를 말한다.
3.
이전의 이진 탐색 트리와 달리 중복 값을 허용한다.

✍🏻 힙의 종류

최대 힙(Max Heap)

최대 힙은 아래 3가지 조건을 만족하는 힙이다.
1.
상위 노드(부모 노드)가 서브트리의 모든 노드의 값보다 항상 크다.
2.
최대 힙 내의 특정 노드를 루트로 하는 서브트리 또한 최대 힙 상태이다.
3.
완전 이진 트리이다.

최소 힙(Min Heap)

최소 힙은 아래 3가지 조건을 만족하며, 최대 힙(Max Heap)의 반대 버전이라고 생각하면 편하다.
1.
상위 노드(부모 노드)가 서브트리의 모든 노드의 값보다 항상 작다.
2.
최소 힙 내의 특정 노드를 루트로 하는 서브트리 또한 최소 힙 상태이다.
3.
완전 이진 트리이다.

👨🏻‍💻 힙에서 만들 수 있는 메소드

insert(item) : 새로운 원소를 삽입하는 메소드
1.
트리의 마지막 자리에 임시로 새로운 원소를 저장
2.
부모 노드와 키 값을 비교하여 이동 후 조건 만족 시, 상위로 이동
기존 키 값 // 2 을 반복하여 부모 노드 단계로 이동한다.
remove() : root node 를 반환 후 힙에서 삭제처리
1.
힙에서 원소 제거 시, 루트 노드에서 하나가 제거된다.
2.
트리 마지막 노드를 임시로 루트 노드 자리에 배치
3.
더 큰 자식 노드와 비교 후, 조건 만족 시 하위로 이동(삽입 단계와 반대)

❗ 최대 / 최소 힙의 응용

우선 순위 큐(priority queue)에서 사용

Enqueue 시, 느슨한 정렬을 이루고 있도록 한다.
Dequeue 시, 최댓 값을 순서대로 추출 가능

힙 정렬(heap sort)

정렬되지 않은 원소들을 아무 순서로 힙에 삽입 가능
삽입 후, 빈 힙이 될 때 까지 하나씩 삭제
원소들이 삭제된 순서 = 원소들의 정렬 순서

👨🏻‍💻 알고리즘 문제 풀이를 위한 입력과 출력 팁

⌨️ 문제의 정답 예시 값 입력 받는법

코딩테스트의 문제에서는 예제 입력 / 예제 출력 으로 나뉘어 정답의 예시를 보여준다.
각 문제마다 띄어쓰기 / 엔터 등 다양한 구분자로 입력 값을 구분하기 때문에, 각 상황에 맞는 테스트 값(예시 값) 입력 법을 알아두면 편하다.
💡
본인은 파이썬을 주로 사용하여 코딩테스트를 준비하기 때문에 python3 를 기준으로 작성하였다.

띄어 쓰기로 입력 값이 구분되는 경우

예제 입력이 오른쪽과 같은 경우이다.
이럴 경우에는 split() , map() 함수를 사용한다.
예제 입력 4 7
Plain Text
input().split() 를 사용하여 띄어쓰기로 구분된 값을 나눈 후, map() 함수를 사용하여 int형으로 변환
num1, num2 = map(int, input().split()) # 입력 값 확인 print("num1 : {}".format(num1)) print("num2 : {}".format(num2))
Python
map(int, input().split()) 은 아래와 같은 과정이다.
# input().split() 값 -> ['4', '7'] value = input().split() # map()을 사용하여 리스트 요소를 int로 변환 data = map(int, value) # 해당 map 객체를 이용하여 여러 변수에 값 동시 저장 num1, num2 ... = data
Python

줄바꿈으로 값을 구분하는 경우

예제 입력이 오른쪽과 같은 경우이다.
이럴 경우에는 한 줄씩 input() 해주면 된다.
예제 입력 472 385
Plain Text
num1 = input() num2 = input() # 입력 값 확인 print("num1 : {}".format(num1)) print("num2 : {}".format(num2))
Python

더 빠르게 입력받는 방법

input() 으로 입력 받을 경우 상당히 느리다고 한다.
그래서 파이썬 기본 내장 모듈인 sys 모듈의 sys.stdin.readline() 함수를 사용하여 입력받으면 더 빠르다.
import sys # 입력 행 갯수 N = int(input()) # 입력 행 만큼 반복 for _ in range(N): # input() 대신 sys.stdin.readline()을 사용 A, B = map(int, sys.stdin.readline().split()) print(A, B)
Python

🔎 결과 값 출력 방법

코딩테스트의 문제에서는 예제 입력 / 예제 출력 으로 나뉘어 정답의 예시를 보여준다.
간단한 문제는 아래와 같은 방법으로 여러줄의 print 문을 사용하지 않고 1-2줄에 정답 출력이 가능하다.

특정 변수들을 여러 수식을 사용하여 여러줄로 출력할 경우

이 문제와 같이 입력받은 특정 변수를 여러 수식의 결과를 출력하는 문제일 때, 각 수식의 결과마다 print 을 사용할 수 밖에 없게되며 이는 코드가 길어지는 원인이 된다.
예제 문제 내용
두 자연수 A와 B가 주어진다. 이때, A+B, A-B, A*B, A/B(몫), A%B(나머지)를 출력하는 프로그램을 작성하시오.
출력 값
첫째 줄에 A+B, 둘째 줄에 A-B, 셋째 줄에 A*B, 넷째 줄에 A/B, 다섯째 줄에 A%B를 출력한다.
일반적으로 print 함수를 사용하여 각 수식의 결과를 출력하면 다음과 같다.
print 함수가 하나의 값을 출력한 후, 기본적으로 개행을 하기 때문에 아래와 같이 작성한다.
A, B = map(int, input().split()) print(A+B) print(A-B) print(A*B) print(A//B) print(A%B)
Python
하지만 print 함수의 sep 옵션을 사용하여 한줄에 출력하고자 하는 여러 값을 모두 적은 후, 구분자를 설정할 수 있다.
A, B = map(int, input().split()) print(A+B, A-B, A*B, A//B, A%B, sep='\n')
Python

출력과 조건문 동시 사용법

기존에는 조건문을 사용할 때, 조건에 따라 print 해주는 값을 일일히 설정해줘야했다.
조건이 길거나 출력이 필요한 결과 값이 그리 긴 상태가 아니라면 한줄에 축약하는거도 깔끔한 코드를 작성하는데 하나의 방법이 될 수 있다.
예제 문제 내용
두 정수 A와 B가 주어졌을 때, A와 B를 비교하는 프로그램을 작성하시오.
출력
첫째 줄에 다음 세 가지 중 하나를 출력한다. - A가 B보다 큰 경우에는 '>'를 출력한다. - A가 B보다 작은 경우에는 '<'를 출력한다. - A와 B가 같은 경우에는 '=='를 출력한다.
일반적인 방법으로 각 조건문의 결과를 출력하면 다음과 같다. 각 조건마다 print 함수를 일일히 설정해야 한다.
A, B = map(int, input().split()) if A > B: print(">") elif A < B: print("<") elif A == B: print("==")
Python
하지만, 아래와 같이 print 문 안에서도 조건식을 직접 작성이 가능하다.
2-3개 정도의 간단한 조건일 경우 아래와 같이 사용하면 좋을 듯 하다.
A, B = map(int, input().split()) # print([참 출력 값] if [조건] else [거짓 출력 값]) # 거짓 출력 값에 추가적인 조건이 또 들어갈 수 있다. # print([참 출력 값] if [조건] else [참 출력 값] if [2차 조건] else [거짓 출력 값]) print(">" if A > B else("<" if A < B else "=="))
Python

✍🏻 함수 정리

순열 함수

N개의 문자 조합에서 R개로 이루어진 조합을 구하는 함수이다.
⚠️
ilist 인자의 리스트 원소는 모두 str 형식이어야 한다.
def exclude(ilist,num): return ilist[:-1] if num + 1 == len(ilist) else ilist[:num] + ilist[num+1:] def All_case(Oper_list,num): case = [] if num > len(Oper_list): return case if num == 1: for item in Oper_list: case.append(item) elif num > 1: for index in range(len(Oper_list)): case.extend([list(Oper_list[index]) + list(item) for item in All_case(exclude(Oper_list,index),num-1) if list(Oper_list[index]) + list(item) not in case]) return case # 5개의 원소로 이루어진 경우에서 3개의 원소로 이루어진 모든 경우 출력 (중복 X) # (2,1) (1,2)는 다른 경우로 취급 RESULT = All_case(['1','2','3','4','5'],3) for item in RESULT: print(item)
Python

📖 코딩 테스트 문제 정리

주로 백준 사이트프로그래머스 사이트에서 코딩 테스트 문제를 많이 공부한다고 한다.
특히 백준 사이트는 문제가 매우 많기 때문에 본인처럼 막 시작한 사람은 어떤 문제를 풀어봐야할지 고민이었는데, 감사하게도 아래 블로그에서 잘 정리해 주셨다.
백준으로 코딩 테스트를 준비하는 사람은 아래 블로그를 참고하면 아주 좋을 것 같다.
TOP