DJ's Blog

https://www.acmicpc.net/problem/12886 12886번: 돌 그룹 오늘 강호는 돌을 이용해 재미있는 게임을 하려고 한다. 먼저, 돌은 세 개의 그룹으로 나누어져 있으며 각각의 그룹에는 돌이 A, B, C개가 있다. 강호는 모든 그룹에 있는 돌의 개수를 같게 만들려 www.acmicpc.net 이 글을 쓰는 이유는, 문제를 복습하면서 다시 푸는데 바로 생각해내지 못한 부분이 있어서(부끄럽지만) 그 부분을 기록해서 잊어버리지 않고 다음에는 비슷한 문제를 만났을 때 바로 풀기 위해서이다. 돌 그룹 문제는 세 그룹의 돌을 동일한 수로 나누는 문제인데, 세 그룹의 돌의 전체 개수가 정해져 있다는 점을 이용해야 메모리와 시간을 아낄 수 있는 문제이다. 무조건 문제를 풀기 시작하는게 아니라 ..

알고리즘 2022. 11. 21. 00:28

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/1947 1947번: 선물 전달 경우의 수를 1,000,000,000으로 나눈 나머지를 첫째 줄에 출력한다. www.acmicpc.net 위 문제는 백준 1413번 박스 안의 열쇠와 매우 유사한 문제인것 같아 오랜만에 글 올려본다. https://djjblog.tistory.com/26 ( ↑ 백준 1413번 박스 안의 열쇠) 선물을 돌리는데 자신의 것은 받을 수 없다면 결국은 사이클이 있어야 한다는 점. 그 점을 이용해서 다이나믹 프로그래밍 알고리즘으로 푸는 문제이다. n (사람의 수)이 1인 경우는 내가 내자신의 선물을 받는 경우밖에 없으므로 0이 된다. n 이 2 인 경우에는 상대방의 선물을 받는 경우밖에 없으므로 경우의 수는 1이 된다. ..

알고리즘 2022. 8. 15. 16:03

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net DP를 이용해서 푸는 문제이다. 풀면서 한번 틀리고, 찾았던 반례에 대해서 적어보려고 한다. 배열 d는 인덱스값을 무게로 하고, 그 무게에서 가질 수 있는 최대값을 최대 가치 값(원하는 답)으로 둔 변수이다. 최대로 가질 수 있는 무게(K)가 7이라고 해보자. 무게(W)가 4이고 가치(V)가 8이라고 하면, d[4]에서 가질수 있는..

알고리즘 2022. 5. 5. 17:55

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

https://www.acmicpc.net/problem/1557 1557번: 제곱 ㄴㄴ 어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K www.acmicpc.net 이전 백준 문제는 화면을 캡쳐하고 몇번째 줄은 어떤 의미인지 설명했는데, 이 문제는 다시 풀 때 캡쳐해서 줄별로 설명하지 않고 의식의 흐름대로 주석으로 정리하면서 풀어보았다. import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { ..

알고리즘 2022. 4. 14. 14:14