모기와의 스파링 기록장

이진 탐색이란?이진 탐색 알고리즘은 정렬된 배열, 리스트에서 원하는 값을 빠르게 찾아낼 수 있는 알고리즘이다. 이진 탐색이 얼마나 빠른지는 다른 대표적인 알고리즘인 선형 탐색 알고리즘과 비교해볼 수 있다. 선형 탐색의 경우, 앞에서부터 차례대로 탐색하므로 O(n)의 시간복잡도를 갖지만 이진 탐색은 무려 O(log n)의 시간복잡도를 갖는다. 하지만 배열이 정렬된 상태에서 이진 탐색이 올바르게 작동함을 유의해야 한다.    이진 탐색 알고리즘 설명이진 탐색 알고리즘의 핵심은 탐색 범위를 반으로 좁히는 것에 있다. 탐색 범위의 중앙에 있는 값을 보고, 우리가 찾는 값이 어느 범위에 있을지 찾아내는 것이다. 따라서 중복 없이 오름차순 정렬된 배열에서 이진 탐색은 아래와 같은 순서로 진행된다.배열 내에서 값 k..

문제 링크https://www.acmicpc.net/problem/12789    풀이 과정# 문제에서의 예시1번을 통과시키기 위해 1번 앞에 있는 5번, 4번을 모두 왼쪽 공간으로 이동시킨다.그리고 2번을 통과시키기 위해 앞의 3번을 왼쪽 공간으로 이동시킨다.줄에 있는 사람이 다 없어졌다면, 왼쪽 공간의 3~5번이 왼쪽 공간으로 들어온 순서의 반대로 통과한다. 원래 서있던 줄에서는 순서대로 빠져나갈 수 있고, 왼쪽 공간에서는 들어온 순서의 반대로 빠져나가는 것을 이용해 문제를 해결해야 한다. 1번을 먼저 통과시키기 위해, 입력으로 들어온 순서 정보를 큐에 저장한 뒤 순차적으로 조사하면 문제 상황을 구현할 수 있다. 큐의 앞부분을 확인하고 제거하는 식으로 큐를 순차적으로 조사할 수 있다.(이때 제거의 의..