본문 바로가기
반응형

전체 글1308

동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문이다. 동적 계획법과 분할 정복의 차이가 발생하는 부분은 문제를 나누는 방식이다. 동적 계획법(DP)은 다른 알고리즘과 함께 이용해서 문제를 풀어야 하는 경우가 있다. 특정 Case를 여러번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용하여 속도를 높이다. 그러기 위해 각 문제의 답을 메모리에 저장해 둘 필요가 있다. → DP[ ][ ] ▶ 연속된 부분 합(연속합) - 1 (완전 탐색) ▶ 연속된 부분 합(연속합) - 2 (Prefix Sum) ▶ 연속된 부분 합(연속합.. 2021. 5. 22.
[SWEA] 9236 곰돌이 출처: SWEA Approach ① Input Data를 입력 받아 base[][]에 저장한다. 벌(bee)과 곰돌이(bear) 이동을 확인하기 위해 BFS를 여러번 해야 하는데 이를 위해 base[][]를 원본으로 활용 - 곰돌이 위치(M), 집 위치(D), 벌의 초기 위치(H)를 표시한다. ② 벌들을 확산시킨다. 확산되는 원리는 BFS 방식을 이용한다. ▶ BFS (Breadth-First Search, 너비 우선 탐색) BFS (Breadth-First Search, 너비 우선 탐색) BFS 그래프 전체를 탐색하되, 인접한 노드들을 차례대로 방문합니다. Queue 이용 * DFS로 풀리는 문제는 일반적으로 BFS로도 풀 수 있습니다. Process ※ 깊이 우선 탐색과는 달리 너비 우선 탐색에서 z.. 2021. 5. 22.
[SWEA] 4747 사막에서 만난 지니 출처: SWEA Approach 문제를 맞추려면 조건 中에서 3 ≤ N ≤ 2000 와 1 ≤ V ≤ 10000 조건을 만족해야 한다. 개수 상관없이 3명의 아이들에게 동일한 값어치를 분배할 때, 각자 받은 물건의 값어치는 배낭에 있었던 물건들의 {총 값어치 ÷ 3} 이다. ex) {1, 2, 3, 4, 5} → 1 + 2 + 3 + 4 + 5 → 15 ÷ 3 = 5 (=아이들이 받은 물건의 값어치) 즉, 평균(avg)에 해당하는 것을 알 수 있다. 다음 고려해야 할 부분은 어떻게 분배해야 할 것인지이다. Input Data에서 한 사람당 받은 물건의 총 값어치를 알 수 있기에 1번에게 물건 배정 → 2번에게 물건 배정까지 한다면 남은 한 사람 3번은 나머지 물건을 가지며 될 것이다. 문제에서 "항상 물.. 2021. 5. 22.
[SWEA] 7794 동환이의 알뜰살뜰 출처: SWEA Approach 문제에서도 명시되어 있지만 할인금액은 아래와 같이 계산할 수 있다. 1% → 0.99 2% → 0.98 3% → 0.97 ex) 100만원, 3% 할인 적용 → 100 × 0.97 = 97만원 36만원, 2% + 3% 할인 쿠폰 적용 → 36 × 0.98 × 0.97 = 34.2216만원 구조체 배열 coupon[]에 할인 정보 저장 ex) 상품가격 = 100, 쿠폰 가격 = 1, 할인율 = 2 → {쿠폰 가격, 쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {1, 0.97, 2} ex) 상품가격 = 100, 쿠폰 가격 = 2, 할인율 = 2 → {쿠폰 가격, 쿠폰 할인율(백분율), 쿠폰 가격 대비 효율치(가성비)} = {2, 0.97, 1} ▶ 동일한 할인.. 2021. 5. 21.
[SWEA] 8569 개미 관찰 출처: SWEA Approach Parametric Search 를 적용하는 문제이다. [탐색] Parametric Search Parametric Search 최적화 문제를 결정 문제로 바꿔 푸는 것 O(logN) ex) Binary Search (이분 탐색)을 이용해서 Lower/Upper Bound를 구하는 경우가 많습니다. Binary Search (이분 탐색) Binary Search (이분 탐.. zoosso.tistory.com Lower Bound를 이용하는데 해당 개념에 대해 모른다면 아래 내용도 함께 참고 ▶ Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O.. 2021. 5. 20.
[SWEA] 8744 도로 제거 출처: SWEA Approach N개의 도시를 서로 한번씩 연결하면 (N × (N-1)) ÷ 2 의 간선이 생긴다. ex) N = 4 → (4 × 3) ÷ 2 = 6 "어떤 k개의 도로 폐쇄해도 서로 다른 두 도시간에 이동할 수 있음이 유지되도록 하고 싶다" 위 문제 조건을 이해한다면 어렵지 않게 구현할 수 있는 문제이다. 위 모습은 2(= M) 개의 간선을 제거한 상태이다. (각 도시에 남아있는 도로 개수는 {빨간 숫자}로 표시) "이동될 수 있음"을 보장하면서 도로를 추가로 제거한다면 도로 {② ↔ ④} 1(=k)개를 제거하거나 도로 {① ↔ ④}를 1(=k)개를 제거할 수 있다. 하지만 어떤 k개의 도로를 폐쇄해도 서로 다른 두 도시로 이동되어야 하기 때문에 제거되는 1개 도로가 {③ ↔ ④}가 된.. 2021. 5. 19.
[SWEA] 1248 공통조상 출처: SWEA Approach 노드 [8]의 부모노드는 [5]이며, [13]의 부모노드는 [11]이다. 위로 올라가면 공통 조상격인 [3]과 [1]이 있으며 가까운 공통 조상은 [3]이 된다. 가장 가까운 공통 조상노드를 기준으로 하였을 때, 서브트리의 크기는 아래와 같다. (기준 노드를 포함한 수치) ① 구조체로 트리(Tree) 구현 - 이진트리이므로 왼쪽/오른쪽 자식노드를 순차적으로 구성 - 공통 조상을 탐색하기 위해 부모노드 표시 ② 첫번째 대상 노드를 시작으로 부모 노드(들) 표시 ex) 정점 [8]에 대해서 [5] → [3] → [1] 노드들이 vistied[] 표시된다. ③ 두번째 대상 노드를 시작으로 조상 노드 추적 ex) [13]을 기준으로 조상 노드를 추적할 때, [11] → [6] →.. 2021. 5. 17.
[SWEA] 3421 수제 버거 장인 출처: SWEA Approach 버거를 만들 때, 재료가 하나도 없는 것도 하나의 버거가 될 수 있다. 즉, N개의 자료 중에 하나도 선택하지 않는 경우도 포함해야 한다. 조합(combination) 을 구현한다. - 재료 자체를 중복해서 선택할 수 없다. ▶ 순열과 조합 순열과 조합 (백준 N과 M 시리즈) 순열과 조합 순열(Permutation) / 조합(Combination)에서 개수를 구하는 경우에는 ▶ P(n, r) = n × (n - 1) × (n - 2) × ... × (n - r - 1) = n! / (n - r)! 상황에 따라서는 주어지는 Data가 나올 수.. zoosso.tistory.com ▶ N과 M (2) (중복 허용하지 않는 조합) [BOJ] 백준 15650 N과 M (2) 출.. 2021. 5. 16.
[SWEA] 4411 덕환이의 카드 뽑기 출처: SWEA Approach 조세푸스 점화식을 구현하는 문제이다. #include #define ULL unsigned long long ULL N, K, r; int tc, TC; int main() { // freopen("input.txt", "r", stdin); scanf("%d", &TC); for (tc = 1; tc 2021. 5. 16.
[BOJ] 백준 3020 개똥벌레 출처: https://www.acmicpc.net/problem/3020 Approach - 모든 지점(높이)에 대해서 N개의 장애물(종순, 석순)과 부딪히는지 확인한다면 TLE - 정렬 + 이분탐색을 통해 구할 수 있다. ▶ 합병 정렬(Merge Sort) ▶ Binary Search (이분 탐색) ▶ Parametric Search ① 이분 탐색 (lower_bound와 upper_bound) 하기 위해서 원소를 정렬 합니다. top = {2, 2, 3, 3, 3, 4, 4} bottom = {1, 2, 3, 3, 3, 3, 4} ② 정렬된 원소에서 특정 높이에서 개똥벌레가 출발할 때, 부딪히는 장애물 개수를 구해야한다. 출발 높이 pivot = 4라고 했을 때, bottom = {1, 2, 3, 3.. 2021. 5. 16.
반응형

티스토리툴바