Coding 01

https://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 Code import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; impo..

백준문제를 풀다가 이분 탐색을 사용하게 된 문제가 있어서 글을 써본다. 먼저 이분탐색이란 주어진 정렬된 리스트에서 특정한 값을 찾는 알고리즘으로, 리스트를 반으로 나누어 탐색 범위를 좁혀가며 원하는 값을 찾아가는 방식이다. 이 알고리즘은 매우 효율적으로 동작하고, 탐색 대상이 많은 큰 데이터 집합에서 유용하게 사용된다. 이분탐색은 O(log N)의 시간 복잡도를 가진다. 이분탐색 알고리즘을 글로 설명하자면 다음과 같다. 1. 처음에 주어진 리스트의 초기 인덱스와 끝 인덱스를 받아 2로 나누어 가운데 값을 구한다. ex) mid = (low + high ) / 2 2. 주어진 리스트는 정렬되어 있으므로 리스트의 mid에 위치하는 요소와 찾고자 하는 요소를 비교한다. 이때, 찾고자 하는 요소인 key 값이 ..