DJ's Blog

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net 이 문제에서는 배열 크기를 잘못 설정해줘서 런타임에러(ArrayIndexOutOfBounds)가 났다. 반례를 생각해내서 풀긴 했지만, 바로 생각해내지 못해서 글로 남겨본다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System...

알고리즘 2022. 11. 21. 20:35

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 글을 쓰는 목적은 BFS 알고리즘을 한번 더 정리하고, 뱀과 사다리 게임 문제를 풀면서 놓쳤던 경우의 수를 기록해서 내 생각을 정리하고, 비슷한 실수를 반복하지 않기 위함이다. 위 문제는 그래프 탐색 알고리즘 중에서 BFS, Breadth-First Search 알고리즘에 해당하는 문제이다. 그래프란, 정점과 간선으로 이루어진 자료구조이다. 어떠한..

알고리즘 2022. 11. 11. 00:05

https://www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 이 글을 기재하는 이유는 그래프 탐색 알고리즘인 DFS와 BFS 개념에 대해 스스로 정리하기 위해서 이며, 알고리즘 로직을 잘못 짰을때 찾았던 반례와 잘못 생각했던 부분을 기록하여 나중에 잊어버리더라도 다시 생각하기 위해서이다. 우선, DFS란 그래프를 탐색하는 알고리즘 중에 하나이며 Depth First Search, 깊이 우선 탐색이다. 루트노드 또는 임의의..

알고리즘 2022. 11. 9. 23:54

https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 이 문제는 nmk 공식에 맞는 수열을 만드는 로직을 생각하고, 풀면서 생각하지 못한 여러가지 예외가 많이 나와서 애먹었다. 먼저, m값(길이가 가장 긴 증가하는 부분 수열)과 k값(길이가 가장 긴 감소하는 부분 수열)에 따라서 가능한 n값의 범위가 있다. (13~16번 줄) m 과 k 가 모두 3이라고 가정하면, n이 최소로 될 수 있는 값은 {3, 2, 1, 4, 5} → 5값(m+k-1)을 가질 수 있고 n이 최대로 될 수 있는 값은 {3, 2, 1, 6, 5, 4, 9, 8, 7} → 9값(m*k)을 가질 수 있다. n 안에서 증가하는 수열..

알고리즘 2022. 5. 2. 12:54

https://www.acmicpc.net/problem/1767 1767번: N-Rook II N * M 크기의 체스판에 K개의 룩을 놓을 때, 각 룩이 최대 1개의 룩에만 공격받는 경우의 수를 1,000,001로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 풀이를 보고 한참을 이해하지 못했는데, 내가 애초에 문제를 잘못 이해했기 때문이라는 것을 알았다.. 원래도 어려웠지만 그래서 더더욱 어려웠다.... [각 룩이 최대 1개의 룩에만 공격받는 경우의 수] 라는 것은 각 룩이 공격을 받지 않을 수도 있고, 받는다면 1개의 룩에게만 공격을 받는다. 이것은 모든 각각의 룩에게 적용이 되는 룰이다. 룩을 어느 자리에 하나 놓으면 그 룩이 속한 행이나 열에는 다른 하나의 룩만 놓거나 놓지 않..

알고리즘 2022. 4. 16. 00:10