본문 바로가기
반응형

알고리즘80

[Python] Baekjoon - 13460. 구슬 탈출 2 구슬 탈출 2 문제는 벽과 하나의 구멍으로 이루어진 N x M 크기의 보드판에 두개의 구슬을 넣고 기울여서 하나의 구슬만 빼내기까지의 최소 기울임 횟수를 구하는 문제다. 그래프 탐색 알고리즘 중 BFS를 통해 해결할 수 있다. 백준 13460번 구슬 탈출 2 문제 정보 알고리즘 분류 구현 그래프 탐색 BFS 난이도 골드 2 구슬 탈출 2문제 요약 NxM 보드판은 벽과 하나의 구멍으로 이루어져있다. 구슬 R과 B를 보드판에 넣고 보드판을 상하좌우로 기울일때, 구슬 R만 구멍에 빠지기까지의 최소 기울임 횟수를 구하라. 문제 풀이 방법 과정 최소 횟수를 구하는 문제이므로 BFS를 사용 구슬 R과 B가 같은 곳에 위치할 수 없으므로 기울이는 방향에 더 앞쪽에 있는 구슬을 먼저 이동시킴 두 구슬이 방문했던 좌표를.. 2021. 9. 11.
[Python] Baekjoon - 2239. 스도쿠 백준 2239번 스도쿠 문제는 일반적인 스도쿠 문제를 백트래킹 기법을 사용하여 해결하는 문제다. 빈칸이 있는 9칸 스도쿠 퍼즐이 주어졌을 때 빈칸을 모두 채워서 출력하는 문제이며 사전 순으로 가장 빠른 답을 출력해야 한다. 난이도는 골드 4이다. 백준 2239번 스도쿠 문제 정보 알고리즘 분류 - 백트래킹 난이도 - 골드 4 스도쿠 문제 요약 9x9 크기의 스도쿠에 빈칸들이 주어졌을 때, 빈칸을 모두 채워서 출력하는 문제다. 사전 순으로 가장 빠른 답을 출력한다. 문제 풀이 방법 1 (일반적인 방식) 과정 스도쿠 보드판을 입력받을 때 빈칸들의 좌표를 따로 저장해둔다. 모든 빈칸들에 대해서 백트래킹 수행한다. 각 빈칸에서 넣을 수 있는 숫자들을 구해서 해당 숫자들 넣고 다음 depth로 진행한다. 넣을 수.. 2021. 8. 5.
[Python] Baekjoon - 12852. 1로 만들기 2 1로 만들기 2 문제는 주어진 세 가지 연산을 이용해서 N을 1로 만드는 최소 연산 횟수와 연산 중간 과정을 구하는 문제다. 그래프 탐색 또는 다이내믹 프로그래밍 기법을 통해 해결할 수 있다. 이 글에서는 두 가지 경우의 해결방안을 모두 제시한다. 난이도는 실버 1이다. 백준 12852번 1로 만들기 2 문제 정보 알고리즘 분류 - 그래프 탐색 - 다이내믹 프로그래밍 (DP) 난이도 - 실버 1 1로 만들기 2 문제 요약 아래의 연산들을 사용하여 입력 N을 1로 만드는 최소 연산 횟수와 중간 숫자들(경로)을 구하는 문제다. X - 1 X가 2로 나누어 떨어지면 2로 나누기 X가 3으로 나누어 떨어지면 3으로 나누기 문제 풀이 방법 1 과정 최소 연산 횟수를 구하는 문제이기 때문에 BFS를 사용한다. 각 .. 2021. 7. 27.
[Python] Baekjoon - 2178. 미로 탐색 백준 2178번 미로 탐색 문제는 세로 N, 가로 M 길이의 미로의 왼쪽 맨 위칸에서 오른쪽 맨 아래칸까지 이동할 때 거쳐가는 칸의 최소 개수를 구하는 문제다. 최단 거리를 찾는 문제이므로 그래프 탐색 알고리즘 중 너비 우선 탐색(BFS)을 이용한다. 난이도는 실버 1이다. 백준 2178번 미로 탐색 문제 정보 알고리즘 분류 - 그래프 탐색 난이도 - 실버 1 미로 탐색 문제 요약 이동 불가능한 칸 0과 이동 가능한 칸 1로 구성된 NxM 크기의 미로가 있다. (1,1)에서 출발하여 (N, M)에 도착하기까지 거쳐가는 칸의 최소 개수를 구하는 문제다. 인접한 칸으로만 이동 가능하다. 문제 풀이 과정 최단거리 문제이기 때문에 그래프 탐색 알고리즘 BFS를 사용한다. 한번 방문한 곳은 다시 방문하지 않도록 .. 2021. 7. 27.
반응형

티스토리툴바