# 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
# Foundation/백준풀이
[정렬] 백준 2230 :: 수 고르기
수 고르기 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB131938628328.442%문제N(1≤N≤100,000)개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오.예를 들어 수열이 {1, 2, 3, 4, 5}라고 하자. 만약 M=3일 경우, 1 4, 1 5, 2 5를 골랐을 때 그 차이가 M 이상이 된다. 이 중에서 차이가 가장 작은 경우는 1 4나 2 5를 골랐을 때의 3이 된다.입력첫째 줄에 두 정수 N, M(0≤M≤2,000,000,000)이 주어진다. 다음 N개의 줄에는 차례로 A[1], A[2], …, A[N]이 주어진다. 각각..
2019. 5. 17. 18:10
# Foundation/백준풀이
[정렬] 백준 2399 :: 거리의 합
거리의 합 성공시간 제한메모리 제한제출정답맞은 사람정답 비율1 초128 MB162880764252.110%문제수직선에 n개의 점이 찍혀 있다. 각각의 점의 x좌표가 주어졌을 때, n2개의 모든 쌍에 대해서 거리를 더한 값을 구하는 프로그램을 작성하시오.즉, 모든 i, j에 대해서 |x[i] - x[j]|의 합을 구하는 것이다.입력첫째 줄에 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 x[1], x[2], x[3], …, x[n]이 주어진다. 각각은 0 이상 1,000,000,000 이하의 정수이다.출력첫째 줄에 답을 출력한다.예제 입력 1 복사5 1 5 3 2 4 예제 출력 1 복사40 문제 풀이처음 봤을 땐, 정렬문제가 맞을까 의심했던 문제.수학이 이렇게 중요합니다 여러분, 1차 풀이 ( ..
2019. 5. 17. 15:43
