코드 낙서장

문제 주소 : www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net 문제 확인 트리에서 dp 문제입니다. 얼리 어답터인 경우 친구는 얼리 어답터이거나 아닐 수 있지만 자신이 얼리 어답터가 아닌 경우 친구 중 한 명은 꼭 얼리 어답터이어야 함을 이용합니다. 이 말은 즉 자신의 모든 친구가 얼리 어답터가 아니라면 자신이 얼리 어답터가 돼야 함을 의미하고 반대로 모든 친구가 얼리 어답터라면 나 자신은 어답터일 필요가 없습니다. 풀이 depth 조절과 효율성을 위해..

문제 주소 : www.acmicpc.net/problem/1033 1033번: 칵테일 august14는 세상에서 가장 맛있는 칵테일이다. 이 칵테일을 만드는 정확한 방법은 아직 세상에 공개되지 않았지만, 들어가는 재료 N개는 공개되어 있다. 경근이는 인터넷 검색을 통해서 재료 쌍 N www.acmicpc.net 문제 확인 a -> b 관계식이 있을 때 b -> c 관계식이 a에게 영향을 미치므로 그래프 탐색 문제입니다. 풀이 문제에서 주어진 n개의 vertex와 n-1개의 edge를 가지면서 n개의 vertex에 대한 모든 관계식을 나타내기 위해서는 사이클이 존재할 수 없습니다. 따라서 입력받을 시 edge를 작성하면서 비율을 맞춰가면 됩니다. 최대 공약수, 최소 공배수를 활용해 곱할 값을 찾아냅니다. ..

문제 주소 : www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 문제 확인 브루트 포스 혹은 수학으로 풀 수 있는 문제입니다. 풀이 브루트 포스를 통해 ax + b 식을 구해 풀 수 있지만 느리므로 계산식을 이용해 풀었습니다. n = 1의 경우 뒤에 어떠한 숫자가 올 수 있으므로 A n = 2의 경우 x1 = x2 일 때 나올 수 있는 식은 y = x + 0, y = -x + 2 * x1로 2가지가 나옵니다. 하지만 x1 = x2 이므로 두 식의 결과는 항상 일정한 x1 값이 나오므로 x1을 출력합니다. 그 외의 경우는 나올 ..

문제 주소 : www.acmicpc.net/problem/2534 2534번: 카드 배열 첫 번째 줄에는 전체 카드의 수를 나타내는 N과 선택하는 카드의 수 k와 제약조건의 수 P가 하나의 빈칸을 사이에 두고 주어진다. 단, 3> p; for (int i = 0; i > a >> b; gph_1[b].push_back(a);//역순 gph_2[a].push_back(b); d_1[a]++;//역순 indegree = a d_2[b]++; } //최댓값 for (int i = 0; i n-1 for (int next : gph_1[t]) if (!--d_1[next]) pq.push(next); } //최솟값 for (int i = 0; i 0 while (!pq.empty()) { int t = pq.t..

문제 주소 : www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이 www.acmicpc.net 문제 확인 위상 정렬 문제입니다. 위상 정렬이란 간단하게 말해서 사이클이 없는 방향 그래프에서 방향을 한쪽으로 몰아세우는 정렬 방법입니다. 자세한 설명은 다음 블로그에서 잘 해두었습니다. Topological Sort(위상 정렬) DAG에서 방향성을 거스르지 않게 정점들을 나열하는 알고리즘을 Topological sort(위상 정렬)이라 합니다. DAG란 Direc..

문제 주소 : www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 확인 특별한 알고리즘이 필요 없는 스택을 이용한 구현 문제입니다. 풀이 입력받은 직사각형의 높이와 i 값을 스택에 쌓으면서 기록합니다. 다음 나오는 직사각형의 높이에 따라 다음과 같이 동작합니다. 다음 직사각형의 높이에 높다면 계속해서 스택을 쌓아갑니다. 높이가 같은 경우 시작 지점인 i값을 기록해 두었으므로 스택에 넣을 필요가 없습니..

문제 주소 : www.acmicpc.net/problem/16287 16287번: Parcel 입력은 표준입력을 사용한다. 입력의 첫 줄에는 무게 w(10 ≤ w ≤ 799,994)와 A의 원소 개수 n(4 ≤ n ≤ 5,000)이 공백으로 분리되어 주어진다. 다음 줄에는 A의 원소인 n개의 정수 ai ∈ A(1 ≤ i ≤ n)가 www.acmicpc.net 문제 확인 dp 문제입니다. dp를 사용하지 않고 4중 포문으로 풀면 n이 5000이기 때문에 시간 초과가 납니다. 따라서 문제를 i + j, w - (i + j) 두 파트로 나누어 문제를 풀어야 합니다. 풀이 무게를 인덱스로 활용해 만들 수 있는 무게를 기록합니다. 각 원소의 최대 크기는 200000으로 dp[400000]을 사용합니다. 2중 포문..

문제 주소 : www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 확인 dp로 풀어도 되지만 a를 둔 후 z를 분배하는 식으로 중복 조합을 이용해 풀 수 있습니다. 풀이 a를 두고 z를 분배하는 식으로 점화식을 짜봅니다. 예를 들어 a : 3, z : 4 일 경우 _a_a_a_ 로 두고 z를 분배할 수 있는 공간은 4칸이 됩니다. 따라서 총경우의 수는 a+1 H z로 35가지가 나옵니다. 문제의 조건에 따라 k가 35 보다 높은 경우 -1을 출력해 예외처리를 해 줍니다. z를 분배하는 식은 z의 개수에 ..

문제 주소 : www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 확인 정렬 후 최선의 선택을 하는 Greedy 알고리즘으로는 예외가 있는 문제를 해결할 수 없습니다. memory : 30 10 50 cost : 2 3 4 위와 같은 경우 확보해야 할 메모리가 40인 경우 cost가 적은 2개를 선택하게 되면 잘못된 답이 될 수 있습니다. 따라서 dp로 풀어야 합니다. 풀이 cost의 크기가 작기 때문에 인덱스로 활용할 수 있어 사용할 앱 : i, cost : j..

문제 주소 : www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 문제 확인 숫자 처리 구현 문제입니다. 주의해야 할 점은 첫 시작 페이지가 1이며 n자릿수 수에 재일 앞자리 수는 0이 될 수 없습니다. 풀이 현재 자리수의 숫자 기준으로 경우의 수를 나눌 수 있습니다. 예를 들어 1234라는 수가 있을 때 첫자리부터 경우의 수를 생각해 봅시다. XXX0 의 경우 0000은 없는 페이지 이므로 XXX에 001~123 까지 총 123의 경우의 수가 있습니다. XXX1 ~ XXX4 까지의 경우 XXX 자리에 000~123 까지 총 1..