Algorithm6 [JAVA] BOJ1089 스타트링크 타워 알고리즘 분류 수학 구현 확률론 문제 풀이 방법 nums 배열에서 구역을 알면 어떤 수인지 알 수 있습니다. nums[행][0] ~ nums[행][2] 일 때는 1 nums[행][4] ~ nums[행][6] 일 때는 2 nums[행][8] ~ nums[행][10] 일 때는 3 ... nums[행][32] ~ nums[행][34] 일 때는 9 ArrayList 배열은 각 idx번째에서 어떤 정수를 가질 수 있는지 저장합니다. e.g) list[0]: 0번째 위치에서 가질 수 있는 숫자들 (조건을 판단해서 가능한 것들을 ArrayList구조로 저장함) map과 nums를 비교하면서 현재 map의 범위에서 가능한 경우를 list에 저장합니다. checkNums 함수에서 구현하였습니다. 각 자릿수에서 가능한 정.. 2024. 2. 1. [JAVA] BOJ2293 동전 1 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 방법 동전들의 가치를 저장하는 num 배열을 입력받습니다. dp[i][j] 배열은 인덱스 i번째 동전까지 사용했을 때, 가치 j를 만들 수 있는 경우의 수라고 정의했습니다. 동전들을 num 배열에 저정합니다. 첫 번째 동전만 사용할 경우, j(가치) % num[i] == 0일 때, 해당 동전으로 가치를 만들 수 있는 것이므로 arr[i][j]의 값을 1로 만들어주었습니다. e.g. 가치가 14이고, 첫 번째 동전이 7일 경우 dp[0][7]과 dp[i][14]의 값만 1이고, 나머지 값은 0의 값을 가짐 동전을 두 개 이상 사용하는 경우는 dp배열은 다음과 같습니다. dp[i][j] = dp[i - 1][j] + dp[i][j - arr[i]] 이 때, j -.. 2024. 1. 15. [JAVA] BOJ11049 행렬 곱셈 순서 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 방법 점화식의 특성에 따라, N이 주어졌을 때, N-1개 까지의 개수는 구할 수 있다고 가정 D[i][j]: i부터 j까지 행렬의 연산 횟수 D[1][N] = D[1][j] + D[j + 1][N] + a, a = (j번째 행렬의 행의 개수) * (j + 1번째 행렬의 행의 개수) * (j + 1번째 행렬의 열의 개수) 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class BOJ11049 { /* 행렬 곱셈 순서 */ static class Matrix { int r.. 2023. 12. 14. [JAVA] BOJ1915 가장 큰 정사각형 알고리즘 분류 다이나믹 프로그래밍 문제 풀이 방법 주어진 배열을 arr라고 한다. arr[i][j] 원소를 끝 점으로 지정했을 때, 만들 수 있는 정사각형의 최대 길이를 DP[i][j]의 값으로 한다. arr[i][j] == 0 일 때는 정사각형을 만들 수 없으므로, DP[i][j]의 값은 무조건 0이 된다. 점화식 arr[i][j] == 0, DP[i][j] = 0 arr[i][j] == 1, DP[i][j] = Math.min(DP[i - 1][j - 1], Math.min(DP[i][j - 1], DP[i - 1][j])) 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenize.. 2023. 12. 13. [JAVA] BOJ15685 드래곤 커브 알고리즘 분류 구현 시뮬레이션 문제 풀이 방법 정말 문제에서 주어진 조건 순서대로 프로그래밍을 했다. 세대에 따른 드래곤 커브를 만들기 위해서는 이전의 드래곤 커브를 구성하는 점들을 ArrayList에 저장한 후, 기준 점을 중심으로 시계방향으로 회전한 점의 좌표를 다시 ArrayList에 저장하는 방법으로 구현을 했다. 기준 점이 있을 때 시계방향으로 회전한 점의 좌표를 구하는 것은 법선벡터를 이용했다. (a, b)인 벡터가 있을 때, 이 벡터를 90도 회전했을 한 벡터: (-b, a) 두 점의 차이를 계산하여 벡터를 구한 뒤, 기준점에 대해 시계방향으로 90도 회전 한 점의 좌표를 계산했다. 기준점에 대해 시계방향으로 90도 회전한 점들을 ArrayList에 담을 때는 주의해야될 점이 있다. 현재 드.. 2023. 12. 13. [JAVA] BOJ20057 마법사 상어와 토네이도 알고리즘 분류 구현 시뮬레이션 문제 풀이 방법 우선 토네이도가 이동하는 경로를 while문을 통해 작성한다. 토네이도가 왼쪽으로 이동할 때를 기준으로 해서 모래가 확산될 수 있는 방향 벡터(scatterR, scatterC)를 정의한다. 그리고 토네이도가 회전할 때마다 토네이도의 방향벡터의 변화를 확인하면서 모래가 확산될 수 있는 방향벡터도 같이 계산해준다. 이번에도 벡터를 활용해서 문제풀이를 하였다. 설명이 부족할 수도 있지만, 내가 문제풀이를 할 때 생각했던 것들을 정리해보았다. (왜 이런지 이상하거나, 모르겠으면 질문 고고) 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokeniz.. 2023. 12. 13. 이전 1 다음
