Algorithm9 [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 2 다음
