elevne's Study Note

최단경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 최단경로 알고리즘 유형에는 다양한 종류가 있는데, 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다고 한다. 1. 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘이다. 다익스트라 최단경로 알고리즘은 기본적으로 그리디 알고리즘으로 분류된다. 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문이다. 출발 노드를 설정한다 최단 거리 테이블을 초기화한다 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해서 최단 거리 테이블을 갱신한다..

다이나믹 프로그래밍, 동적 프로그래밍은 연산 속도와 메모리 공간을 최대한으로 활용할 수 있게끔 해주는 효율적인 알고리즘이다. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 문제로 피보나치 수열 문제가 있다. 수학자들은 점화식을 통해 수열의 항이 이어지는 형태를 간결하게 표현한다. 피보나치 점화식은 인접 3 항 간 점화식이다. 이러한 점화식에 따라 실제로 피보나치를 구하는 함수를 작성하면, 재귀함수를 작성해볼 수 있다. 하지만 재귀함수를 사용하면, f(n) 함수에서 n 의 값이 커질수록 수행 시간이 기하급수적으로 늘어나게 된다. ( n 이 30 일 때, 약 10 억 가량의 연산을 수행한다) 재귀함수를 사용하는 것보다는, 다이나믹 프로그래밍을 사용하면 효율적으로 문제를 해결할 수 있다. 아래 조건들이 만족..

오늘은 이진탐색에 대해서 알아보았다. 순차탐색: 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 (가장 기본적인 방법) 이진탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (시작점, 끝점, 중간점 이용하여 탐색범위를 설정한다) 이진탐색을 진행할 때, 우선 순서대로 정렬된 리스트에서 시작점, 중간점, 끝점을 지정한다. 그 후, 찾고자하는 값을 중간점의 값과 비교하여 찾고자하는 값이 중간점을 기준으로 왼쪽에 있는지 오른쪽에 있는지 알아본다. 이러한 방식으로 범위를 절반으로 줄인 뒤, 위 과정을 반복하는 것이다. 이진탐색의 시간복잡도는 log N 을 보장한다. 코드로 확인하자면, 아래와 같이 적어줄 수 있다. 재귀함수 사용 코드: # 이..

정렬이란 데이터를 특정한 기준에 따라 순서대로 나열하는 것을 말한다. 문제 상황에 따라서 적절한 정렬 알고리즘이 공식처럼 사용된다고 한다. 정렬 알고리즘은 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬 등 아주 많은 종류가 있다. 1. 선택정렬 선택정렬이란 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 방법이다. 가장 작은 것을 선택해서 앞으로 보내는 과정을 반복해서 수행하다 보면, 전체 데이터의 정렬이 이루어지게 되는 것이다. 아래와 같은 이중 반복문, 스와프 코드로 간단하게 구현해볼 수 있다. def selection_sort(arr): for i in range(len(arr) - 1): min_idx = i for j in range(i + 1..

DFS, BFS 는 대표적인 그래프 탐색 알고리즘이다. (탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다) DFS, BFS 에 대해 공부하기 위해 우선 몇 가지 자료구조에 대해 알아본다. 스택 자료구조라는 것이 있다. 스택 자료구조는 먼저 들어온 데이터가 나중에 나가는 선입후출의 자료구조를 갖는다. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. Python 에서 stack 에 데이터를 추가할 때는 append 함수, 원소를 삭제할 때는 pop 함수를 사용한다. 다음으로는 큐 자료구조가 있다. 큐는 먼저 들어 온 데이터가 먼저 나가는 선입선출의 자료구조를 갖는다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다. Python 에서 큐 자료구조를 활용하..

알고리즘 자체는 간단하지만 코드가 길어지거나 작성하기 까다로운 문제들이 있다. 이러한 문제들에는 모든 경우의 수를 주저 없이 다 계산하는 방식을 사용하는 완전탐색, 제시한 알고리즘을 한 단계씩 차례대로 직접 수행해야 하는 시뮬레이션 유형이 있다. (해당 책에서는 둘을 묶어 구현 파트에 넣어두었다) 두 유형에 해당하는 문제들을 하나씩 살펴보았다. 알고리즘 문제에서는 행렬을 많이 사용하게 된다. 2차원 행렬 위에서 캐릭터가 특정 규칙에 의해 좌표를 이동하는 등의 문제가 자주 출제된다고 한다. 아래는 하나의 예시 문제이다. 문제 1) 여행가 A는 N x N 크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 아래 좌표는 (..

Greedy Algorithm 은 현재 상황에서 지금 당장! 좋은 것만 고르는 방법을 의미한다. 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 아래와 같은 예시 문제 상황을 보면 이해가 쉽다. [문제 상황] 루트 노드부터 시작하여 거쳐가는 노드 값의 합을 최대로 만들고 싶을 때 어떻게 이동해야 할까? 그리디 알고리즘은 위 문제상황에서 단순히 매 상황에서 가장 큰 값만 고르는 방법을 택한다. 위 노드에서 7, 9 를 순서대로 고르는 것이 아니라 10, 4 를 선택하게 되는 것이다. (그래서 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수는 없다) 그리디 알고리즘의 대표적인 문제로 동전 거스름 문제가 있다. 문제 1) 당신은 음식점의 계산을 도와..

복잡도란 알고리즘의 성능을 나타내는 척도이다. 복잡도는 시간복잡도와 공간복잡도로 나누어진다. 시간복잡도: 알고리즘을 위해 필요한 연산의 횟수 (알고리즘이 얼마나 오래 걸리는가) 공간복잡도: 알고리즘을 위해 필요한 메모리의 양 (알고리즘이 얼마나 많은 메모리를 차지하는가) 동일한 기능을 수행하는 알고리즘이 있을 때 시간복잡도와 공간복잡도가 낮은 것이 더욱 좋은 것으로 일반적으로 해석될 수 있는 것이다. 또한, 효율적인 알고리즘을 사용한다고 했을 때 일반적으로 시간복잡도와 공간복잡도는 일종의 Trade-off 관계가 성립된다고 한다. 메모리를 조금 더 많이 사용하는 대신 반복되는 연산을 생략하거나 더 많은 정보를 관리하면서 계산의 복잡도를 줄일 수 있는 것이다. (이 때 메모리를 더 소모하는 대신에 얻을 수..