알고리즘 문제풀이
-
BOJ 2178 DFS? BFS? DP?알고리즘 문제풀이/Java 2020. 5. 4. 23:27
문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력..
-
BOJ 6064 나머지 정리알고리즘 문제풀이/Java 2020. 5. 1. 13:38
문제 최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 로 표현하고, 두 번째 해를 로 표현하였다. 의 다음 해를 표현한 것을 이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 예를 들어, M = 1..
-
BOJ 10971 오랜만에 풀어보는 순회 문제알고리즘 문제풀이/Java 2020. 5. 1. 01:19
문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다. 항상 순회할 수 있는 경우만 입력으로 주어진다. www.acmicpc.net 해설 내가 처음 문제를 해결하기 위한 방법은 배열을 이용하는 것이었다. 0번 배열에 번호를 저장하고, 이후 해당 번호를 인덱스로 하는 배열에 다른 번호를 저장하는 방식으로 처리하면 문제를 해결할 수 있을 것 같았다. 34번째 줄을 추가하기 전까지는 문제를 계속 틀렸는데,..
-
BOJ 2225 합분해알고리즘 문제풀이/Java 2020. 4. 18. 16:51
문제 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 예제 입력 1 복사 20 2 예제 출력 1 복사 21 해설 이 문제의 경우, 초반에 0 또한 수를 만드는 경우에 속하는 지 모르고, 삽질을 조금 했었다. 하지만 점화식으로 식을 이미 세워놨기 때문에 쉽게 문제를 찾아내 수정할 수 있었다. 먼저 이 문제의 점화식을 정리하면 다음과 같다. D[n][k] = k개의 수..
-
DP - 점화식의 중요성(BOJ 11052, 16194)알고리즘 문제풀이/Java 2020. 4. 17. 18:28
요새 다이나믹 프로그래밍(Dynamic Programming)을 공부 중인데, 한 번 새로운 깨달음을 얻을 때마다 문제가 슝슝 풀리는 게 기분이 좋다. 강의를 들으면서, 종만북에서 얻지 못할 좋은 사고의 흐름을 얻었는데, 같이 공유할까 한다(물론 종만북은 너무 어려워서 아직 제대로 보지도 못했다. 그래서 종만북에도 있을 수 있는 내용이다. 갓갓 종만북). 먼저, DP의 구조는 익히 들어서 알 것이다. 겹치는 부분 문제(Overlapping problem)와 최적 부분 구조(Optimal substructure)을 둘 다 만족해야 한다. 구조의 정의는 한글말이니 이해하겠는데, 문제에서 해당 정의를 찾아내는 게 나에겐 너무 어려웠다. 기본 개념을 문제에 적용을 못 시키고 있었달까?? 그렇게 혼자 헤매다가, ..
-
BOJ 2004, 1676 - 팩토리얼에 대한 접근알고리즘 문제풀이/Java 2020. 4. 15. 14:40
https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m(0≤m≤n≤2,000,000,000, n!=0)이 들어온다. www.acmicpc.net https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 강의에서 배운 팩토리얼 문제에 대한 접근을 정리해볼까 한다. 1676번 문제를 먼저 살펴보자. 어떤 수 N이 주어졌을 때, 이 수의 팩토리얼의 값에서 0은 몇 개 일까? (잠시 고민해보자.) 다음과 같은 방법을 생각할 수 있을 것이다. 더보기 1. 팩토리얼 값을 계산한 뒤, 0..
-
BOJ 1918 후위표기식 - 스택알고리즘 문제풀이/Java 2020. 4. 14. 21:17
문제 수식은 일반적으로 3가지 표기법으로 표현할 수 있다. 연산자가 피연산자 가운데 위치하는 중위 표기법(일반적으로 우리가 쓰는 방법이다), 연산자가 피연산자 앞에 위치하는 전위 표기법(prefix notation), 연산자가 피연산자 뒤에 위치하는 후위 표기법(postfix notation)이 그것이다. 예를 들어 중위 표기법으로 표현된 a+b는 전위 표기법으로는 +ab이고, 후위 표기법으로는 ab+가 된다. 이 문제에서 우리가 다룰 표기법은 후위 표기법이다. 후위 표기법은 위에서 말한 법과 같이 연산자가 피연산자 뒤에 위치하는 방법이다. 이 방법의 장점은 다음과 같다. 우리가 흔히 쓰는 중위 표기식 같은 경우에는 덧셈과 곱셈의 우선순위에 차이가 있어 왼쪽부터 차례로 계산할 수 없지만 후위 표기식을 사..
-
BOJ 17299 오등큰수 풀이를 통한 자료구조에 담을 정보에 대한 회고알고리즘 문제풀이/Java 2020. 4. 14. 00:14
문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) < F(A7=1) 이기 때문에, NGF(3) = 1..