" (백준/ C++) 1106 - 호텔 " https://www.acmicpc.net/problem/1106 1106 - 호텔첫째 줄에 C와 형택이가 홍보할 수 있는 도시의 개수 N이 주어진다. C는 1,000보다 작거나 같은 자연수이고, N은 20보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 각 도시에서 홍보할 때 대는 비용과 그 비용으로 얻을 수 있는 고객의 수가 주어진다. 이 값은 100보다 작거나 같은 자연수이다.www.acmicpc.net 이 문제는 냅색과 비슷하다.다른 점이 있다면 중복으로 넣을 수 있는 점? 냅색 문제는 물건 하나 씩 넣는다. 가장 간단해보이는 예제 입력1번을 보고 DFS를 이용하여 풀 수 있는 방법을 고민해봤다.  " C명(12명)을 확보하면서 최소의 비용이 들어..

"(백준/ C++) 2629 - 양팔저울"https://www.acmicpc.net/problem/2629 아마 .. 양팔저울 문제 설명에 냅색 알고리즘으로 푸는 문제라고 적혀 있지 않으면 오랫동안 못 풀었을거 같다.. ^^;;  냅색과 같이 나올수 있는 무게의 경우를 만드는 방식으로 풀이를 했다. 점화식은 (가)저울에만 추를 둘수 있다고 생각 하고 경우의 수를 고려하였다. (가)에 A추가 있는 경우 → (가) A추 + 구슬 = (나) B추 → (가) 구슬 = (나) B추  -  A추 (나)에 A추가 있는 경우 → (가) 구슬 = (나) B추 + A추(가), (나)에 A추가 모두 없는 경우 → (가) 구슬 = (나) B추 처음에는 이분탐색으로 찾으려 했으나 메모리 문제로 실패 ! DP[비교대상개수][무게..

11438번: LCA 2 (acmicpc.net) 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 희소 테이블에 대해 모른다면 풀기 어려운 문제 일거 같습니다. 풀기전에 희소 테이블로 워밍업을 하고 천천히 풀어보자. 아래 주소는 희소 테이블에 관한 문제입니다. [Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께 (tistory.com) [Algorithm/ Sparse Table (희소테이블)] 백준 17435번과 함께 Sparse Table (스파스 테이블) 특징 방..

12738오늘은 가장 긴 증가하는 부분 수열 1, 2, 3, 4, 5를 모두 풀어볼겁니다. 이 문제들을 다 풀었다면 자연스럽게 11055번 가장 큰 증가 부분 수열과 11054번 가장 긴 바이토닉 부분 수열은 쉽게 풀수 있을겁니다. 저는 단계별로 풀어보기에서 이분 탐색을 풀면서 연관된 문제 그냥 다 풀어보자 하는 마음으로 풀어보았고, 많은 블로그도 보고 질문 게시판의 도움도 받으면서 풀었습니다. 자 이제 그럼 풀어봅시다.  ❗문제❗수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.11053..

https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 줄에 N과 C가 주어진다. N은 30보다 작거나 같은 자연수, C는 109보다 작거나 같은 음이 아닌 정수이다. 둘째 줄에 물건의 무게가 주어진다. 무게도 109보다 작거나 같은 자연수이다. www.acmicpc.net 이분 탐색은 생각하기 너무 어려운 문제인거 같습니다. 냅색이라는 이름만 보고 DP로 접근하려고 했는데 생각이 멈춰버렸습니다.... 언제 문제를 읽자마자 무슨 알고리즘을 써야하는지 떠오를까 ..ㅜㅜ 이 문제는 https://allmymight.tistory.com/99 [백준]1450번 냅색문제 - C++ https://www.acmicpc.net/problem/1450 1450번: 냅색문제 첫째 ..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. 두 수의 합이 0과 가장 가까운 것(음수도 있을 수 있음)을 찾아야 한다. ▶▷ 두 수의 합을 구하고 절댓값으로 비교한다. 2. 주어진 수는 정렬 돼서 주어지지 않는다. ▶▷ 정렬을 후, 투 포인터의 조건을 만들어준다. ※ ex) "백준 1644 - 소수의 연속함" 투 포인터 인덱스 움직임의 조건: sum이 N보다 작으면 t..

1644번: 소수의 연속합 (acmicpc.net) 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 문제 키워드 1. 연속된 소수의 합으로 나타낼 수 있는 자연수 2. 자기 자신이 소수 일 때도 카운트 해결 방법 1. 에라토스테네스의 체 알고리즘을 통해 N이하(N포함)의 소수를 찾아 Vector에 넣는다. 2. vector의 size가 0이 아닐 경우 두개의 index(oneIdx, twoIdx)는 vector의 맨 앞 인덱스 0을 가진다. 3 sum이 N보다 작으면 twoIdx를 클 경우 oneIdx를 증가시킨다. ※ sum은 one과 two 사이의 vector의 합 ▼TwoIdx ▲ OneIdx 코드 #include #inc..

4673번: 셀프 넘버 (acmicpc.net) 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net

11066번: 파일 합치기 (acmicpc.net) 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 너무 어려웠던 .. 파일 합치기 .. 많은 블로거들이 포스팅한 글을 봐도 이해가 거의 안갔다 @_@.. ㅋㅋㅋ 억지로 외우고 따라 써보고 코드 그대로 그림을 그려보니 이해가 갔던 문제 였습니다.. 다시 보고 또 다시 봐야 할 거 같습니다. for(int idx = 1; idx < K ; ++idx) { for(int x = 1; x + idx testcase; while(testcase--) { int ..

16139번: 인간-컴퓨터 상호작용 (acmicpc.net) 16139번: 인간-컴퓨터 상호작용 첫 줄에 문자열 $S$가 주어진다. 문자열의 길이는 $200,000$자 이하이며 알파벳 소문자로만 구성되었다. 두 번째 줄에는 질문의 수 $q$가 주어지며, 문제의 수는 $1\leq q\leq 200,000$을 만족한다. 세 번째 www.acmicpc.net * 이 전의 누적합으로 사용했던 배열 SumArr[MAX]를 알바벳 개수 만큼 증가 시킴. -> SumArr[26][MAX] #include #include #include #include using namespace std; #define MAX 200'001 int SumArr[26][MAX]; // 구간 합. int main(void) { ios_b..

2559번: 수열 (acmicpc.net) 2559번: 수열 첫째 줄에는 두 개의 정수 N과 K가 한 개의 공백을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 온도를 측정한 전체 날짜의 수이다. N은 2 이상 100,000 이하이다. 두 번째 정수 K는 합을 구하기 www.acmicpc.net 누적 합 * 가장 큰 값만 찾기 때문에 priority_queue 사용함.(기본 정렬 = less) * S값보다 크거나 같을 때부터 누적 합을 해주어 queue에 넣어줌. #include #include #include #include using namespace std; #define MAX 100'001 int SumArr[MAX], Arr[MAX]; // 구간 합. int main(void) { ios..

10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net ※틀린 답: 시간초과 (N^2) 왜 틀렸는지.. 그럼 어떻게 풀어야하는지.. 질문검색을 뒤져보는 중에.. 무슨 말이지??? .. 그래서 예제를 이용해서 천천히 정리해보았다. 1. 부분합을 M으로 나눈 나머지가 같은 것끼리 그룹을 짓는다고 생각해봅시다. SumArr[i] = (Arr[i] + SumArr[i-1]) % M; 범위 (1,1) (1,2) (1,3) (1,4..