알고리즘/백준(30)
-
[백준] [C++] 1275번 커피숍2 (segment tree)
1. 문제 1275번: 커피숍2 (acmicpc.net) 1275번: 커피숍2 첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합 www.acmicpc.net 2. 풀이 이 문제의 핵심은 수를 업데이트 시켜줘야한다는것이다. 배열을 사용하여 i번째까지의 합을 저장하여 psum[i] - psum[j] 로 구간합을 구하는 방식은 수를 업데이트하려면 최악의 경우 O(N) 의 시간 복잡도를 가진다. 하지만 이런 구간들을 이진 검색 트리 형태로 표현하게되면 그 수가 속하는 구간들을 업데이트하는데 O(lgn) 의 시간복잡도로 업데이트할 수 있다..
2021.07.10 -
[백준] [C++] 9466번 텀 프로젝트 (dfs, scc)
1. 문제 9466번: 텀 프로젝트 (acmicpc.net) 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 2. 풀이 이 문제는 간단히 그래프에서 순환하는 구간을 찾는것이다. 강결합 컴포넌트 의 타잔 알고리즘을 응용해서 문제를 해결하였다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55..
2021.07.04 -
[백준] [C++] 7579번 앱 (dp, knapsack, bsearch)
1. 문제 7579번: 앱 (acmicpc.net) 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 2. 메모이제이션과 결정문제 배낭문제의 변형, 값어치의 최대화가 아닌 비용이 최소인 값 이 문제는 아래와 같은 일반적인 방법으로 메모이제이션하는것은 불가능하다 (메모리의 최대 크기가 10,000,000, N의 크기가 100이기 때문에 128 MB보다 더 많은 메모리가 필요하다) solve(i, mem) = mem만큼 메모리를 비웠을때, i번째 인덱스에서 시작하여 최소인 cost를 리턴 solve(i, mem) = mi..
2021.07.03 -
[백준] [C++] 14003번 가장 긴 증가하는 부분 수열 5 (bsearch)
1. 문제 14003번: 가장 긴 증가하는 부분 수열 5 (acmicpc.net) 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 2. N log N O (N lg N) 만에 lis를 구하는 방법 키워드는 "증가" 인덱스 0 부터 차례대로 수열의 수들을 스택에 담는다. 이때 top보다 더 작은 수가 들어온다는것은 lis가 연결되지 않는다는 의미이다. 하지만 이 원소를 포함한 lis가 만들어 질 수 도 있다. 따라서 이 원소를 스택안에서 이것보다 크지만 최소인 원소랑 바꾼다 (low..
2021.07.02 -
[백준] [C++] 2623번 음악프로그램 (DFS, 위상정렬, 사이클, DAG)
1. 문제 2623번: 음악프로그램 (acmicpc.net) 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 2. 간략한 풀이 이 문제는 각각 PD들이 주는 목록들을 합쳐 트리로 만들고, 그 트리를 위상정렬하면 자연스럽게 모든 pd의 요구사항을 만족할 수 있다. 하지만, PD들 서로의 목록에 모순(순환, 사이클) 이 있는 경우 모든 pd들의 요구사항을 만족할 수 없으니. 위상정렬을 하면서 사이클 존재 여부 또한 검사해야한다. 3. 위상 정렬 맨 마지막 노드인 리프를 제일 끝에 두는 방법이 ..
2021.07.02 -
[백준] [C++] 2473번 세 용액 (bsearch, two pointer)
1. 문제 2473번: 세 용액 (acmicpc.net) 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2. 이진 탐색 일단 용액들을 정렬하고 난 뒤, 완전 탐색으로 두개의 용액을 합한다. 그리고 그 합과 합할 나머지 용액하나를 정렬된 배열에서 이진 탐색하는 방법으로 문제를 해결하였다. 총 수행시간은 O(N^2 lgN) 이 걸린다. 이 문제를 풀때 시도를 많이 했는데, 문제는 타입이였다. 이전 용액 문제에서는 두개의 용액으로, 합해도 20억이 넘지 않았지만 이 문제는 3개의 용액이므로 ..
2021.07.01