알고리즘19 공유기 설치 (이진 탐색) n 개의 집이 수직선으로 존재하고 각 좌표값이 주어질때 c개의 공유기를 최대한 집을 많이 띄워서 설치할때 최대거리는 얼마가 될 수 있는지 묻는 문제입니다. 처음에 문제를 조금 헷갈렸는데, 이진탐색의 기준을 최대거리로 세우고 진행하면 쉽게 풀 수 있습니다. 또한 시작 start 및 end 또한 발생할 수 있는 최소거리 , 발생할수 있는 최대거리여야 하므로 1, nums[n-1]-nums[0]이 되야합니다. (저는 헷갈려서 nums[0], nums[n-1]로 설정해서 한번 틀렸습니다.) n, c = map(int, input().split()) nums = [] for i in range(n): a = int(input()) nums.append(a) nums.sort() def binary_search(n.. 2021. 6. 14. 정렬된 배열에서 특정 수 의 개수 구하기. 정렬이 되어있지 않다면 정렬을 해주고, 만약 정렬이 되어 있따면 이진탐색을 통해 O(log n) 탐색이 가능합니다. 이진 탐색을 통해 해당 수를 탐색하며 target 값과 일치할 때 해당 값이 그 값중에 최대한 왼쪽 인덱스인지 혹은 오른쪽 인덱스인지 확인하면 됩니다. 해당 수가 0 인덱스이거나 현재 값이 target과 동일한데 그 이전 값이 target보다 작은 경우 해당 값중 가장 왼쪽이라 할 수 있습니다. 혹은 오른쪽은 이의 반대로 탐색가능합니다. n, x = map(int, input().split()) nums = list(map(int, input().split())) def find_first(nums,target): start = 0 end = len(nums)-1 while start=ta.. 2021. 6. 14. 알고리즘- KMP 알고리즘, 문자열 검색 KMP를 요약하면 다음과 같습니다. 어떤 수의 접미사와 접두사가 일치하는 경우가 있다면 그것을 기억해서 실패시 스킵(다음 탐색때 시작점으로 삼는다) 한다. 이를 통해서 굉장히 빠른 탐색이 가능합니다. O(N+M) fail함수를 구현하고 이에 따른 KMP함수를 구현합니다. ( 내용은 비슷합니다.) 구현이 익숙치 않아서 해당 부분을 문제를 풀며 좀 연습해봐야할 것 같습니다. https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 2021. 3. 9. 이전 1 2 3 4 5 다음