본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 11048 이동하기 출처: https://www.acmicpc.net/problem/11048 Input 3 4 1 2 3 4 0 0 0 5 9 8 7 6 Output 31 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com 각 칸에서 이동 방향은 (r+1, c), (r, c+1), (r+1, c+1)로 아래와 같습니다. 반대로 어느 지점 (i, j)에서 도달하는 방법은 아래와 같습니다. dp[i][j] = dp[i][j.. 2021. 2. 23.
[BOJ] 백준 1890 점프 출처: https://www.acmicpc.net/problem/1890 Input 4 2 3 3 1 1 2 1 3 1 2 3 1 3 1 1 0 Output 3 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com [이동 방식] - 아래쪽 혹은 오른쪽으로 이동할 수 있습니다. - 이동거리는 각 칸에 적혀있는 숫자만큼 이동해야 합니다. [구현] 이동 거리와 방향 특성을 이용. dp[i][j] = 해당 지점.. 2021. 2. 23.
[BOJ] 백준 11051 이항 계수 2 출처: https://www.acmicpc.net/problem/11051 Input 5 2 Output 10 [BOJ] 11050 이항 계수 1 문제처럼 재귀방식으로 접근하면 시간제한이 걸립니다. [BOJ] 백준 11050 이항 계수 1 출처: https://www.acmicpc.net/problem/11050 Input 5 2 Output ※ 이항 계수(binomial coefficient)는 n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수 다음과 같은 점화식이 존재.. zoosso.tistory.com 불필요하게 재귀호출되는 bino(n, k)를 DP 방식으로 처리 [Bottom-up 방식] import java.util.Scanner; public class Main{ s.. 2021. 2. 23.
[BOJ] 백준 11050 이항 계수 1 출처: https://www.acmicpc.net/problem/11050 Input 5 2 Output ※ 이항 계수(binomial coefficient)는 n개의 서로 다른 원소 중에서 r개의 원소를 순서없이 골라내는 방법의 수 다음과 같은 점화식이 존재합니다. * n == r 이거나 r == 0 이며 1을 반환한다! ▶ 재귀 방식 이용 DP 방식 풀이: [BOJ] 11051 이항 계수 2 [BOJ] 백준 11051 이항 계수 2 출처: https://www.acmicpc.net/problem/11051 Input 5 2 Output 10 [BOJ] 11050 이항 계수 1 문제처럼 재귀방식으로 접근하면 시간제한이 걸립니다. [BOJ] 백준 11050 이항 계수 1 출처: https://www.ac.. 2021. 2. 23.
[BOJ] 백준 1932 정수 삼각형 출처: https://www.acmicpc.net/problem/1932 Input 5 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 Output 30 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com ※ 아래층 이동은 현재 층에서 선택된 수에서 대각선 왼쪽 혹은 대각선 오른쪽 입니다. arr[i][j] → arr[i+1][j] or arr[i+1][j+1] [n = 1] → result = .. 2021. 2. 23.
[BOJ] 백준 2947 나무 조각 출처: https://www.acmicpc.net/problem/2947 5개 숫자를 정렬하는데 교환이 발생할 때마다 현재 배열 상태를 출력해야 한다. 버블 정렬(Bubble Sort)을 구현하는 것에서 버블 정렬(Bubble Sort) 특징 - O(N2) - 서로 인접한 두 원소를 비교하여 정렬 - 한 번의 탐색으로 가장 큰 원소가 맨 뒤에 위치하게 됩니다. (오름차순 기준) 시뮬레이션 구현 코드 (오름차순 기준) #include int swap(int* a, int* b zoosso.tistory.com 출력하는 시점을 잘 고려하면 된다. 구현 ① 5개 숫자 입력 받기 ② 위치 교환 발생 여부 처리 ③ 배열 위치 교환 swap() ④ 배열 상태 출력 #include const int SIZE = 5;.. 2021. 2. 23.
[BOJ] 백준 2583 영역 구하기 출처: https://www.acmicpc.net/problem/2583 Input 5 7 3 0 2 4 4 1 1 2 5 4 0 6 2 Output 3 1 7 13 직사각형의 정보는 아래와 같습니다. 문제에서 주어진 인덱스를 아래와 같이 해석해도 무방. 3개의 분리된 영역과 그 넓이는 아래와 같습니다. ① 모눈 종이를 순회하며 직사각형으로 안 덮여진 지점을 찾습니다. ② BFS를 통해 분리된 영역을 구분합니다. ③ 분리된 영역의 개수와 각각의 넓이를 구합니다. import java.util.ArrayList; import java.util.Collections; import java.util.LinkedList; import java.util.List; import java.util.Queue; imp.. 2021. 2. 23.
[BOJ] 백준 10819 차이를 최대로 출처: https://www.acmicpc.net/problem/10819 Input 6 20 1 15 8 4 10 Output 62 배열 A 원소 순서를 적절히 바꿔 다음 식의 최댓값을 구하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 구현 |A[0] - A[1]| + |A[1] - A[2]|의 최대값을 구하기 위해서는 A[1] 기준으로 양 옆에 최솟값 최대값을 배치하는 것입니다. 주어진 Sample을 풀이하면 다음과 같습니다. → |10 - 4| + |4 - 20| + |20 - 1| + |1 - 15| + |15 - 8| = 6 + 16 + 19 + 14 + 7 = 62 즉, 전체 수식에서 마찬가지로 가장 가운데를 기준으로 채워갑니다. ①.. 2021. 2. 23.
[BOJ] 백준 4963 섬의 개수 출처: https://www.acmicpc.net/problem/4963 Input 5 4 1 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 1 5 5 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 1 0 1 0 1 0 0 Output 1 9 ① 지도 배열을 탐색하며 땅(1) 탐색 ② BFS로 땅끼리 연결된 섬을 구분 ③ 찾은 섬의 개수 출력. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static Queue queue; static int w, h; static int[][] arr; static int[] rows, cols;.. 2021. 2. 23.
[BOJ] 백준 9663 N-Queen 출처: https://www.acmicpc.net/problem/9663 Input 8 Output 92 체스판에서 퀸(x, y)의 이동은 같은 행, 열 그리고 대각선 방향입니다. 두 좌표가 (x1,y1), (x2,y2)일 때, |x1- x2 | = | y1 - y2|이면 좌표상 대각선상에 있다고 볼 수 있습니다. ex) A=(1,1) / B=(5,5)가 존재하면, |5-1| = |5-1| 이므로 대각선상의 위치. 1행을 기준으로 퀸을 한개씩 놓아서 재귀 탐색처리. 1~N행까지 서로 공격하지 않게 퀸을 놓을 수 있는 모든 경우를 구합니다. ex) 4 x 4 크기의 체스판 만약 1행에 두번째에 퀸을 두었다면 아래의 형태가 됩니다. (특정 행에서는 여왕이 하나입니다.) 다른 풀이: [Jungol] 1889 .. 2021. 2. 23.
반응형

티스토리툴바