코딩테스트

[백준] 도시 분할 계획

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 우선 문제부터 간단하게 요약하면, N개의 마을과 그 마을들을 연결하는 M개의 길이 있을 때, 마을을 두 그룹으로 나누고, 그 안에서 필요하지 않은 길을 모두 없앨 때, 길의 유지비 합을 최소로 할 때의 유지비를 구해야 하는 문제입니다. 문제를 직접 한번 읽어보는 것이 정확합니다. 우선 문제를 읽자마자 최소 신장 트리가 생각이 납니다. 그러면 최소 신장트리를 구..

[백준] 소수의 연속합

https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 우선 문제부터 간단하게 요약하면, N이 주어지면, 연속된 소수의 합으로 N을 구성할 수 있는 경우의 수를 구해야 하는 문제입니다. 우선 N까지의 숫자들중 소수를 에라토스테네스의 체로 구합니다. 그리고 이 소수들을 이용하여 누적합 배열을 만들어 두고, 총 몇개의 조합이 가능한지 투포인터 알고리즘을 이용하여 탐색하면 됩니다. 실제 구현은 아래와 같습니다. #include #include #include #define MAX 4000000 using namespace std; int N; int isPrime[MAX+10..

[백준] 계단 수

https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 45656과 같이 이웃한 자릿수가 모두 1차이나는 숫자들을 계단수라고 정의를 합니다. 이 때, 길이가 N 이면서 0~9까지의 숫자가 모두 등장하는 계단수가 총 몇개 있는지를 구해야 하는 문제입니다. 우선 가장 처음 생각 해볼 부분은, 12123... 12323... 위의 두가지 경우에 대해 뒤에 진행되는 부분에 대한 계산은 단 한번만 하면 된다는 점입니다. 즉 현재까지 사용된 숫자의 종류가 같고, 종료되었을 때의 가장 마지막 숫자가 같은 경우는 같은 case로 취급하면 된다는 것입니다...

[백준] 부분수열의 합 2

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, N개의 정수로 이루어진 수열에서 크기가 양수인 부분수열 중, 수열의 원소를 다 더한게 S가 되는 경우의 수를 구해야 하는 문제입니다. 부분수열의 정의는 인터넷을 한번 검색하고 시작하는 것이 좋을 것 같습니다. 우선 간단하게 시간복잡도를 생각해보면, 최대 40개의 숫자가 나올 수 있으므로 해당 숫자들을 뽑거나 뽑지 않는 가짓수..

[백준] 2진수 8진수

https://www.acmicpc.net/problem/1373 1373번: 2진수 8진수 첫째 줄에 2진수가 주어진다. 주어지는 수의 길이는 1,000,000을 넘지 않는다. www.acmicpc.net 우선 문제부터 요약하면, 2진수가 주어지면, 해당 수를 8진수로 바꾸어서 출력해야 하는 문제입니다. 뒤에서 부터 parsing을 해야하므로 나중에 들어온 input부터 처리할 수 있는 stack등의 자료 구조를 활용할 수 있습니다. 하지만 stack을 사용하면, push는 그냥 input으로 char array를 만들어 넣을 수 있지만 pop을 하게 되면, function call이 일어나거나 하면 속도가 느려질 수 있습니다. 그래서 직접 index를 이용하여 forloop를 이용하여 처리하였습니다...

[백준] 보석 도둑

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 우선 문제부터 간단하게 요약하면, 보석점을 상덕이가 털려고 하는데, 상덕이가 가진 가방에는 각각 보석 1개씩만을 넣을 수 있고, 각각의 가방은 담을 수 있는 보석의 최대 무게를 가지고 있습니다. 이 때, 훔쳐갈 수 있는 보석의 최대 가격을 구하는 것이 문제입니다. 우선 어떤 가방이 좋은 가방일지 생각을 해보면, 당연히 무게를 많이 담을 ..

[백준] 두 배열의 합

https://www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 www.acmicpc.net 우선 문제부터 간단하게 요약하면, A={1, 3, 1, 2}, B={1, 3, 2}, T = 5 이렇게 A, B 배열과 T값이 주어질 때, A의 부배열과 B의 부배열의 합이 T가 되도록 하는 모든 경우의 수의 갯수를 구해야 합니다. 부 배열과 같은 부분에 대한 정의는 문제를 한번 직접 읽어보는 것을 추천합니다. 사실 ..

[백준] 다각형의 면적

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 우선 문제부터 간단하게 요약하면, 주어진 N개의 점들이 순서대로 이어져 다각형을 구성하게 될 때, 해당 다각형의 넓이를 계산하는 것이 문제입니다. 기본적으로 "삼각형 여러개로 쪼개서 구하는 것이 좋지 않을까" 라는 생각이 가장 처음 듭니다. N각형은 분할된 N-2개의 삼각형의 넓이의 합으로 구할 수 있기 때문입니다. 그러면 이 삼각형의 넓이를 어떤 방식을 이용하여 구하는 것이 가장 효율적일까요? 물론 많은 방법이 있지만, ..