이분탐색 3

[Level 4 프로그래머스] 카카오 기출, 2020 KAKAO BLIND RECRUITMENT - 가사 검색(Python)

programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 트라이(Trie) 자료형을 사용하여 풀 수도 있지만, 이분탐색을 사용해서 풀어보았다. 이분탐색은 따로 구현하지 않고 Python의 bisect 라이브러리를 활용하였다. 문제 해결 2개의 배열을 사용한다. 각각 주어진 단어, 단어의 순서를 반대로 한 단어를 리스트에 추가한다. 예를들면 "frodo"라는 단어를 "frodo"와 "odorf"로 나누어 각각의 배열에 담는다. 단어의 순서를 바꾸는 것은 word[::-1] 을 하여 append 하면 거꾸로 담긴다 각 배열을 이분탐색을 하기 위해 정렬한다. queries가 접미사인지, 접두사인지 구분하고 그에 맞게 ..

[BOJ 백준] 12757번 : 전설의 JBNU

www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net map과 이분탐색을 활용해서 조건에 맞게 푸는 문제이다. 8번의 시도 끝에 풀었다. 문제 해결 문제를 읽어보면 다음과 같은 조건이 있다. 1 Key Value : 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다. 2 Key Value : 해당 Key로 검색된 데이터를 Va..

[BOJ 백준] 1477 - 휴게소 세우기

https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. N은 100보다 작거나 같으며, M도 100보다 작거나 같다. L은 100보다 크거나 같고, 1000보다 작거나 같다. 모든 휴게소의 위치는 중복되지 않으며, N+M은 L보다 작다. 둘째 줄에, 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 이분탐색을 활용하는 문제였다. 단순히 이분탐색 뿐 아니라 파라메트릭 서치를 사용하여야 한다. 물론 이 문제는 N의 값이 작아서, 이분탐색을 활용하지 않아도 된다. 문제는 현재 세워진 휴게소들 사이에 M개의 휴게소를 세우고 휴게소가 없는 구간의 ..