# Foundation/백준풀이
[이분탐색] 백준 7453 :: 합이 0인 네 정수
합이 0인 네 정수 성공한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율2 초256 MB7483159794720.196%문제정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.입력첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다.출력합이 0이 되는 쌍의 개수를 출력한다.예제 입력 1 복사6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -5..
2019. 5. 28. 01:48
# Foundation/알고리즘
이분탐색(Binary Serach) 알고리즘
이분탐색이란?매 단계마다 탐색범위를 절반씩 줄이는 방식.현재범위를 반으로 쪼갠 뒤, 답이 존재하지 않는 쪽을 제거한다. 업 다운 게임이 대표적인 예시인데,범위가 [0, 100]인 게임에서 최소횟수로 정답을 맞추려면, 정답이 있을법한 구간의 중간값을 골라서, 매번 정답의 범위를 절반으로 줄여야 한다. UP 이라면, 작은 구간에는 답이 없으며.DN 이라면, 큰 구간에는 답이 없다. 이분탐색의 제약이분탐색의 핵심은 정답이 없는 절반을 배제하는 것 이며,배제할 구간에 정답이 없다는 것을 확신할 수 있어야 한다. 업-다운 게임에서 이분탐색을 적용할 수 있는 이유는.50의 결과가 UP일때, 50이하에는 정답이 없다고 확신할 수 있기 때문이다. 중간값과의 비교를 통해 답의 위치를 알 수 있어야 하며, 수학적으로 풀어..
2019. 5. 24. 14:38
# Foundation/백준풀이
[이분탐색] 백준 1920 :: 수 찾기
수 찾기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB339878981592227.524%문제N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.입력첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.출력M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.예제 입력 1 복사5 4 1 5 2 3 5 1 3 7 9 5 예제 출력 1 복사1..
2019. 5. 23. 20:23
