https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 1. Logic 이 문제를 접근할 때 처음에는 이분탐색이 아닌 투포인터로 접근하려고 했었다. 입력이 1000개이기 때문에 시간복잡도를 맞춰야 했고 N^3으로는 풀지 시간내에 계산을 못한다. 적어도 N^2logN정도를 맞춰야 했다. 이분탐색으로 가능했는데 이분탐색에 대한 로직은 1. 입력 받은 수를 토대로 3개의 수 중 2개의 수를 합쳐놓은 sum 배..
이분탐색
https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 1. Logic - 처음 문제를 딱 봤을 때 map이 먼저 생각났다. map로 선언한 후 접근하면 풀릴 것 같았다. 그리고 이후에 문제의 범위를 봤을때 500000이길래 이분탐색을 사용해서 숫자를 찾아야하는구나 라고 느꼈다. 사실 map과 이분탐색 둘다 해봤는데 둘다 통과 된다. 하지만 이분탐색이 시간복잡도가 더 작을 뿐이다. 2. Code map을 이용한 풀이 #i..
https://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 ≤ 1, www.acmicpc.net 1. Logic 스탠다드한 이분탐색 문제이다. 중앙값을 구한 뒤 입력 받은 사탕들 중에서 나눗셈연산자로 사탕의 갯수를 구해주면 된다. 2. Code #include using namespace std; int nephew, cookie; vector input; bool check(int val) { int re..
https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 1. Logic 완전탐색으로 이 문제를 풀게되면 2^40을 하면 약 1조정도가 나와 당연히 시간초과가 당연히 뜰것같았다. 그래서 시간복잡도가 O(logN)인 이분탐색을 써서 풀면되겠다는 생각을 했다. 이분탐색을 input의 반을 나눠서 왼쪽과 오른쪽 부분에 대해 탐색을 돌고 0~n/2까지의 구간의 부분수열의 합을 map에 넣어준다. n/2~n까지의 구간의 부..
https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 1. Logic 스탠다드한 이분탐색 문제이다. 주의할 점은 문제에서 포커스를 맞춰야 할 곳이 절단기에 설정할 높이를 구하는 것이고, 절단기에 설정한 높이를 나무의 길이에서 빼준 값으로 비교해야 한다는 점이다. 이분탐색이 이해가 잘 안간다면 아래의 알고리즘 설명글을 참고하면 좋을 것 같다! https://go2gym365.tistory.com/87 [Algor..
1. 이분탐색이란? 이분 탐색 알고리즘은 정렬되어 있는 배열에서 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 알고리즘이다. 이분탐색은 결정 문제의 답이 이분적일 때 사용할 수 있는데 대표적인 예시로 카드 뽑기 문제가 있다. 결정 문제란 답이 Yes or No인 문제를 의미한다. 시간 복잡도 : O(logN) 카드 뽑기 문제는 1 ~ 50까지 오름차순으로 정렬된 카드묶음에서 28번 카드를 찾는 문제를 예시로 들어보겠다. 첫번째 카드부터 n번째 카드는 card[i], 우리가 찾고자 하는 카드인 28은 val로 가정한다. 이때 문제를 푸는 방법에 v[i] >= val 인가를 잡으면 답은 1~27까지는 False, 28이후로는 True가 나오게된다. 이때 우리가 찾고자 하는 값은 처음으로 card[i] >= ..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 1. Logic - 기본적인 LIS문제이다. 이 문제가 LIS인 이유는 전깃줄이 교차하지 않아야한다는 것은 이전 전깃줄의 번호가 다음 전깃줄의 번호보다 커지면 안되고 항상 작은 번호여야하기 때문에 증가하는 부분수열이 될 수 밖에 없다. 다른 LIS문제와 다른점은 단지 입력 값을 pair로 받아 준 다음 A를 기준으로 오름차순 정리해주고 B를 기준으로 LIS를 찾아주면 된다. 공부겸 시간복잡도가 O(nlo..
