분류 전체보기
-
1744 수 묶기백준/그리디 알고리즘 2024. 7. 22. 21:50
입력값에서 음수랑, 양수를 따로 받는다. 예를 들어 -10 -5 -1 0 1 2 3 4 5 이런식으로 입력값이 있을 때1) 양수는 양수 리스트에 담고, 내림차순 정렬-> 5 4 3 2 1 2) 음수와 0은 음수리스트에 담고, 오름차순 정렬-10 -5 -1 0 그런 다음에 맨 처음에 있는 값부터 다음수와 묶으면 된다. 즉 양수의 경우 -> 5 4 3 2 15*4 + 3*2 + 1 = 20 + 6 + 1 = 27 이 최대의 값이 되고, 음수의 경우-10 -5 -1 0(-10) * (-5) + (-1)*0 = 50 + 0 = 50 이 최대의 값이 된다. 0을 음수 리스트에 넣은 이유는,음수가 홀수개 있을 경우 나머지 1개는 수를 묶을 수 없어서음수 그대로 남게 되는데, 0을 곱해서 0으로 만들면 음수를 ..
-
10974 모든 순열백준/백트래킹 2024. 7. 13. 12:35
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int number[]; static boolean visit[]; static int result[]; static int N; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer ..
-
1788 피보나치 수의 확장백준/DP 다이나믹 프로그래밍 2024. 7. 9. 22:50
양수, 음수를 나누어서 풀었는데, 일단 f(0) = 0f(1) = 1 1) n : 양수f(n) = f(n-1) + f(n-2) 이므로, f(2) = f(1) + f(0) f(3) = f(2) + f(1) f(4) = f(3) + f(2) 여기에서, dp[i] = dp[i-1] + dp[i-2] 임을 알 수 있다. 2) n : 음수 f(n-2) = f(n) - f(n-1) 이므로f(-1) = f(1) - f(0)f(-2) = f(0) - f(-1)f(-3) = f(-1) - f(-2) 이 경우, 절댓값으로 숫자 따지면,dp[i] = dp[i-2] - dp[i-1] 이 된다. 그래서 양수의 경우는 dp_plus 배열로, 음수의 경우는 dp_minus 배열로 따로 만들었고,음수의 경우에는 -1 일 경우,..
-
1781 컵라면백준/그리디 알고리즘 2024. 7. 5. 10:50
일단,먼저 다음과 같이 생각해보았다 (시간초과 남) 일단, 입력값을 컵라면 수 내림차순으로 정렬하는 것이다. 예제의 경우 71 61 73 23 12 42 56 1 1 71 62 52 43 26 13 1 => 그리고 visit 배열을 만들어서1) 만약에 그 시간에 방문한 적이 없다면, 방문표시하고2) 혹시나 방문한 적이 있다면 그보다 작은 시간에 방문한 적 없다면 방문표시하는 것이다. 예를 들어서 [1]1 7 에서 기한은 1이므로visit[1] = true 이다.그리고 count = 7이 된다. (컵라면 수 ) [2]그 다음 컵라면 수가 많은 1 6은 기한이 1이다.하지만 이미 visit[1] = true 이므로그냥 넘어간다. [3] 그 다음은 2 5 인데visit[2] = false 이므로visit[..
-
15685 드래곤 커브백준/구현 2024. 6. 28. 14:52
첫번째 예제를 가지고 설명을 해본다.33 3 0 14 2 1 34 2 2 1 여기서 두번째 예제 4 2 1 3 를 설명해보면,4가 세로 방향이고, 2가 가로 방향이라고 했으므로(2,4) 인 상황을 생각해보겠다. 일단 방향은 아래와 같다. 0 : 오른쪽 →1 : 위 ↑2 : 왼쪽 ←3 : 아래 ↓ 1. 차수 0 그러면 차수가 0일 때의 상황은 아래와 같다. (2,4)에서 위쪽으로 올라간다. 2. 차수 1 끝 점인 (1,4) 을 기준으로 시계방향으로 90도 회전하면 왼쪽 방향이 된다.즉 (1,4)에서 (1,3)으로 이동3. 차수 2 위의 도형을 끝점 기준으로 시계방향으로 회전시, 아래와 같다. 4. 차수 3 마지막으로 아래와 같이 완성된다. 그러면 위의 그림에서 규칙성을 찾을 수 있다. ..
-
1915 가장 큰 정사각형백준/DP 다이나믹 프로그래밍 2024. 6. 26. 17:48
입력값을 input 배열에 넣고,만약 i,j 위치 값이 1일 경우 (아래 그림에서 input[i][j] = 1)dp[i][j] => dp[i-1][j-1], dp[i-1][j-1], dp[i][j-1] 중 최소값 + 1하면 된다. dp[1][1] = input[0][1], input[0][0], input[1][0] 중 최소값 + 1 하면 되는데,=> input[0][1] = 1, input[0][0] = 0, input[1][0] = 0 이므로이 중 최소값은 0 이고dp[1][1] = 0 + 1 = 1 이 된다. 그래서 dp배열을 완성하면 아래와 같다. 0100011111200010 규칙 1dp를 만들 때, 첫 행, 첫 열은input행렬의 첫 행, 첫 열 값을 그대로 입력하면 된다. 규칙 2 ..
-
15684 사다리 조작백준/백트래킹 2024. 6. 26. 15:19
사다리 표시할 때,만약 1번 세로선 -> 2번 세로선사이에 가로선이 있다면 배열에 map[1][2] = 1 표시를 해준다. 그래서 만약 1번 세로선에서 사다리를 타고 내려오면, 오른쪽 (2번 세로선)으로 이동하면 되고, 2번 세로선에서 사다리를 타고 내려오면,왼쪽(1번 세로선)으로 이동하면 된다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int value; static int H; static int N; static int map[][]; public static v..
-
11404 플로이드백준/플로이드 워셜 2024. 6. 25. 14:49
1. 플로이드 워셜 알고리즘에 대해 설명하자면,모든 정점에서 모든 정점으로의 최단경로를 구하고 싶을 때 사용한다.=> 거쳐가는 정점 기준으로 알고리즘 수행=> 음수 순환 사이클이 없는 그래프에서 수행 2. 다익스트라 알고리즘은, 하나의 정점에서 출발하여 다른 모든 정점으로의 최단경로 구함. 그러면 플로이드 워셜 알고리즘에 대해 알아보자. 1. 첫번째 맨 처음에 직행으로 갈 수 있는 경로를 구하면, 아래 표와 같다.갈 수 있는 경로가 없다면, 무한(큰 값)으로 둔다. 1->1, 2->2, 3->3 즉 본인에서 본인으로 가는 경로는 0으로 한다. 1231011210435무한0 2. 두번째 - 정점 1을 경유하여,위에서 플로이드 워셜 알고리즘은 거쳐가는 정점 기준으로 수행한다고 했다. 정점..