나그네

27968번: 사사의 사차원 사탕 봉지 문제 https://www.acmicpc.net/problem/27968 27968번: 사사의 사차원 사탕 봉지 첫 번째 줄에 아이의 수 $N$과 사사가 사탕을 꺼내주려고 하는 최대 횟수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 300 \, 000$, $1 \le M \le 300 \, 000$) 두 번째 줄에 사사가 한 번에 사탕을 꺼내는 www.acmicpc.net 풀이 누적 합 + 이분 탐색 문제로 사탕을 꺼낼 때마다 사탕의 수는 누적되므로 몇 번 꺼냈을 때 사탕이 얼마나 있는지 알 수 있다. 그리고 아이가 받고 싶어하는 사탕의 수가 정확히 꺼낸 수와 동일하지 않을 수 있으므로 lower_bound 함수로 최초로 같거나 큰 수의 사탕이 있..

16566번: 카드 게임 문제 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 풀이 철수가 낸 카드보다 숫자가 큰 카드 중 가장 작은 카드를 민수가 내도록 하면 된다. 즉, 사용할 수 있는 카드를 오름차순 정렬한 다음 upper_bound 함수를 사용하면 된다. (upper_bound 함수는 찾고자 하는 값을 초과하는 값 중 가장 작은 값의 iterator를 반환한다.) 그러나 같은 카드는 ..

2143번: 두 배열의 합 문제 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 풀이 n과 m이 최대 1000이므로 가능한 모든 부분합을 구한 다음 가능한 조합의 수를 구하면 된다. 즉, A 부분합 배열의 각 원소에 대해 T가 되기 위해 필요한 수가 B 부분합 배열에 몇 개가 있는지 확인한다. B 부분합 배열을 오름차순 정렬한 후 lower_bound, upper_..

3745번: 오름세 문제 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 풀이 수열이 주어졌을 때 점차 증가하는 부분 수열을 오름세라 하고 가장 긴 오름세를 찾는 문제다. 즉, 가장 긴 증가하는 부분 수열을 구하는 문제다. 범위가 10^5이므로 시간복잡도가 O(NlogN)인 알고리즘을 사용해 풀어야 한다. O(NlogN)으로 푸는 법은 아래 링크에 설명되어 있다. [12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 긴..

3066번: 브리징 시그널 문제 https://www.acmicpc.net/problem/3066 3066번: 브리징 시그널 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽 www.acmicpc.net 풀이 최대한 많은 시그널을 교차하지 않도록 연결해야 하므로 연결되는 포트의 번호가 증가하는 순서대로 많이 연결할 수 있도록 해야 한다. 따라서 이 문제는 가장 긴 증가하는 부분 수열의 크기를 구하는 문제다. N의 범위는 4 × 10^4이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 시간초과가 나므로 시간복잡도가 O(NlogN)인 알고리즘으로 풀어야 ..

12014번: 주식 문제 https://www.acmicpc.net/problem/12014 12014번: 주식 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 www.acmicpc.net 풀이 주가가 올랐을 때만 주식을 사고, 그리고 구매는 하루에 1번만 가능하고 최대 K번만 살 수 있다. 따라서 가장 긴 증가하는 부분 수열의 길이가 K 이상이면 조건을 만족하며 주식을 구매할 수 있다. N의 범위는 10^4이지만 테스트 케이스의 수가 10^2 이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 최대 시간복잡도가 10^10이 되므로 시간복잡도가 O(Nl..

1365번: 꼬인 전깃줄 문제 https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열(LIS)을 구하는 문제다. 전깃줄 문제와 같아 보이나 정렬할 필요가 없는 문제다. 왼쪽 전봇대의 위에서부터 차례대로 어디에 연결되어 있는지 주어지므로 순서대로 LIS를 구하면 된다. N의 범위가 10^5 이므로 시간복잡도가 O(NlogN)인 알고리즘으로 풀어야 시간초과가 안 난다. O(NlogN)으로 LIS를 구하는 방..

2352번: 반도체 설계 문제 https://www.acmicpc.net/problem/2352 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 풀이 전깃줄 문제와 같이 이어진 두 포트가 입력으로 들어오기 때문에 pair로 받아 저장한다. 왼쪽 포트 기준으로 가장 많이 이어야 하기 때문에 입력받은 값들을 정렬한 후 2568번 문제와 같은 알고리즘으로 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다. N의 범위가 4 × 10^4 이므로 시간복잡도가 O(N^2)인 알고리즘으로 풀 수 없고..

14003번: 가장 긴 증가하는 부분 수열 5 문제 https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 그리고 N의 크기가 10^6이기 때문에 시간복잡도가 O(N^2)인 알고리즘으론 시간초과가 나게 된다. 따라서 시간복잡도가 O(NlogN)인 알고리즘을 사용해 12015번 문제와 같이 가장 긴 증가하는 부분 수열(LIS)을 구할 수 있다. 그러나 이 알고리즘으론 길이만 구할 수 있고 정확한 수열을 구할 수는 없기..

12738번: 가장 긴 증가하는 부분 수열 3 문제 https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 풀이 12015번 가장 긴 증가하는 부분 수열 2 문제와 완전히 같은 알고리즘으로 풀 수 있다. 수열을 이루는 수의 크기에 변화가 있지만 int 범위 안이고 시간복잡도 자체에는 바뀔 부분이 없다. 12015번 해설은 아래 링크를 참고하자. [12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 ..