본문 바로가기

알고리즘24

[알고리즘] 다익스트라 알고리즘 Goal - 다익스트라 알고리즘을 이해하고 활용할 수 있다. ✔ - 다익스트라 알고리즘을 구현할 수 있다. ✔ 다익스트라 알고리즘 그래프 탐색 문제와 유사하나 정점 간의 간선에 가중치가 있어 경로 상의 가중치를 모두 더했을 때 가장 최소가 되는 경로를 구하는 문제이다. 그냥 그래프 탐색으로 모든 경로를 탐색하여 최솟값을 구할 수 있으나, 보통 시간 초과 오류가 난다. 다이나믹 프로그래밍을 사용해 그래프 탐색을 최대한 최소화 하는 것이 이 알고리즘의 기본 아이디어이다. 간단하게는 그래프 탐색과 다이나믹 프로그래밍을 함께 활용하는 것이라고 이해하면 좋다. 다익스트라 알고리즘의 원리 탐색을 시작할 점을 잡는다. (거리의 합이 중요하므로 시작점은 하나만 잡을 수 있다.) 해당 그래프 주위의 간선들을 탐색하여 그.. 2022. 8. 2.
[BOJ 1987 파이썬] 벽 부수고 이동하기 BFS 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 .. 2022. 7. 27.
[BOJ 1987 파이썬] 알파벳 백트래킹 DFS 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 .. 2022. 7. 4.
[BOJ 7562 파이썬] 나이트의 이동 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net 문제 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까? 입력 입력의 첫째 줄에는 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 세 줄로 이루어져 있다. 첫째 줄에는 체스판의 한 변의 길이 l(4 ≤ l ≤ 300)이 주어진다. 체스판의 크기는 l × l이다. 체스판의 각 칸은 두 수의 쌍 {0, ..., l-1.. 2022. 7. 3.

티스토리툴바