루바의 여정

플로이드 워셜 알고리즘 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘이다. 플로이드 워셜 알고리즘은 다익스트라 알고리즘처럼 단계마다 최단 거리를 가지는 노드에 대해 최단 거리 테이블을 갱신하는 방식으로 동작한다. 하지만 매 단계마다 최단 거리를 갖는 노드를 찾을 필요가 없다는 점이 다르다. 또한, 다익스트라 알고리즘은 1차원 리스트에 최단 거리 테이블을 저장했다면 플로이드 워셜 알고리즘은 2차원 리스트에 최단 거리 정보를 저장한다. 동작 방법 노드의 개수가 N개라고 하면, N번만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신하기 때문에 다이나믹 프로그램이라고 할 수 있다. $0

다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 여러 개의 노드가 있을 때, 특정한 노드에서 출발해 다른 노드로 가는 최단 경로를 구해주는 알고리즘이다. 다익스트라 알고리즘은 '음의 간선', 즉 0보다 작은 값을 가지는 간선이 없을 때 정상적으로 동작한다. 다익스트라 알고리즘의 구현 방법에는 2가지가 존재한다. 첫 번째 방법은 순차 탐색을 사용하는 방법이다. 매 단계마다 1개의 노드의 최단 거리를 탐색한다. 두 번째 방법은 우선순위 큐를 사용해 첫 번째 방법에서 시간을 줄인 방법이다. 동작 방법 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 본인 노드는 0으로 초기화하고, 그 외 노드는 무한대로 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리 테이블의 값이 가장 짧은 노드를..

이진 탐색 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 탐색 알고리즘이다. 이미 데이터가 정렬되어 있다면 매우 빠르게 타겟값을 찾을 수 있다. 이진 탐색은 위치를 나타내는 변수를 3개를 사용한다. 리스트의 시작점, 끝점, 그리고 중간점이다. 타겟값과 중간점에 있는 데이터를 반복적으로 비교하며 타겟값을 찾는다. 예시 숫자 1, 3, 5, 7, 9, 11, 13, 15, 17, 19가 순서대로 저장되어 있을 때 15를 찾는 과정을 알아보자. 시작점을 리스트의 맨 처음 인덱스([0]), 끝점을 리스트의 맨 뒤 인덱스([9])로 설정한다. 중간점은 0과 9의 중간값인 [4]번 인덱스가 된다.(소수점 이하는 버린다.) 찾고자 하는 값인 15가 중간점의 데이터 값의 9보다 크므로 중간값 이전의 값은 확..

순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 탐색 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 시간만 충분하다면 데이터가 아무리 많아도 원하는 데이터를 찾아낼 수 있다. 예시 숫자 42, 23, 56, 11, 60이 순서대로 저장되어 있을 때 56을 찾는 과정을 알아보자. 준비된 데이터의 앞에서부터 56을 찾는다. 리스트의 맨 앞에는 42가 들어있다. 이는 찾고자 하는 56과 다르므로 다음 데이터로 이동한다. 그 다음에는 23이 들어있다. 이 또한 찾고자 하는 56과 다르므로 다음 데이터로 이동한다. 그 다음에는 56이 들어있다. 이는 찾고자 하는 56과 같으므로 탐색을 마친다. 코드 ## 순차 탐색 함수 ## 매개변수..

퀵 정렬 정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이며 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다. 퀵 정렬은 '피벗'이라는 기준을 가지고 피벗보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법을 사용한다. 동작 방법은 아래와 같다. 1. 리스트에서 첫 번째 데이터를 피벗으로 설정한다. 2. 리스트의 왼쪽에서부터 피벗보다 큰 데이터를 찾는다. 3. 리스트의 오른쪽에서부터 피벗보다 작은 데이터를 찾는다. 4. 작은 데이터와 큰 데이터가 서로 엇갈린 위치에서 발견되었다면 작은 데이터와 피벗의 위치를 바꾼다. 5. 엇갈리지 않았다면 작은 데이터와 큰 데이터의 위치를 바꾼다. 예시 숫자 10, 20, 6, 39, 40, 1, 16, 9가 순서대로 저장되어 있다. 리스트의 첫 ..

계수 정렬(Count Sort) 특정한 조건이 부합할 때만 사용할 수 있는 정렬 방법이다. 하지만 매우 빠른 속도를 가지고 있다. 여기서 특정한 조건은 아래와 같다. 1. 데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있다. 2. 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적이다. 계수 정렬은 가장 큰 데이터와 가장 작은 데이터 차이만큼의 크기를 갖는 리스트를 선언해야 하기 때문에 위와 같은 특정한 조건을 갖는다. 즉, 계수 정렬은 별도의 리스트를 선언하고 그 안에 정렬에 대한 정보를 담는 특징이 있다. 계수 정렬은 모든 범위를 포함하는 인덱스를 갖는 리스트를 생성한 후, 앞에서부터 데이터를 읽어나가며 해당하는 데이터에 맞는 인덱스에 1을 추가한다. 예시 숫..

삽입 정렬(Insertion Sort) 리스트가 정렬된 부분과 정렬 안된 부분으로 나뉜다. 정렬 안된 부분의 가장 왼쪽 원소를 정렬된 부분의 적절한 위치에 '삽입'하는 방식의 알고리즘이다. 선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적으로 동작한다. 동작 방법 숫자 4, 3, 40, 5, 23, 18, 1 이 순서대로 준비되어 있다. 1) 첫 번째 원소 '4'는 정렬되어 있다고 판단하고, 두 번째 원소인 '3'이 어떤 위치로 들어갈지 판단한다. 화살표가 들어갈 수 있는 위치이고 빨간색 화살표가 들어가야하는 위치이다. 2) 이어서 '40'이 어떤 위치로 들어갈 지 판단한다. 원래 자리가 '40'이 들어갈 자리이다. 3) 이어서 '5'가 어떤 위치로 들어갈 지 판단한다. 4) 마지막으로 '1..

선택 정렬(Selection Sort) 리스트에서 아직 정렬 안된 부분의 원소들 중에서 최솟값을 '선택'하여 정렬 안된 부분의 가장 왼쪽의 원소와 교환하는 정렬 알고리즘. 동작 방법 숫자 20, 4, 2, 1, 50, 31, 13, 7 이 준비되어 있다. 정렬된 데이터는 색으로 표시한다. 1) 정렬되지 않은 원소 중 가장 작은 '1'을 선택해 정렬 안된 부분의 가장 왼쪽에 있는 '20'과 교환해준다. 교환된 '1'이 가장 왼쪽에 위치하고 '20'은 '1'의 자리에 들어있다. 2) 정렬되지 않은 원소 중 가장 작은 '2'를 선택해 정렬 안된 부분의 가장 왼쪽에 있는 '4'와 교환해준다. 교환된 '2'가 '1' 다음에 정렬되고 '4'는 '2'의 자리에 들어있다. 3) '4'는 정렬되지 않은 수 중에서 가장 ..

큐 정의: 삽입과 삭제가 양 끝에서 각각 수행되는 자료구조. 동작: 먼저 들어온 데이터가 먼저 나가는 형식, 선입선출의 자료구조 동작 방법 숫자 5, 10, 2, 7을 순서대로 큐에 삽입하면 아래와 같은 그림으로 들어간다. 먼저 들어간 5가 큐의 맨 앞에 자리하고 그 뒤로 10-2-7이 이어서 저장되어 있다. 이제 큐를 비우기 위해 저장된 모든 데이터들을 삭제해보면 아래 그림과 같이 동작한다. 맨 먼저 큐에 삽입된 5가 가장 먼저 큐에서 삭제되고 삽입 순서인 10-2-7이 순서대로 큐에서 삭제된다. 이처럼 큐는 먼저 들어간 데이터가 먼저 삭제되는 것을 알 수 있다. 큐의 연산 큐는 스택과 달리 deque 라이브러리를 사용하는데 이는 시간 복잡도가 증가하는 것을 방지하기 위한 것이다. from collec..

스택 정의: 한 쪽 끝에서만 데이터(item)을 삭제하거나 새로운 항목을 저장하는 자료구조. 동작: 먼저 들어간 데이터가 먼저 나가는 형식, 선입후출 구조 동작 방법 숫자 6, 7, 3, 5를 순서대로 스택에 입력하면 아래와 같은 그림으로 들어간다. 먼저 들어간 6이 제일 안쪽에 존재하고, 7-3-5가 이어서 스택에 저장되어 있는 것을 확인할 수 있다. 이제 스택을 비우기 위해 스택에 저장된 항목들을 모두 삭제해보자. 스택의 맨 앞에 저장된 5가 가장 먼저 출력되고, 3-7-6이 이어서 삭제되는 것을 확인할 수 있다. 이처럼 스택은 먼저 들어간 항목일수록 나중에 삭제된다는 것을 알 수 있다. 스택의 연산 삽입 연산: 스택에 새로운 항목을 입력하는 연산이다. push라고 한다. 파이썬의 경우 append(..