kkh1902's Algorithm Study

1. 최단 경로 알고리즘 최단 경로 문제란 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 1) 최단 경로 문제의 종류 단일 출발 (single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾는 문제 단일 도착 (single-destination) 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제로 그래프 내의 간선들을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있다. 단일 쌍(single-pair) 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 2) 주요 알고리즘 BFS (완전탐색 알고리즘) 가중치가 없거나 모든 가중치가 동일한 그래프에서 최단경로를 구하는 경우 가장 빠르다 다익스트라 알..

현실에서 우리가 컴퓨터를 이용하여 문제를 해결하려 할 때 컴퓨터로도 해결하기 어려운 문제들이 있을 것이다. 보통 최적의 해를 구하는데 시간이 매우 오래걸리거나 메모리 공간이 많이 필요한 문제 등이 해결하기 어려운 문제들이다. 컴퓨터는 연산 속도에 한계가 있고, 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야하는데 이러한 문제를 해결할 수 있는 대표적인 방법이 다이나믹 프로그래밍 (Dynamic Programming)이다. 글에서는 다이나믹 프로그래밍을 줄여서 DP라고 표현하겠다. DP란 '동적 계획법'이라고도 불리는 알고리즘 큰 문제를 작은 문제로 나누어 푸는 문제를 ..

이분 탐색 / 이진 탐색 (Binary Search) 이진 탐색(이분 탐색) 알고리즘은 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법이다. 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 변수 3개(start, end, mid)를 사용하여 탐색한다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색의 과정이다. 이진 탐색 / 이분 탐색 알고리즘 코드 (Python) 재귀 함수로 구현한 이진 탐색(이분 탐색) # 재귀 함수로 구현한 이진 탐색 def binary_search(array, target, start, end): if start > end: return None mid = (st..

📌 각각의 정렬 알고리즘 특징 📍 선택 정렬(Selection Sort) 선택 정렬은 앞쪽부터 정렬하는 방식이다. 주어진 배열에서 가장 작은 최소값을 찾고 배열의 맨 앞의 값과 위치를 바꾸면서 정렬한다. 선택 정렬은 배열의 최솟값을 찾아 선택하여 정렬한다는 뜻에서 이름이 붙여졌다. 배열에서 최솟값을 찾아야 하기 때문에 비교 횟수는 많지만 실제로 값을 바꾸는 교환 횟수가 적다는 것이 특징이다. 👍 장점 ▶️ 구현이 간단하다. ▶️ 데이터를 하나씩 비교하기 때문에 정밀한 비교가 가능하다. ▶️ 비교하는 횟수에 비해 교환하는 횟수가 적다. 👎 단점 ▶️ 데이터를 하나씩 비교하기 때문에 시간이 오래 걸린다. ▶️ 정렬된 상태에서 새로운 데이터가 추가되면 정렬 효율이 좋지 않다. 소스코드 📍 버블 정렬(Bubbl..

BFS, DFS 두가지 모두 그래프를 탐색하는 방법입니다. 그래프란, 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종을 말하며, 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것을 말합니다. DFS 깊이 우선 탐색 (Depth-First Search) 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말합니다. 예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다. 모든 노드를..

탐욕 알고리즘(Greedy Algorithm)이란? Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다. 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 탐욕 알고리즘 문제를 해결하는 방법 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다. 해답 검사(Solution Check): 원..