본문 바로가기

알고리즘39

숨바꼭질3 숨바꼭질 3 백준 13549번 문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 이 문제는 다음 노드로 이동(걷거나 순간이동)할 때의 가중치가 1 또는 0으로 균일하지 않다. BFS로 풀 수 있는 문제들은 가중치가 균일해서 Queue에 가중치 합이 작은 순으로 순차적으로 들어오게 되어있다. 그러나 이 문제는 가중치가 균일하지 않기 때문에 일반적인 BFS 방식으로 문제를.. 2023. 1. 9.
퍼-즐 퍼-즐 백준 1525번 문제 https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 우선 나는 2차 배열인 퍼즐을 1차 배열로 변환하고 문제를 풀었다. 문제를 풀 때, 주어진 퍼즐의 원소를 이동시켜야 하는데 2차 배열보다는 1차 배열이 다루기 더 쉬울 거 같았기 때문이다. 2차 배열의 각 위치를 1차 배열로 표현할 수 있기 때문에 1차 배열로 변환해서 문제를 푸는데 전혀 문제가 되지 않는다. [1차 배열로 변환] 문제는 간단하다 목표 상태에 도달하기 위한 행위의 최솟값을 구하는 것이기 때문.. 2023. 1. 2.
내리막-길 내리막-길 백준 1520번 문제 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 d(i, j) 를 시작점에서부터 i, j로 갈 수 있는 경우의 수를 의미한다고 하자. 그러면 다음과 같은 점화식이 성립한다. d(i, j) = SUM(d(i - 1, j), d(i, j + 1), d(i + 1, j), d(i, j - 1)) (단, (i,j)의 높이보다 높을 경우만 더해준다.) 따라서 도착점을 (i, j)라고 할 .. 2022. 9. 8.
회-문 회-문 백준 17609번 문제 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 1. 문제 2. 풀이 2.1 풀이 방법 문자열의 앞과 뒤를 비교하며 회문인지 검사한다. 만약 탐색 중 앞의 문자 또는 뒤의 문자를 지웠을 때, 회문이 될 수 있는 가능성이 있다면 앞의 문자 또는 뒤의 문자를 지우고, 탐색하지 않은 나머지 문자열이 회문인지를 확인한다. 문자열 전체가 회문일 때 0을 반환. 문자를 하나 지웠을 때 나머지 문자열이 회문이 된다면 1을 반환. 문자를 하나 지웠을 대 나머.. 2022. 8. 31.

티스토리툴바