![]()
1. 최단 경로 알고리즘이란?최단 경로 알고리즘은 그래프에서 한 정점에서 다른 정점까지 가는 데 필요한 최단 거리를 찾는 알고리즘입니다. 여기서 ‘최단’의 의미는 경로 상의 가중치 합이 가장 작다는 뜻입니다. 예를 들어, 지도에서 두 도시를 최단 거리로 연결하는 방법을 찾는 것이 최단 경로 문제라고 볼 수 있습니다.방금 제가 풀고 있던 이 문제: https://www.acmicpc.net/problem/16928 에서의 '정점'은 게임판의 칸이 될 것이며, 각 칸마다 이동하는 것이 경로를 통해 이동하는 상황이 되는 것입니다. 다만, 이 문제에서는 각 경로의 가중치가 모두 1로 동일한 상황이며, 이 경우에는 어떤 알고리즘으로 푸는 게 적합한지 글의 마지막 부분에 언급하도록 하겠습니다. 2. 대표적인 최단 ..
![]()
정렬 알고리즘 문제를 푸는 중에 매우 깔끔한 코드를 발견했습니다.저는 열심히 퀵소트로 문제를 풀었는데, 어떤 분들은 Arrays.sort와 lambda 함수를 사용해서 아주 깔끔한 코드로 풀이를 완성한 것이었죠!!! 저는 그런 식으로 코딩해본 적이 없어서 한 줄씩 뜯어봤는데,사실 '저 코드가 도대체 왜 오름차순 정렬을 하는 코드인거지???' 하는 생각이 계속 들었습니다. 그래서 다시 찾아보면서 이해를 하고 메모를 해두려고 합니당 정렬하는 부분만 작성해둔 예시 코드는 다음과 같습니다.// 예시 코드import java.util.Arrays;public class Main { public static void main(String[] args) { int[] arr1d = new int[]..
이진탐색 알고리즘은 선형 탐색 알고리즘과 달리, 정렬된 리스트를 전제로 한다. 정렬된 리스트가 아니면 이 알고리즘은 적용이 불가능하다. 이진탐색 알고리즘이 무엇인지는, 다른 자료들을 통해 이미 충분히 많이 설명되어 있으므로 설명을 생략한다. 사용한 언어는 python이고 재귀를 사용한 방법, if-else문을 사용한 방법 두 가지를 모두 살펴보자. 문제는 찾고자 하는 원소 element가 리스트 안에 존재하면 그 원소의 인덱스를 리턴하고, 없으면 None을 리턴하는 것이다. 1. 재귀 def binary_search(element, lst): mid = len(lst)//2 if not len(lst): return None elif element == lst[mid]: return mid elif el..
