백준 1504번 : 특정한 최단 경로

2024.02.10 - [알고리즘] - 다익스트라 알고리즘이 문제는 다익스트라 알고리즘을 활용하여 최단 경로를 찾는 문제입니다. 다익스트라 알고리즘은 한 정점에서 다른 모든 정점으로 가는 최단 거리를 찾을 때 사용되는 알고리즘으로, 가중치가 있는 그래프에서 음수 가중치가 없을 때 효율적으로 사용할 수 있습니다.다익스트라 알고리즘의 개념다익스트라 알고리즘의 핵심은 시작 정점에서 다른 정점들로 가는 최단 경로를 점진적으로 찾는 것입니다. 최단 거리를 기록하면서, 방문하지 않은 정점 중 현재까지 가장 짧은 거리로 도달할 수 있는 정점을 선택해 이동하며 최단 경로를 찾아나갑니다.다익스트라 알고리즘의 동작 과정초기화: 시작 정점의 거리를 0으로 설정하고, 다른 모든 정점의 거리는 무한대로 초기화합니다.정점 선택:..

• format_list_bulleted 알고리즘/백준
• · 2024. 11. 1.
• textsms

백준 1012번 -유기농 배추

BFS와 DFS 모두 활용할 수 있는 연습문제라고 생각하면 된다. 너비 우선 탐색(BFS)을 사용하는 이유최단 경로 탐색에 유리하다.BFS는 탐색을 가까운 노드부터 순차적으로 넓혀가며 수행하기 때문에, 시작 지점에서 특정 목표 지점까지의 최단 경로를 찾을 때 유리하다. 예를 들어 미로 탐색에서 출발점에서 도착점까지의 최단 경로를 찾을 때, BFS는 가장 먼저 목표 지점에 도달하는 경로가 최단 경로가 되므로 이를 바로 반환할 수 있다.모든 노드를 고르게 탐색한다.BFS는 한 지점에서 출발하여 깊이를 하나씩 늘리며 탐색하므로, 모든 노드를 고르게 탐색한다. 모든 인접 노드들을 차례로 확인하며 탐색하므로 특정 노드들이 더 깊게 우선 탐색되는 일이 없다. 이 점은 깊이 우선 탐색(DFS)과 다르며, 특히 그래프..

• format_list_bulleted 알고리즘/백준
• · 2024. 10. 29.
• textsms

백준6603: 로또

📌 문제를 뜯어보자숫자 1부터 49까지 중에서,테스트 케이스마다 몇 개의 숫자(k개)가 주어지고,그 중 6개를 뽑는 모든 조합을 출력해야 함.마지막 줄에 0이 들어오면 입력 종료.각 케이스는 출력할 때 조합을 오름차순, 케이스 사이에는 빈 줄 하나.예를 들어 7 1 2 3 4 5 6 7이 들어오면,1~7 중에서 6개 뽑는 조합들을 전부 출력해야 되는 식.🤔 접근 방법처음엔 조합을 직접 구현해볼까 했는데,파이썬에선 이럴 때 itertools 모듈의 combinations가 진짜 편하다.그냥 combinations(리스트, 6) 하면 알아서 6개짜리 조합을 다 만들어준다.그래서 입력만 잘 처리하고, 조합 돌려서 출력하면 끝.from itertools import combinationsdef func(ar..

• format_list_bulleted 알고리즘/백준
• · 2024. 8. 5.
• textsms