본문 바로가기
반응형

전체 글1311

[BOJ] 백준 11559 Puyo Puyo 출처: https://www.acmicpc.net/problem/11559 Input ...... ...... ...... ...... ...... ...... ...... ...... .Y.... .YG... RRYG.. RRYGG. Output 3 ① DFS 탐색을 통해 터질 수 있는 그룹을 찾아 폭파시킵니다. map[][]에서 각 지점별로 DFS 처리해야 합니다. ex) 아래는 총 2 그룹에서 터지지만 연쇄 횟수는 1번으로 측정됩니다. ..G.BB ..B.BB RRRRGG GGRRRR ② 폭파로 비워져 버린 공간을 채워야 합니다. 한 개의 열을 기준으로 처리. ③ 터지는 뿌요가 없어질 때까지 ①, ② 과정 반복. #include #include #include #include #include usi.. 2021. 2. 28.
[BOJ] 백준 5532 방학 숙제 출처: https://www.acmicpc.net/problem/5532 Input 20 25 30 6 8 Output 15 총 20일 중 국어숙제는 5일에 걸쳐서 완료할 수 있으며 수학숙제는 4일에 거쳐서 완료할 수 있으므로 모든 숙제를 완료하는데 걸린 기간은 5일입니다. ▶ 20 - 5 = 15 ① 국어와 수학 숙제를 모두 완료하는 기간 중 최대값을 구합니다. ② 방학기간 - 숙제 완료 기간을 통해 놀 수 있는 기간을 구합니다. #include using namespace std; int maxOfValue(int x, int y){ if(x > y) return x; else return y; } int findElapsedTime(int totalPage, int perPage){ int elap.. 2021. 2. 28.
[BOJ] 백준 2979 트럭 주차 출처: https://www.acmicpc.net/problem/2979 Input 5 3 1 1 6 3 5 2 8 Output 33 truckCnt[101];에 분 단위로 주차된 트럭의 개수를 구한 후, 주차된 개수에 맞게 요금을 측정합니다. #include using namespace std; int truckCnt[101]; int main() { int A, B, C; cin >> A >> B >> C; for (int i = 0; i > s >> e; // 각 시간대별 주차한 트럭 개수 for (int j = s; j < e; j++) { truckCnt[j]++; } } int result = 0; for (int i = 1; i 2021. 2. 28.
[BOJ] 백준 1018 체스판 다시 칠하기 출처: https://www.acmicpc.net/problem/1018 Input 10 13 BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB BBBBBBBBWBWBW BBBBBBBBBWBWB WWWWWWWWWWBWB WWWWWWWWWWBWB Output 12 ① N * M 크기의 board를 8 × 8로 잘나 낼 수 있는 모든 경우의 수 구하기 ex) 9 × 9 크기에서는 4가지 경우가 존재 ② 8 × 8크기로 잘나낸 board에서 색을 바꾸어야할사각형의 개수를 합니다. - 흰색 / 검은색으로 시작하는 경우 중 색이 바뀌는 개수가 더 작은 것을 구합니다. ③ 전체 Case 중 ②에서 구한 값 중 최소값.. 2021. 2. 28.
[BOJ] 백준 1915 가장 큰 정사각형 출처: https://www.acmicpc.net/problem/1915 Input 4 4 0100 0111 1110 0010 Output 4 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com ▶ DP[i][j] = (i,j)를 우측 끝으로 하는 정사각형의 최대 크기의 제곱근 DP[i][j]는 map[i][j] = 1인 지점에서 점화식 DP[i][j] = min(DP[i-1][j], DP[i][j-1.. 2021. 2. 28.
[BOJ] 백준 1793 타일링 출처: https://www.acmicpc.net/problem/1793 Input 2 8 12 100 200 Output 3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251 2 * N 직사각형이 주어질 때, 2×1과 2×2 타일로 채우는 방법의 수 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 z.. 2021. 2. 28.
[BOJ] 백준 2110 공유기 설치 출처: https://www.acmicpc.net/problem/2110 Approach [탐색] Parametric Search [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다. Binary Search (이분 탐색) Binary Search (이분 탐.. zoosso.tistory.com Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택.. 2021. 2. 28.
연속된 부분 합(연속합) - 2 (Prefix Sum) ※ 구간합을 구하는 효율적인 방법 연속된 부분 합(연속합) - 1 (완전 탐색) 연속된 부분 합(연속합) - 2 (Prefix Sum) 연속된 부분 합(연속합) - 3 (DP) [구간합] Sum of sub-matrix (2D Array) Prefix Sum : psum[i] = 첫번째 원소부터 i 번째 원소까지의 구간 합 A[i] = psum[i] - psum[i-1] ex) A[3] = -4 = psum[3] - psum[2] = -3 - 1 = -4 psum[]을 이용한 특정 구간 합 ▶ 구간 [8, 9] 합 = psum[9] - psum[7] = 19 - (-2) = 21 = A[8] + A[9] = 13 + 8 ↔ psum[9] - psum[7] = (1~9까지의 합) - (1~7 까지의 합) .. 2021. 2. 28.
연속된 부분 합(연속합) - 3 (DP) ※ 구간합을 구하는 효율적인 방법 연속된 부분 합(연속합) - 1 (완전 탐색) 연속된 부분 합(연속합) - 2 (Prefix Sum) 연속된 부분 합(연속합) - 3 (DP) [구간합] Sum of sub-matrix (2D Array) DP ① D[i] = 인덱스 i를 오른쪽 끝으로 갖는 연속 구간의 최대값 ② D[i - 1] > 0인 경우는 활용하지만 D[i-1] ≤ 0 이라면 이용하지 않습니다. partialSum = Math.max(partialSum, 0) + A[i]; answer = Math.max(answer, partialSum); 즉, 배열을 순회하며 부분합이 0보다 작으면 이전의 부분 배열의 합은 무시하고 다시 순회한다고 보면됩니다. (※ patialSum = D[i] / answe.. 2021. 2. 28.
[SWEA] 3819 최대 부분 배열 출처: [SWEA] SW 문제해결 심화 - Ad Hoc Algorithms Input 2 1 3 5 1 3 -5 3 6 Output #1 3 #2 9 연속되는 부분 배열의 최대합을 구하는 문제 import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = Integer.parseInt(sc.next()); for(int tc=1; tc 2021. 2. 28.
반응형

티스토리툴바