DATA101

본 포스팅에서는 최단경로(길 찾기)알고리즘 중에서도 플로이드-워셜 알고리즘에 대해 알아봅니다. 📚 목차 1. 최단경로(길 찾기) 알고리즘이란? 2. 플로이드-워셜 알고리즘 개념 3. 플로이드-워셜 알고리즘 특징 4. 플로이드 워셜 알고리즘의 동작 과정 5. 플로이드 워셜 알고리즘 구현(Python) 1. 최단경로(길찾기) 알고리즘이란? 최단경로 알고리즘은 길찾기 알고리즘이라고도 불리며, 말 그대로 특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘입니다. 이번 포스팅에서는 알고리즘 테스트에서 빈출 최단경로 알고리즘 유형 2가지 중 2번째, 플로이드-워셜 알고리즘에 대해 알아봅니다. 다익스트라 최단경로 알고리즘(Dijkstra Algorithm) 플로이드-워셜 알고리즘(Floyd-Warshal..

간단한 내용이므로 바로 본론으로 들어가죠! 1. 정의 및 특징 리스트 컴프리헨션(comprehension)은 리스트를 초기화하는 방법 중 하나로서 대괄호('[]') 안에 조건문이나 반복문을 넣는 방식으로 리스트를 초기화하는 방식입니다. 리스트 컴프리헨션은 필요한 리스트를 생성할 때 보다 간결하고 직관적으로 코드를 작성할 수 있도록 도와줍니다. 아래 예시와 함께 살펴보죠. 2. 예시1: 일반적인 리스트 생성 방법과 비교 예시로서 간단하게 1부터 100까지의 정수 중에서 짝수만 포함하는 리스트를 생성해 보겠습니다. 특히 반복문과 조건문을 각각 나누어 사용하여 리스트를 생성하는 방법과 나누어 살펴보도록 하겠습니다. (1) 일반적인 방법 먼저, 리스트를 직접 생성하고, 반복문을 수행하고 그 안에서 조건문을 수행..

📚 목차 1. 최단경로(길찾기) 알고리즘이란? 2. 다익스트라 최단경로 알고리즘이란? 3. 다익스트라 최단경로 알고리즘의 동작 과정 4. 구현 방법1: 일반적인 구현 4.1. 코드 해설 4.2. 전체 코드 4.3. 시간 복잡도 5. 구현 방법2: 시간 복잡도 개선 5.1. 우선순위 큐(Priority Queue) 자료구조 5.2. 힙(Heap) 자료구조 5.3. 우선순위 큐 자료구조 기반의 알고리즘 동작 과정 5.4. 우선순위 큐 자료구조 기반 알고리즘 구현(Python) 1. 최단경로(길찾기) 알고리즘이란? 최단경로 알고리즘은 길찾기 알고리즘이라고도 불리며, 말 그대로 특정 지점까지 가장 빠르게 도달할 수 있는 경로를 찾는 알고리즘입니다. 알고리즘 테스트에서 빈출 최단경로 알고리즘 유형은 아래와 같습니..

📚 목차 1. 힙 자료구조 2. 힙 자료구조는 언제 사용할까? 3. 힙 자료구조의 종류 4. 힙 자료구조의 동작 과정(최소 힙) 4.1. 데이터 삽입 4.2. 데이터 삭제 5. 힙 자료구조 구현(Python) 5.1. heapq 셋업 5.2. 힙 데이터 삽입(heappush) 5.3. 힙 데이터 삭제(heappop) 5.4. 리스트를 힙으로 변경(heapify) 1. 힙 자료구조 힙 자료구조는 가장 높은(혹은 가장 낮은) 우선순위(e.g., 최댓값, 최솟값)를 가지는 노드를 빠르게 찾아내기 위해 고안된 *완전 이진트리(Complete Binary Tree) 기반의 자료구조입니다. 따라서 가장 높은(또는 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드(root node)에 오는 게 특징입니다. * 완..

📚 목차 1. 우선순위 큐(Priority Queue)란? 2. 힙(Heap) 자료구조 2.1. 힙 자료구조란? 2.2. 우선순위 큐 구현 방식: 리스트 vs 힙 3. 힙 기반의 우선순위 큐 구현(Python) 3.1. heapq 라이브러리 소개 3.1.1. 힙 원소 추가(heappush) 3.1.2. 힙 원소 삭제(heappop) 3.1.3. 리스트를 힙으로 변경(heapify) 3.2. 힙 기반의 우선순위 큐 구현 예시 1. 우선순위 큐(Priority Queue)란? 우선순위 큐는 말 그대로 우선순위가 가장 높은 데이터를 가장 먼저 추출하는 자료구조입니다. 일반적으로 큐(Queue) 자료구조는 선입선출 방식으로서 가장 먼저 삽입된 데이터를 가장 먼저 추출합니다. 간단하게 특징이 유사한 자료구조들의 ..

본 포스팅에서는 그래프(graph) 자료구조에 대해 알아봅니다. 그래프 자료구조의 구성 그래프는 그림 1 과 같이 노드(Node)와 간선(Edge)으로 표현됩니다. 이때 노드는 정점(Vertext)이라고도 불립니다. 일반적으로 노드와 간선은 각각 도시와 도시를 잇는 도로를 예시로 많이 표현됩니다. 즉, A 도시(노드)와 B 도시(노드)가 있을 때, A 도시에서 B 도시로 이동하기 위해 도로(간선)를 거친다고 생각하시면 노드와 간선에 대한 이해가 쉬울 것입니다. 그래프 탐색? 그래프 탐색이란 하나의 노드에서 시작해서 다른 노드들을 방문하는 것을 의미합니다. 노드 인접? 두 노드가 간선으로 연결되어 있다면, '두 노드는 인접(Adjacent)해 있다'라고 말합니다. 그래프 자료구조 관련 용어 정리 그래프(트..

본 포스팅에서는 다이나믹(동적) 프로그래밍에 대해 알아봅니다. 📚 목차 1. 다이나믹 프로그래밍이란? 2. 다이나믹 프로그래밍 예제 3. 재귀함수 기반 구현 3.1. 소스코드 3.2. 문제점 3.2.1. 연산 복잡성 3.2.2. 문제 발생의 원인 3.2.3. 문제 해결 방안 4. 다이나믹 프로그래밍 기반 구현 4.1. 탑 다운 방식(재귀함수 활용) 4.1.1. 메모이제이션이란? 4.1.2. 소스코드 4.1.3. 특징 4.2. 바텀 업 방식(반복문 활용) 4.2.1. 소스코드 4.2.2. 특징 1. 다이나믹 프로그래밍이란? 다이나믹(동적) 프로그래밍은 큰 문제를 작은 문제로 나누어 연산 속도와 메모리를 최대한으로 활용하기 위한 기법입니다. 특정 값을 얻기 위해 매번 같은 결과를 반환하는 연산을 굳이 반복해..

본 포스팅에서는 이진 탐색(Binary Search) 알고리즘에 대해 알아봅니다. 📚 목차 1. 이진 탐색이란? 2. 이진 탐색의 동작 과정 3. 이진 탐색의 시간 복잡도 4. 이진 탐색 구현(Python) 1. 이진 탐색이란? 이진 탐색은 탐색의 범위를 절반씩 좁혀가며 데이터를 탐색하는 알고리즘입니다. 이진탐색 알고리즘은 리스트 내 데이터가 어느 정도 정렬되어 있어야만 사용 가능하며 데이터가 무작위로 정렬되어 있다면 사용할 수 없습니다. 이진 탐색 알고리즘은 입력 데이터가 많거나(e.g., 1,000만 개 이상) 탐색 범위의 크기가 매우 넓을 때(e.g., 1,000억 이상) 효과적으로 문제를 해결할 수 있습니다. 2. 이진 탐색의 동작 과정 이진 탐색의 동작 과정에 대해 이해하기 위해서는 순차 탐색(..