www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 아이디어: 뭔가 일단 정렬을 해야 할 것 같다. 근데 이걸 투 포인터로 어떻게 풀 수 있을까? 모든 경우를 찾아본다면, 가능한 두 수를 모두 뽑고 그 합과 같은 숫자가 있는지 탐색할 수 있을 것이다. 탐색은 이분 탐색이 가능할 것 같다. 근데 이게 시간 안에 풀어질까..? 그래서 구글링함^^ 내 생각이 조금은 맞았다. 대신 반대로, arr에 있는 모든 수를 돌면서 합이 arr[i]가 되는 두 수가 있는지를 찾는다. 이때 투 포인터를 이용한..
알고리즘💻
www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 아이디어: G = 현재 몸무게^2 - 기억하던 몸무게^2 현재 몸무게와 기억하던 몸무게가 뭐든 될 수 있으니까..(이게 무슨..) 자연수의 제곱 중에서 투포인트를 사용해서 차가 G가 되는 경우를 구하자. 일단 가능한 몸무게의 배열을 만들고 (1~200000까지의 제곱) result, left, right 모두 0으로 초기화한다. result가 g보다 큰 경우 left++, 작은 경우 right++ import sys ..
www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 아이디어: 투 포인트로 구현하면 되고, 대충 로직은 강의 들으면서 이해했는데 구현 과정에서 애를 먹었다. 이래서 어설프게 알면 안돼..ㅠㅠ left, right 포인터를 0, 0 으로 초기화하고 합result와 출력할 답 ans 도 0으로 초기화한다. 무한루프를 돌면서 합이 m보다 클 경우에는 합을 줄여야 하므로 result에서 arr[left]값을 빼고 left++한다..
www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아이디어: prefix sum(누적 합)을 이용하..
www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 아이디어: 이분 탐색으로 푼다는 게 무조건 mid 값을 찾는다는 게 아닌가보다..((아닐수도)) 1. 정렬 2. high = n-1, low = 0으로 포인터를 설정하고, while문을 수행하면서 특성값을 구하고 절댓값을 취하여 최솟값을 업데이트한다. 특성값이 음수면 low++(0에 가까워지려면 커져야 되니까), 양수면 high--(0에 가까워지려면 작아져야 되니까) impor..
www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 레슨 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 레슨이 들어가는데, 블루레이를 녹화할 때, 레슨의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 아이디어: 블루레이 크기를 이분 탐색. high = 10^9, low = 1 레슨의 길이를 더하다가 mid보다 같거나 커지면 블루레이 개수 +1 레슨의 길이가 M보다 크면 low = mid + 1, 같거나 작으면 블루레이 크기를 더 줄여야 하니까 high = mid - 1하고 ans 업데이트 import sys n, m = map(int, sys.stdin.readline().split()) arr = list(map..
www.acmicpc.net/problem/16401 16401번: 과자 나눠주기 첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 과자 N개의 길이 L1, L2, ..., LN이 공백으로 구분되어 주어진다. 과자의 길이는 (1 ≤ L1, L2, ..., LN www.acmicpc.net 아이디어: 막대 과자의 길이를 이분 탐색하여 조카 n명에게 줄 수 있는 과자 길이의 최댓값을 구한다. import sys m, n = map(int, sys.stdin.readline().split()) arr = list(map(int, sys.stdin.readline().split())) high = 1000000000 low =..
www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 아이디어: 시간을 이분탐색하여 시간의 최솟값을 찾는다. import sys n, m = map(int, sys.stdin.readline().split()) time = [] for _ in range(n): time.append(int(sys.stdin.readline())) high = 10**18 low = 1 ans = high while (high>=low): mid = (high+low..
www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 아이디어: 이분 탐색의 기본 문제. 이분탐색의 로직을 잘 익히자. import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) arr.sort() m = int(sys.stdin.readline()) num = list(map(int, sys.stdin.read..
www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 아이디어: 배낭 문제 dp[i][k] = 최대 배낭 수용 무게가 k일때, i번째 까지의 물건을 봤을 때 가치의 최대합 i번째 물건을 넣을 수 있는 경우(k>=wi): max(dp[i-1][k-wi]+vi, dp[i-1][k]) i번째 물건을 넣을 때 vs 넣지 않을 때 가치가 더 큰 것 선택 i번째 물건을 넣을 수 없는 경우(k dp[n][k] ..
