분류 전체보기
-
15724 주지수백준/누적 합 2022. 5. 28. 14:17
1. 풀이 누적 합을 이용한다. 예제를 가지고 설명하겠다. 4 4 9 14 29 7 1 31 6 13 21 26 40 16 8 38 11 23 3 1 1 3 2 1 1 1 4 1 1 4 4 1) sum 배열 sum[i][j] = sum[i][j-1] + (i,j) 위치에 살고 있는 사람 수 로 채운다. 즉, 9 23(9+14) 52(23+29) 59(52+7) 1 32(1+31) 38(32+6) 51(38+13) 이런 식으로 채운다. sum 배열의 (1,1) 위치 값은 9 이다. 즉 sum[1][1] = 9 2) dp 배열 dp[i][j] = (1,1) 부터 (i,j) 까지의 인구수 합 => dp[i][j] = dp[i-1][j] + sum[i][j] 즉, 3) 결과 출력 주어진 직사각형 범위의 (x1,..
-
10164 격자상의 경로백준/DP 다이나믹 프로그래밍 2022. 5. 22. 20:15
1. 풀이 문제에 주어진 예시를 가지고 설명하겠다. 3 5 8 이러한 값이 주어졌기 때문에 격자는 이와 같다. map[i][j] 배열에 위와 같이 입력한다. dp[i][j] 배열은 처음 위치(0,0) 에서 ((i,j) 위치까지 이동하는 서로 다른 경로의 수를 입력할 것이다. 그러면 8의 위치를 변수 a,b 에 저장한다. 즉, 8의 위치는 (1,2) 이다. a = 1, b = 2 1) dp[0][1] ~ dp[0][b] = 1 => dp[0][1] = 1 인건, (0,0) 에서 출발해서 (0,1) 까지 이동가능한 방법은 오른쪽으로 이동하는 경우 1가지 있다. => dp[0][2] = 1 인건, (0,0) 에서 출발해서 (0,2) 까지 이동가능한 방법이 오른쪽으로 이동하는 경우 1가지 있기 때문이다. dp[..
-
11060 점프 점프백준/DP 다이나믹 프로그래밍 2022. 5. 22. 15:17
1. 풀이 문제에서 주어진 예시를 가지고 설명하겠다. 10 1 2 0 1 3 2 1 5 4 2 input 배열에 입력값을 입력한다. 1 2 0 1 3 2 1 5 4 2 => input 배열에 입력 dp[i] 배열값은 첫번째 위치에서 i 번째까지 점프한 횟수이다. 1) i = 0 dp[0] = 0 첫번째 칸은 시작 칸으로 이동이 없으므로 0으로 초기화된다. input[0] = 1 이므로, 오른쪽으로 한 칸 점프 가능하다. => i = 1 위치까지 점프 2) i = 1 dp[0] 에서 점프가 1번 더해졌으므로 dp[1] = dp[0] + 1 =1 input[1] = 2이므로, 오른쪽으로 한 칸, 두 칸까지 이동 가능하다. => i = 2, 3까지 이동 3) i = 2 dp[2] = dp[1] + 1 = 2 ..
-
11048 이동하기백준/DP 다이나믹 프로그래밍 2022. 5. 17. 22:55
1. 풀이 문제 예시 1로 설명하겠다. 3 4 1 2 3 4 0 0 0 5 9 8 7 6 map 배열에 각 위치의 사탕 개수를 입력한다. 즉, 1 2 3 4 0 0 0 5 9 8 7 6 이 값들을 map 배열에 입력한다. 문제에서 한 점은 1) 오른쪽, 2) 아래쪽, 3) 오른쪽 아래로 이동 가능하다고 했다. 즉, (1,1) 위치에서 이동 가능한 곳은 아래 그림과 같다. 그렇기 때문에 위치(2,2)에 있는 준규가 가질 수 있는 사탕 개수의 최댓값은 (2,2) 위치의 사탕 개수 + (1,1), (1,2), (2,1) 위치 사탕 개수 중 제일 큰 값이다. 자세히 설명하자면, (1,1) 에서 오른쪽, 아래쪽, 오른쪽 아래 방향으로 이동 가능하다. 그런데 이것은 출발지 -> 도착지 방향이다. 그렇다면 도착지에서..
-
2461 대표 선수백준/두 포인터 2022. 5. 15. 22:37
1. 풀이 1) 능력치 기준 오름차순 정렬 예제를 가지고 설명하겠다. 3 4 12 16 67 43 7 17 68 48 14 15 77 54 각 줄은 각 반 학생들의 능력치를 표시한다. 12 16 67 43 => 1반 학생 7 17 68 48 => 2반 학생 14 15 77 54 => 3반 학생 이 모든 능력치를 input 리스트에 Student 객체를 이용해서 넣을 것이다. Student 클래스에는 '반' 을 의미하는 group 변수, '능력치'를 의미하는 ability 변수가 있다. 12 16 67 43 는 1반 학생들의 능력치이기 때문에 Student 객체로 넣을 때 (1,12) (1,16) (1,67) (1,43) 이런식으로 넣어주면 된다. 그런 다음 input 리스트를 능력치 기준으로 오름차순 정..
-
20165 인내의 도미노 장인 호석백준/시뮬레이션 2022. 5. 14. 15:09
1. 풀이 이 문제에서 핵심이라고 생각한 부분을 설명하겠다. 문제에서 주어진 예제로 풀이한다. 1) map 배열 일단 게임판의 상태, 즉 각 격자에 놓인 도미노의 길이는 map[][] 배열에 표시한다. 그런데 크기를 [N+1][M+1] 로 했다. 문제에서 1행 1열부터 도미노가 세워진다고 해서 입력값이 map[1][1] 부터 map[N][M] 까지 채워지도록 했다. 1 1 1 1 1 1 2 2 1 1 3 1 2 2 2 1 3 2 1 1 1 3 3 1 1 2) result 배열 도미노가 넘어졌는지(F), 넘어지지 않았는지(S) result[][] 배열에 표시했다. 초기에는 도미노가 모두 서있으므로 result[][] 배열의 모든 값이 S 이다. 이 배열 크기 역시 result[N+1][M+1] 이다. 3)..
-
2346 풍선 터뜨리기백준/덱 2022. 5. 12. 19:41
1. 풀이 덱을 이용해서 풀었다. 예제를 가지고 풀이해 보겠다. 5 3 2 1 -3 -1 1. 입력값 받기 코드에서 클래스 Balloon 을 만든다. 변수 number, value 를 갖는다. number : 풍선 번호, value : 풍선 안 종이에 적혀있는 값 위의 예제에서 number => 1 2 3 4 5 value => 3 2 1 -3 -1 일단 입력값을 Balloon 객체에 맞게 만든 뒤 덱 (input) 에 넣는다. 즉, (numver, value) 형태이므로, (1,3) (2,2) (3,1) (4,-3) (5,-1) 이 들어감. 2. while 문 예시로 설명하면, 1) 현재 덱의 상태는 (1,3) (2,2) (3,1) (4,-3) (5,-1) 이다. (1,3) 이 덱의 앞쪽, (5,-1)..
-
11437 LCA백준/트리 2022. 5. 8. 22:38
1. 풀이 다른 사람 블로그를 참고했다. 일단 그림으로 설명하겠다. 문제 예제에 6번 노드와 11번 노드의 부모를 찾으라고 되어있다. 이때, 6번 노드와 11번 노드의 level 이 다르다. 트리에서 level 이란, 루트 노드로부터 깊이를 의미하는데, 루트 노드의 level = 1이다. 이때 level 이 더 큰 11번 노드와 관련해서 변화를 준다. => 11번 노드의 부모 노드를 타고 이동하면서 노드 6과 level 이 같아지는 노드 번호를 찾는다. 5번 노드와 6번 노드의 level 이 같다. 이때부터는 5번, 6번 노드의 각 부모 노드를 타고 올라가면서 그 값이 같아지는 경우를 찾으면 된다. 5번 노드의 부모 노드와, 6번 노드의 부모 노드가 2로 같다. 정답은 2가 된다. 위에서는 쉽게 풀렸지만..