본문 바로가기

정렬/탐색34

[Algorithm] 다익스트라(Dijkstra), 지름길의 지름길로 찾는 최적경로 다익스트라는 출발지부터 목적지까지의 최적 경로를 탐색해주는 알고리즘입니다. 다익스트라의 이론적 설명과 구현 방법, 경로 추적까지 살펴보겠습니다. [ Contents ] 1. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra): 현재까지 찾은 최적경로를 바탕으로 목적지까지의 최단경로를 탐색하는 알고리즘 출발지에서 가까운 지점부터 차례대로 최단경로를 탐색하며, 목적지까지의 최단경로를 탐색하는 알고리즘입니다. 그리디 알고리즘 기법으로, 한 번 결정된 최단 경로는 절대 바뀌지 않으며 이를 바탕으로 목적지까지의 최단경로를 계산합니다. 예를 들어, 출발지 A에서 목적지 D까지의 최단경로를 구해봅시다. 다익스트라 알고리즘에서는 A 주변 노드부터 최단거리를 계산하고, 점차 넓혀갑니다. 아직 A와의 거리를.. 2022. 3. 22.
[탐색/백트래킹] 백준 9663 N-Queen - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 풀이 가로 세로 대각선에 겹치지 않게 N개의 퀸을 놓는 가짓수를 구하는 문제입니다. 2022.03.20 - [Algorithm] - [Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기 [Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기 DFS 탐색 중 가능성이 없는 방향은 가지 않는 '백트래킹' 기법에 대해서 알아보겠습니다. [ Contents ] 1... 2022. 3. 21.
[Algorithm] 백트래킹(Backtracking): 안될 싹은 미리미리 가지치기 DFS 탐색 중 가능성이 없는 방향은 가지 않는 '백트래킹' 기법에 대해서 알아보겠습니다. [ Contents ] 1. DFS 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. DFS(Depth First Search) 깊이 우선 탐색(DFS): 방문하지 않은 인접. star7sss.tistory.com 깊이 우선 탐색(DFS): 방문하지 않은 인접 노드가 없을 때까지 탐색하여 한 곳씩 마무리하는 방식 DFS는 끝이 나올.. 2022. 3. 20.
[탐색/플로이드] 백준 11404 플로이드 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 2. 문제 풀이 플로이드 알고리즘을 이용해서 최단경로를 탐색하는 문제입니다. 2022.02.28 - [Algorithm] - [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 모든 쌍의 최단 경로를 '플로이드 - 와샬' 알고리즘으로 구하는 방법을 알아보고, 구현 코드도 살펴보겠습니다. [ Contents ] 1. 모든 쌍의 최단 경로 위 .. 2022. 3. 16.
[탐색/구현] 백준 14500 테트로미노 - 파이썬(Python) [ Contents ] 1. 문제 (링크 참조) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 2. 문제 풀이 테트릭스 모양으로 탐색한 뒤, 가장 점수를 출력하는 문제입니다. 2022.02.23 - [Algorithm] - [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 [Algorithm] 깊이 우선 탐색(DFS), 끝까지 찾고 넘어가자 DFS는 인접노드가 없을 때까지, 끝까지 탐색하는 알고리즘입니다. 스택을 이용한 DFS 구현방법과 코드를 알아보겠습니다. [ Contents ] 1. .. 2022. 3. 14.
[정렬/탐색] 백준 11004 K번째 수 - Python [ Contents ] 1. 문제 (링크 참조) 11004번: K번째 수 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 풀이 수열 A를 오름차순 정렬한 뒤, K번째 수를 구하는 문제입니다. 3. 코드 import sys input = sys.stdin.readline N, K = map(int, input().split()) numlist = list(map(int, input().split())) numlist.sort() print(numlist[K-1]) 파이썬의 정렬 라이브러리를 이용하면 쉽게 해결할 수 있습니다. 정렬한 뒤, K번째 항목을 출력합니다. 2022. 2. 28.
[탐색/플로이드] 백준 1389 케빈 베이컨의 6단계 법칙 - Python [ Contents ] 1. 문제 (링크 참조) 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 2. 문제 풀이 가장 인싸친구를 찾는 문제입니다. 케빈 베이컨의 6단계 법칙은 '인적 네트워크'의 중요성을 대두할 때 많이 언급하죠. 여섯 다리(지인)만 거치면 지구촌 모든 사람과 만날 수 있다는 허상(?)의 법칙입니다. 애초에 단계를 거칠 때마다 지인이 자신의 모든 지인에게 물어보고 성실하게 답해준다는 가정이 잘못됐죠. 2022.02.28 - [Algorithm] .. 2022. 2. 28.
[탐색/플로이드] 백준 11403 경로 찾기 - Python [ Contents ] 1. 문제 (링크 참조) 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 2. 문제 풀이 인접리스트가 주어졌을 때, 경유지를 통해 갈 수 있는 경로가 있는지를 구하는 문제입니다. 2022.02.28 - [Algorithm] - [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 [Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 모든 쌍의 최단 경로를 '플로이드 - 와샬' 알고리즘으로 구하는 방법을 알아보고, 구현 코드도 살펴보겠습니다. [ Contents ] 1. 모든 쌍의 최단 경로 위 그래프 그림에서.. 2022. 2. 28.
[Algorithm] 플로이드-와샬, 모든 쌍의 최적경로 구하기 모든 쌍의 최단 경로를 '플로이드 - 와샬' 알고리즘으로 구하는 방법을 알아보고, 구현 코드도 살펴보겠습니다. [ Contents ] 1. 모든 쌍의 최단 경로 위 그래프 그림에서 '노드(Node)'는 원으로 된 지역이고, '간선(Edge)'은 각 지역으로 이동할 수 있는 경로입니다. 간선마다 이동거리 혹은 이동시간에 따른 가중치가 부여됩니다. '모든 쌍의 최단 경로'는 말 그대로, 지역 간 최단거리를 구하는 작업입니다. 보통은 A에서 B로 바로 가면 빠르지만, 경유지를 거쳐서 가는 게 더 지름길일 때도 있죠. 이런 경우를 모두 고려해서 계산해야 합니다. 예를 들어, 위 경로에서는 1->3으로 바로 가는 것보다, 2를 경유해서 가는 게 더 빠릅니다. 2. 플로이드 - 와샬(Floyd-Warshall) 알.. 2022. 2. 28.

티스토리툴바