Patrick's Devlog

1. 문제 개요 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 1-1. 설명 N개의 정수 A[1], A[2], ..., A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오. 첫줄에 자연수 N이 주어지고 다음 줄에 N개의 정수가 주어진다. 다음 줄에는 M이 주어지고, 그 다음줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 1-..

개요 공부를 진행하다 오랜만에 이진 탐색을 꺼내려니 기억이 잘 나지 않아서 정리를 해두었다. 단순한 알고리즘이라, 정리해두고 기억이 나지 않을때 가끔씩 살펴보려 한다. 이진 탐색 알고리즘(Binary Search Algorithm) 정렬과 함께 가장 기초인 알고리즘으로 꼽힌다. 검색 범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 정확히 설명하면 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트의 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단해 맨 앞부터 검색하거나 중간부터 검색한다. 이진 탐색의 원리는 사전을 찾을 때 사전을 펴서 찾는 단어가 없으면 ..