문제 링크 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 풀이 간단한 이분탐색 문제 같지만 생각할 예외가 있는 문제였습니다. 처음에는 단순히 배열을 정렬한 후 초기 start를 0, end를 현재 확인하고 있는 인덱스의 앞까지로 해서 이분탐색을 진행하면 되지 않을까 했습니다. 하지만 이렇게 할 경우 아래 테케와 같이 동일한 숫자가 여러 개일 경우 문제가 발생합니다. 4 0 0 0 0 1번 0은 뒤에 있는 0들을 더해서 만들 수 있는 숫자임에도 인덱스 범위로 인해 만..
이진탐색
문제 링크 https://www.acmicpc.net/problem/10815 10815번: 숫자 카드 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10, www.acmicpc.net 문제 문제 풀이 처음에 순차탐색으로 풀었더니 시간 초과가 나왔다. 이진탐색으로 코드를 수정하니 답을 맞힐 수 있었다. import sys # 가지고 있는 카드 개수 N = int(sys.stdin.readline()) # 가지고 있는 카드 숫자 cards = list(map(int, sys.stdin.readline().split())) # 검사해야 할 카..
문제 링크 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 문제 풀이 이진 탐색을 통해 풀이를 했다. 입력받은 집의 위치에 대해 먼저 정렬을 진행하고, 이진 탐색에 대한 끝점을 제일 긴 거리로 처음에 두어 이진탐색을 진행한다. 변수 current는 공유기를 둔 위치를 나타낸다. import sys N, C = map(int, sys.stdin.readline().split()) house..
이진탐색 : 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터 찾는 과정 순차 탐색 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서 수행된다. # 순차 탐색 소스코드 # 순차 탐색 소스코드 구현 def sequential_search(n, target, array): # 각 원소를 하나씩 확인하며 for i in range(n): ..
