Study/Algorithm4 [Algorithm] 다익스트라(Dijkstra) 알고리즘 그래프에서 최단 경로를 구하는 문제를 본적이 있으신가요?일반적으로 최단 경로는 아래 내용을 의미합니다. 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에 간선의 가중치의 합이 최소인 경로 이러한 최단 경로를 구하는 알고리즘은 여러가지가 있는데요,이번 포스트에서는 최단 경로 알고리즘 중 하나인 "다익스트라(Dijkstra)" 알고리즘에 대해 알아보도록 하겠습니다!다익스트라 알고리즘이란?다익스트라 알고리즘은 하나의 출발 노드에서 다른 모든 노드까지의 최단 거리를 찾는 알고리즘입니다. 이 알고리즘은 보통 우선순위 큐를 사용해 구현하며, 가중치가 양수인 그래프에서 효과적으로 사용됩니다. 핵심은, 한 번의 실행으로 하나의 출발지로부터 모든 목적지까지의 최단 경로를 구할 수 있다는 것입니다. 동작 방식.. 2024. 11. 12. [Algorithm] 진법 변환 본 포스트는 진법 변환에 대해 공부한 내용을 정리한 것입니다. 사실 이게 알고리즘..이라기엔 좀 애매하지만..코딩 테스트는 기본적인 수학을 요구하는 경우도 많으니, 진법 변환은 꼭 알아두셔야 합니다!대표적인 진수10진수 : 사람이 사용하는 진수, 수 하나를 0 ~ 9로 표현2진수 : 컴퓨터가 사용하는 진수, 수 하나를 0, 1로 표현8진수 : 2진수를 더 가독성 있게 사용 (거의 사용하지 않음)16진수 : 2진수를 더 가독성 있게 사용, 수 하나를 0, 1, ..., 8, 9, A, B, C, D, E, F로 표현프로그래밍에서는 대표적으로 10진수, 2진수, 16진수를 많이 사용합니다. 그런데 16진수는 뭔가 이상하지 않나요?10진수는 사람이 쓰니까 당연히 잘 사용될거고, 2진수는 컴퓨터가 0, 1로 이.. 2024. 8. 31. [Algorithm] 조합을 구현해보자 이번 포스트는 파이썬에서 조합을 구현하는 방식에 대해 이야기해보려 합니다. 크게 두 가지 방식으로 구현해보겠습니다.1. 중첩 반복문2. 재귀중첩 반복문으로 5C3 구현하기'ABCDE' 문자열 요소들에 대해 for를 활용하여 5C3을 구현해보겠습니다.arr = 'ABCDE'N, R = len(arr), 3 # 5C3 = 10for i in range(N - 2): # 첫 번째 요소 선택 for j in range(i + 1, N - 1): # 두 번째 요소 선택 for k in range(j + 1, N): # 세 번째 요소 선택 print(arr[i], arr[j], arr[k]) 처음 보면 코드가 좀 난해할 수 있습.. 2024. 8. 18. [Algorithm] 순열을 구현해보자 이번 포스트는 파이썬에서 순열을 구현하는 방식에 대해 이야기해보려 합니다. 크게 두 가지 방식에 대해 다뤄보겠습니다.1. 방문 리스트 활용 (반복 / 재귀) 2. 교환 활용 (반복 / 재귀) 먼저 단순히 반복문으로 구현해보고, 다음은 이를 재귀로 구현해볼 것입니다.방문 리스트를 통해서 순열 생성하기 (반복 구조)for 반복문을 이용하여 [1, 2, 3]에 대해 순열 리스트를 생성해보겠습니다.arr = [1, 2, 3]N = len(arr)visit = [0] * N # 요소의 선택 여부 저장order = [0] * N # 실제 순열의 순서를 저장# =============================================for i in range(N): # 첫번째 요소 선택 if.. 2024. 8. 18. 이전 1 다음
