본문 바로가기
반응형

전체 글1310

[BOJ] 백준 2533 사회망 서비스(SNS) (Greedy) 출처: https://www.acmicpc.net/problem/2533 Input 8 1 2 1 3 1 4 2 5 2 6 4 7 4 8 Output 3 Greedy 방식 트리 구조이므로 "단말 노드 개수 ≥ 단말 노드 부모 개수" 이는 단말 노드를 얼리어댑터로 설정하는 것이 전체 얼리어댑터의 개수를 최소화하는데 도움이 되지 않습니다. 단말 노드보다 부모 노드를 얼리 어댑터로 설정하는 것이 전체 얼리어댑터 개수를 최소화하는 것입니다. 단말 노드를 얼리어댑터로 하지 않았다고 생각하면 단말 노드의 부모는 반드시 얼리어댑터이어야 합니다. 그리고 아랫부분을 제외해서 또 다른 부분 문제로 생각할 수 있습니다. child가 모두 얼리어댑터라면 부모 노드는 얼리어댑터로 선택하지 않는다. child에 얼리어댑터가 아닌.. 2021. 2. 27.
[BOJ] 백준 2533 사회망 서비스(SNS) 출처: https://www.acmicpc.net/problem/2533 Input 8 1 2 1 3 1 4 2 5 2 6 4 7 4 8 Output 3 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com "사회망 서비스에 속한 사람들은 얼리 어댑터이거나 얼리 어댑터가 아니다." "얼리 어댑터가 아닌 사람들은 자신의 모든 친구들이 얼리 어댑터일 때만 이 아이디어를 받아들인다." → 두 사람이 친구 사이.. 2021. 2. 27.
[Jungol] 정올 1180 Dessert 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=463&sca=9040 Input 7 Output 1 + 2 - 3 + 4 - 5 - 6 + 7 1 + 2 - 3 - 4 + 5 + 6 - 7 1 - 2 + 3 + 4 - 5 + 6 - 7 1 - 2 - 3 - 4 - 5 + 6 + 7 1 - 2 . 3 + 4 + 5 + 6 + 7 1 - 2 . 3 - 4 . 5 + 6 . 7 6 사전순으로 최대 20개까지 출력하는 것이므로, 1 ~ 20까지의 숫자 순서는 변화가 없습니다. 문제에서 주어진 연산도 "+", "-", "." 순으로 우선순위를 가집니다. → 수와 수 사이에 연산자의 개수는 N - 1 개 입니다. → 가능한 경우의 수는 3N-1 에 해당합니.. 2021. 2. 27.
[Jungol] 정올 1681 해밀턴 순환 회로 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=954&sca=3030 Input 5 0 14 4 10 20 14 0 7 8 7 4 5 0 7 16 11 7 9 0 2 18 7 17 4 0 Output 30 1→ 4 → 5 → 2 → 3 → 1 ▶ 10 + 2 + 7 + 7 +4 = 30 ① 1번을 출발지로 DFS 탐색 ② void DFS(int depth, int v, int cost) 인자: 현재 단계(경유한 곳의 개수), 현재 위치, 누적 비용 ③ 마지막 시험장에서 다시 집으로 돌아올 수 있어야 합니다. 따라서 마지막에 집으로 오는 비용도 고려해야 합니다. ※ 분기한정을 통해 시간 효율을 올릴 수 있습니다. #include const int .. 2021. 2. 27.
[Jungol] 정올 1013 Fivestar (Bitwise) Input 5 6 .*.... .***** .*.... *****. .*.... Output 3 출처: 정올 Jungol 1013 Fivestar 해당 포스팅은 Bitwise를 이용한 풀이 다른 방식 풀이: [Jungol] 1013 Fivestar [Jungol] 정올 1013 Fivestar 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=292&sca=50 Input 5 6 .*.... .***** .*.... *****. .*.... Output 3 가로로만 막대를 놓는 경우 그리디 알고리즘으로 쉽게 막대의 개수를 구.. zoosso.tistory.com #include int N, M, ans = 100; int row[11], column.. 2021. 2. 27.
[Jungol] 정올 1013 Fivestar 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=292&sca=50 Input 5 6 .*.... .***** .*.... *****. .*.... Output 3 가로로만 막대를 놓는 경우 그리디 알고리즘으로 쉽게 막대의 개수를 구할 수 있습니다. 앞에서부터 차례대로 아직 덮지 않은 '*'를 덮어 나가면 됩니다. 이 때 가능한 오른쪽으로 덮을 수 있는 '*'을 최대한 함께 덮어야 합니다. 행의 수가 5개 미만이 경우 열의 최대 길이는 최대 10이므로 ***** 막대기를 놓는 경우는 0~2개 입니다. 중간에 하나의 점만 포함되어도 2개의 막대기를 가로로 놓을 수 없습니다. ex) "*****.****" / "********.*" 한쪽으로 몰려서 5.. 2021. 2. 27.
[Jungol] 정올 2270 여객선(Cruise) 출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1983&sca=9040 Binary Search (이분 탐색) Binary Search (이분 탐색) Binary Search (이분 탐색) 정렬된 자료에서 목표값을 찾고자 할 때, 사용되는 탐색기법 O(logN) 리스트 중간의 값(mid)을 선택하여 찾고자 하는 값과 비교하는 방식 분할 정복 알고리즘(Divide and Conquer Al zoosso.tistory.com 최대 수용무게가 10인 배를 이용해서 1, 2번째 승객을 태운 다음, 최대 수용무게가 15인 배를 이용해서 3, 4, 5, 6번째 승객을 태우면 최대 수용무게가 12인 배를 출항하지 않으므로 최적이 된다. ① 배들을 배치하는 경.. 2021. 2. 27.
[BOJ] 백준 1655 가운데를 말해요 출처: https://www.acmicpc.net/problem/1655 [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 값이 계속 들어올 때마다 중간값을 출력해주어야 하기 때문에 매번 정렬을 해서 가운데 값을 출력해주면 TLE 발생. 우선순위 큐 사용하여 해결 < 최대 힙(Max heap)과 최소 힙(Min heap) 구조 이용 1. 최대 힙의 크기가 최소 힙의 크기보다 1 크거나 같도록 유지하며 값을 넣는다. 2. 값을 넣어준 후 최대 힙과 최소 힙의 t.. 2021. 2. 27.
[BOJ] 백준 2696 중앙값 구하기 출처: https://www.acmicpc.net/problem/2696 [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 우선순위 큐 이용 (C++ STL priority_queue는 내부적으로 Heap 구조로 이루어져 있음) - 우선순위큐를 2개 준비 (최대 힙과 최소 힙) - 새로운 원소가 들어올 때 다음의 과정 수행 ① 두 개의 큐에 쌓인 원소의 개수 비교 - 같으면 maxHeap에 push - 다르면 minHeap에 push 결과적으로 maxHeap의.. 2021. 2. 27.
[BOJ] 백준 17612 쇼핑몰 출처: https://www.acmicpc.net/problem/17612 [그래프] 힙(Heap) 자료구조란? 힙(Heap) 자료구조란? Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진 zoosso.tistory.com 먼저 대기하고 있는 고객이 계산대에서 물건을 계산하고 쇼핑몰을 빠져 나갑니다. → FIFO (First In First Out) - 계산대가 2개이상 동시에 비는 경우 낮은 번호 계산대에 먼저 배정 ex) 3번, 5번 계산대가 비게된다면 3번으로 안내 - 계산이 동시에 끝나는 경우에는 (출구에 가까운)높은 번호 계산대에 있는 고객이 먼저.. 2021. 2. 27.
반응형

티스토리툴바