코드 낙서장

15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 확인 트리 dp 문제입니다. 풀이 그래프를 입력받아서 작성하고 dfs를 통해 dp 값을 채워 넣어주면 됩니다. 자신을 포함하여 서브트리의 정점 개수이므로 초기값은 1로 설정을 하고 자식들의 dp값을 합쳐주면 결과를 얻어낼 수 있습니다. for(auto child : cur.edge) if(child != prev) dp[cur] += dfs(child, cur); prev 값은 되돌아가는 것을 방..

1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 문제 확인 문자열 혹은 숫자 자릿수를 활용하는 문제입니다. 풀이 간략한 풀이를 위해 입력을 문자열로 받습니다. 최대의 숫자를 만들기 위해서는 몇 가지를 고려해야 합니다. 맨 앞자리는 1~9 중 재일 높은 수가 나와야 합니다. 모든 수를 고르고 난 후 남은 n-k개의 수는 가장 긴 자릿수 중 재일 높은 수를 선택해야 합니다. 1번을 고려할때 주의해야 할 점은 91, 9 의 경우9/91이 더 높은 숫자를 만들 수 있는 것입니다. 이를 위해..

문제 주소 : www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 문제 확인 문자열과 정렬을 이용해서 풀 수 있습니다. 풀이 입력받을 시 문자열 다음에는 공백 혹은 \0이 입력되고 이를 구분해서 풀 수 있습니다. fgets를 통해 한번에 문자열 집합을 입력받고 qsort 함수를 통해 정렬을 합니다. qsort 정렬 시 strcmp 함수를 통해 같은 굴에서 뻣어가는 굴일 경우 교차점 이전까지 문자가 모두 같기 때문에 사전 순서대로 정렬됨을 이용합니다..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제 확인 조합과 자료구조를 사용하는 문제입니다. 풀이 dfs로 메뉴 조합을 찾을 수 있지만 최대 depth가 10이고 손님마다 dfs를 모두 돌면 많은 시간이 걸리기 때문에 조합을 찾는 특별한 알고리즘을 사용합니다. 파이썬에서 사용하는 combination 함수를 구현하여 사용합니다. combination 함수는 permutation 방식을 사용하여 조합을 구하는 방식이며 std::next_permutation 함수를 사..

2021 카카오 코딩 테스트 문제입니다. 코딩테스트 연습 - 신규 아이디 추천 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가 programmers.co.kr 문제 확인 코딩 테스트에 단골 문제인 문자열 처리 문제입니다. 모든 테스트 케이스에서 최대 0.02ms 정도 빠른 시간을 받기 위해 한 번의 루프로 처리를 해 줍니다. 풀이 객체 처리는 일반 char 배열에 비하여 느리므로 char와 인덱싱을 통해 풀어줍니다. 좀 더 빠른 실행을 위해 7단계를 3단계로 합칩니다. 1, 2, 3, 6 단계와 4단계 일부분을 처음 문자열 탐색에 모두 마치고 4단계를 한번 더 검증한 후 5..

문제 주소 : www.acmicpc.net/problem/2983 2983번: 개구리 공주 트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르 www.acmicpc.net 문제 확인 링크로 연결해서 풀 수 있지만 링크를 사용하는 것 자체가 인덱싱에 비하여 느리므로 그래프 형식으로 인덱스를 저장해서 풀었습니다. 풀이 개구리는 4방향 (P, P), (-P, -P), (-P, P), (P, -P) 방향으로 점프를 하기 때문에 x, y축에 대하여 식을 새워 다음과 같이 m값으로 나타냅니다. 따라서 점 x, y에서 특정 방향으로 이동하기 위해서는 x, y와 움직일 위치가 같은 m..

문제 주소 : 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..