프로그래밍 diary

격자, 좌표, 경로 탐색 문제 -> BFS(너비우선탐색), DFS(깊이우선검색) 사용 2178번 - 미로 탐색 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 최근 최단거리 문제를 풀 때, 역추적 방법을 사용하여 문제를 해결했던 적이 있어 역추적 방법으로 문제 접근을 했습니다. 하지만 생각해 보니 역추적으로 풀었던 문제는 오른쪽 방향을 우선순위로 이동한다는 조건이 있었습니다. 2178번 문제는 방향 우선순위 없이 칸의 숫자가 1인 칸은 모두 이동이 가능한 문제이기 때문에 역추..

1644번 - 소수의 연속합 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 먼저 N을 입력받는다. 1부터 입력받은 N까지의 범위에서 소수를 찾아 primeArr에 추가한다. 이 문제는 소수의 합으로 N을 구하는 경우의 수 이기도 하지만, 연속된 소수의 합으로 이뤄져야 한다. 어떤 방법을 사용해야 할지 잘 생각이 나지 않아 구글링을 해봤다. 이 과정에서 '슬라이딩 윈도우 알고리즘'을 알게 되었고, 해당 글을 참고해서 문제를 풀었다. 연속된 소수의 합을 위해 누적된 값이 N이 넘지 않는다면 다음 인덱스의 요소를 더하고 단약 누적된 값이 N보다 크거나 같으면 시작하는..

1456번 - 거의 소수 https://www.acmicpc.net/problem/1456 1456번: 거의 소수 어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다. www.acmicpc.net 먼저 정해진 범위 내에서 소수만 저장된 List를 구한다. public static void makePrimeArr(long end) { // 소수로만 이루어진 List 생성 arr = new long[(int) (end + 1)]; for (int i = 2; i B) break; list.add((long) Math.pow(prime.get(i), j)); } } //A의 범위도..

이 글에서는 백준에 있는 소수 문제들을 풀면서 배웠던 부분을 정리하려고 한다. 소수 문제는 '에라토스테네스의 체'라는 개념만 확실히 알고 있어도 반 이상은 먹고 들어간다고 생각한다. 소수? 모두가 알고 있듯이 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수이다. 이런 소수를 찾는데 유명한 방법은 에라토스테네스의 체이다. 에라토스테네스를 자바로 구현한 코드이다. i = 2 ~ 100 i는 2부터 시작해서 2를 제외한 2의 배수 자리에 모두 0을 대입하여 소수가 아님을 확인한다. i가 3이 되면 앞의 방식과 동일하게 3을 제외한 3의 배수 자리에 모두 0을 대입한다. 이 과정을 거치고 나서 arr배열의 0이 아닌 수만 출력하면 소수만 출력된다. public class Main { static in..

9251번 - LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 알고리즘 수업 시간에 다뤄봤던 문제라서 문제 풀이는 쉽게 할 수 있었다. 다만 코드를 작성할 때 좀 둘러둘러 작성한 느낌이 들었다. 코드를 완성했을 때는 생각보다 더더 코드가 간결하게 나와서 놀랬다. A C A Y K P C 0 1 1 1 1 1 A 1 1 2 2 2 2 P 1 1 2 2 2 3 C 1 2 2 2 2 3 ..

2293번 - 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net Ex) n = 3, k = 10 arr 배열 i 1 2 3 arr[i] 1 2 5 dp 배열 (dp[0] = 1, j) 1. 초기상태 1 2 3 4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0 0 2. i = 1일 때 1 2 3 4 5 6 7 8 9 10 1 1 1 1 1 1 1 1 1 1 arr[1] = 1이므로 index 1~10까지는 1로 만들 수 있는 숫자에..

11048번 - 이동하기 https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제를 이해하고 가장 먼저 떠오른 방법은 역추적이다. 알고리즘 학부 수업시간에서 최단경로 문제를 풀 때 역추적으로 해결한 기억이 있어 추적의 시작점을 dp [N][M]으로 설정하였다. 실행 결과는 동일하지만 제출하니 틀렸다고 한다.... 역추적으로 문제 풀이를 시작한 만큼 해결하고 싶었는데 얼떨결에 dp [1][1]부터 시작한 추적도 답과 동일한 결과가 나왔..

11660번 - 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 접근은 쉽다. 값을 입력 받아 배열에 저장하고 시작점부터 끝점까지의 누적 합을 구하면 된다. 시간초과될 것을 알면서도 일단은 이중 for문을 사용하여 코드를 작성하고 제출해봤다. 좌표값을 입력 받을 때 사용하는 이중 for문은 필요한 과정이라고 생각을 했고, 누적 합을 구하는 과정에서 사용되는 이중 for문을 없애..

11057번 - 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 점화식: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 마지막 자리수의 값을 기준으로 문제를 풀었다. 3자리 숫자의 경우 003, 013, 113, 023, 123, 223, 033, 133, 233, 333 이렇게 총 10가지의 오르막 수로 구성된다. 바로 위의 풀이에서 볼 수 있듯이 마지막 수를 제외한 나머지..

12865번 - 평범한 배낭 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 1 2 3 4 5 6 7 1 0 0 0 0 0 13 13 2 0 0 0 8 8 13 13 3 0 0 6 8 8 13 14 4 0 0 6 8 12 13 14 -> dp[N][K] dp[2][6]은 dp[1][6]와 dp[1][2] + 8을 비교하여 더 큰 값을 가져온 것이다. 여기서 2라는 인덱스 값..