Algorithm/Baekjoon7 [JAVA] BOJ21922 학부 연구생 민상 알고리즘 분류 구현 그래프 이론 그래프 탐색 시뮬레이션 문제 풀이 방법 물건이 있을 때, 나아가야되는 방향이 바뀌는데 경우를 나누어서 에어컨 바람이 갈 수 있는 곳을 찾았습니다. 이 때, 한 번 갔던 곳이라고 해서 2차원 배열을 사용해서 방문 처리를 하면, 다시 못 가는 경우가 발생하게 됩니다. 에어컨 바람은 교차해서 갈 수 있으므로 한 번 갔다고 해서 다시 못가게 된다면, 오답입니다. 따라서 2차원 배열이 아닌, 3차원 배열을 사용했습니다. Wind클래스는 에어컨에서 나오는 바람에 대한 정보로, 현재 행, 열 번호와 나아가는 방향의 정보를 담아줬습니다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.. 2024. 2. 8. [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] BOJ1753 최단경로 알고리즘 분류 그래프 이론 데이크스트라 최단 경로 문제 풀이 방법 Node 클래스를 만든 후, 다익스트라 알고리즘을 사용했다. 우선순위 큐에 (끝 점, 가중치)의 값을 가진 노드를 추가하며, 최단 경로로 갔을 때의 값을 배열 d에 저장했다. 코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.PriorityQueue; import java.util.StringTokenizer; /* 최단경로 */ public class BOJ1753 { static class Node implements Comparable { .. 2023. 12. 18. [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. 이전 1 2 다음
