zo_zni's Blog

그래프 (Graph) 그래프의 정의 그래프(G)는 정점(vertex)들의 집합 $V$와 이들을 연결하는 간선(edge)들의 집합 $E$로 구성된 자료구조입니다. 위와 같은 그래프가 있다고 할 때, 정점은 A, B, C, D, E, F 입니다. 또 정점들을 연결하는 간선들은 A-B, B-C, B-E, C-D, E-D, E-F, E-D 입니다. 즉, 위의 그래프는 정점들의 집합 $V = \lbrace A,B,C,D,E,F \rbrace$와 이들을 연결하는 간선들의 집합 $E=\lbrace (A,B),(B,C),(B,E),(C,D), (E,D), (E,F) ,(E,D) \rbrace$로 이루어져 있습니다. 그래프의 활용 그래프는 이렇듯 연결 관계를 표현하기에 현실 세계의 사물이나 추상적인 개념들을 잘 표현할 ..

프리뷰 (Preview) 우리가 전에 배운 queue는 First-in First-Out(FIFO) 구조였습니다. 즉, 아래와 같은 queue가 있을 때, popleft를 하면 5→3→9→...→6 순으로 요소들이 나올 것입니다. 하지만 이때 들어온 순서에 상관없이, 일정한 기준(우선순위)에 따라 요소들이 나오도록 할 수 있는데, 이를 일반적인 queue와 구분 지어, priority queue라고 합니다. 그런데 원소를 추가할 때마다, 오름차순 혹은 내림차순으로 알아서 정렬해 주는 자료구조인 heap을 통해 priority queue를 구현할 수 있습니다. 힙 (Heap) 코딩 테스트에서는 힙(heap)을 일일이 구현할 필요가 없으며, 이미 잘 만들어진 heap을 잘 활용하는 것이 중요합니다. 그렇기에..

트리(Tree) Tree는 서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어 있습니다. 리스트가 단순히 순서를 매겨 데이터를 나열하는 선형 자료구조라면, 트리는 비선형적인 자료구조입니다.⁽¹⁾ 트리는 root에서 시작하여 여러 개의 tree가 중첩되는 형태로 만들어집니다. 그렇기에 하나의 tree안에 여러 개의 subtree가 존재합니다. Tree 관련 개념 기본적인 트리 관련 용어를 정리해 보도록 하겠습니다. 정점 (Vertex): A,B,C와 같은 값을 갖고 나타내며, 노드로 표현됩니다. 간선 (Edge): 정점 간에 연결된 선입니다. 자식 노드 (Child), 부모 노드 (Parent) 형제 노드(Sibling): 같은 부모를 가진 노드를 말합니다. ..

탐색 알고리즘(Search Algorithm) 탐색 알고리즘(Search Algorithm)이란 주어진 데이터 안에서 원하는 값을 찾는 알고리즘을 말합니다. 간단한 예시를 들자면, 만약 다음과 같이 나열된 숫자가 주어졌습니다. [2, 93, -2, 0, 84, 2039] 이 상황에서 어떻게 0을 찾을 것인지에 대한 방법론을 만드는 것이 저희의 목표이고, 그러한 방법을 모두 일컬어 탐색 알고리즘이라고 부릅니다. 종류로는 선형 탐색(Linear Search), 이진 탐색(Binary Search), DFS 또는 BFS가 해당하는 비선형 탐색(Non-linear Search)이 있습니다. 그중 이번에 살펴볼 탐색 알고리즘은 코딩 테스트에서 자주 사용되는 이진 탐색입니다. 이진 탐색(Binary Search) ..

재귀 (Recursion) 재귀란 자신을 정의할 때, 자기 자신을 다시 호출하는 것입니다. 정의는 매우 단순하지만, 추후 그래프 탐색, 트리 , dp 등 주요 자료구조와 알고리즘과 연결되기 때문에 매우 중요한 개념입니다. 재귀에 대한 대표적인 예시는 factorial과 fibonacci가 있습니다. 자기 자신을 재참조한다는 것이 어떤 의미인지 코드를 통해 확인해 보도록 합시다. 재귀의 example 팩토리얼(factorial) def factorial(n): if n == 1: return 1 return n * factorial(n - 1) 함수 factorial 의 반환에 factorial 를 재참조하는 것을 확인할 수 있습니다. 피보나치(fibonacci) def fibo(n): if n == 1 ..

DTA(Direct-address Table) Direct-address Table(직접 주소화 테이블)이란, key값이 $k$인 데이터를 index $k$ 위치에 저장하는 방식입니다. key: 출석번호, value: 이름 (3, 노정호) (5, 배준석) (6, 정재헌) (7, 남영욱) 직접 주소화 방법을 통해 key-value 쌍의 데이터를 저장하고자 하면 많은 문제가 발생합니다. 문제점 1) 불필요한 공간 낭비 key: 학번, value: 이름 (2022390, 노정호) (2022392, 배준석) (2022393, 정재헌) (2022401, 남영욱) 문제점 2) Key값으로 문자열이 올 수 없다. key: ID, value: 이름 (nossi8128, 노정호) (js9876, 배준석) (zebra00..

큐(Queue) 💡 Queue queue는 먼저 저장한 데이터가 먼저 출력되는 선입선출 FIFO(First In First Out) 형식으로 데이터를 저장하는 자료구조입니다. queue의 rear(뒤)에 데이터를 추가하는 것을 enqueue라고 합니다. 또한 queue의 front(앞)에서 데이터를 꺼내는 것을 dequeue라고 합니다. FIFO (First In First Out) List 기반 queue 구현 python에서 queue를 가장 간단히 구현하는 방법은 단순하게 list를 이용하는 것입니다. list의 append 메서드를 사용하면 맨 뒤에 데이터가 추가 되고, pop을 하게 되면, 맨 앞의 데이터가 나오기 때문입니다. 여기서 주목해야 할 점은 list로 queue를 구현하면 dequeu..

리스트 (List) 리스트는 순서를 가지고 원소들을 저장하는 자료구조로, mutable, iterable, sequence 객체입니다. Array List와 Linked List 2가지 방식으로 구현이 가능한데, python에서 사용하는 리스트는 Array List로 구현되었습니다. 동적 배열 dynamic array 배열(array)은 정적 배열(static array)과 동적 배열(dynamic array)로 구분됩니다. 선언 이후에 크기를 변경할 수 없는 정적배열과 다르게 동적배열은 크기를 늘릴 수 있습니다. 파이썬의 리스트는 내부적으로 동적배열(dynamic array)로 구현되어 있습니다. List 사용법 - 기본 선언할 때에 배열의 크기를 정하지 않아도 되는 장점 덕분에 코딩테스트에서 동적 배..

💡 "다이나믹 프로그래밍(Dynamic Programming)"은 큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법을 의미합니다. 다이나믹 프로그래밍을 사용하는 알고리즘의 주요 특징은 다음과 같습니다: 중복 계산 감소: 이미 계산한 결과를 저장하고, 필요할 때마다 재활용하여 중복된 계산을 피합니다. 점화식: 주어진 문제의 해를 작은 문제의 해를 통해 표현하는 식을 정의합니다. 이를 점화식이라고 부릅니다. 최적 부분 구조: 큰 문제의 최적해가 작은 문제들의 최적해를 통해 구할 수 있어야 합니다. 모든 해결책을 다 탐색해보는 ‘완전 탐색’은 기본적으로 높은 시간 복잡도를 가집니다. 이를 ‘체계적’이고 ‘효율적으로 탐색하기 위해서는 몇 가지 조건이 있어야 합니다...

💡 "분할정복"은 문제를 해결하기 위해 문제를 작은 부분 문제로 분할하고, 각 부분 문제를 독립적으로 해결한 후, 그 결과를 조합하여 전체 문제의 해를 얻는 방법입니다. 분할정복의 주요 특성은 다음과 같습니다. 분할(Divide): 주어진 문제를 더 작은 부분 문제로 분할합니다. 이때, 부분 문제들은 원래 문제와 동일한 유형이지만 크기가 작아야 합니다. 정복(Conquer): 각 부분 문제를 재귀적으로 해결합니다. 부분 문제가 충분히 작으면, 재귀를 멈추고 직접적으로 해결합니다. 통합(Combine): 부분 문제들의 해를 조합하여 전체 문제의 해를 얻습니다. 분할 정복은 주로 재귀적인 방식으로 구현되며, 문제를 더 작은 부분 문제로 나누어 해결하고 이를 결합하여 최종 해를 얻습니다. 분할정복의 과정을 의..