문제 https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 설명 이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 형택이의 승률이 절대 변하지 않는다면 -1을 출력한다. 만약 현재 승률이 99% 또는 100%라면 승률이 절대 변할 수 없으므로 -1을 출력한다. 현재 게임을 X번 했으므로 start를 1, end를 X로 하고 이분 탐색을 진행한다. start와 end가 역전되기 전까지 mid를 계속해서 구해서 getPercent 함수를 이용해..
이분 탐색이란 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 원하는 데이터를 탐색하는 방법이다. 리스트의 중간 부분에 찾는 데이터가 있는지 확인하고, 없으면 왼쪽에 있는지 오른쪽에 있는지 판단한다. 이분 탐색은 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. 이분 탐색의 시간복잡도 원하는 데이터를 찾을 때까지 처음부터 끝까지 계속 탐색하는 순차 탐색은 Worst Case일 때 \(O(N)\) 이라는 시간복잡도를 가지므로 10만개의 데이터가 있을 때 10만번을 탐색해야 한다. 그러나, 이분 탐색은 탐색 대상을 절반씩 계속해서 줄여나가기 때문에 Worst Case일 때에도 탐색의 횟수가 \( log_{2} N \)이 되어 \(O(log N)\) 의 시간복잡도를 가지므로 10만개의 데이터가 ..
문제 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 설명 N개의 정수가 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내야 한다. 매번 하나씩 숫자를 비교하면서 탐색할 수 있지만 시간복잡도를 줄이기 위해 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 이분 탐색을 수행한다. 이분 탐색을 하기 위해서는 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있기 때문에 먼저 입력받은 수를 오름차..
