이분탐색3 [백준 1300번] K번째 수 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net N의 최대 크기가 10만이므로, 배열에 들어갈 모든 수를 계산하기에도 벅찹니다 (10만 x 10만 번의 연산). 따라서 이 문제는 모든 숫자를 계산하지 않고 풀 수 있어야 합니다. K번째 수를 구한다는 것은, 이보다 작은 수가 K-1개 존재한다는 뜻입니다. 이러한 상황에서 비교 연산을 훨씬 덜 하면서 원하는 수를 탐색하는 방법 중 하.. 2021. 9. 17. [프로그래머스] 가사 검색 출처: 2020 KAKAO Blind Recruitment 문제 링크: programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 문제에 대한 자세한 내용은 링크를 통해 직접 확인하시기 바랍니다. 이분 탐색 문제를 풀던 중 나온, 카카오 기출문제들이 으레 그렇듯 꽤 난이도 있는 문제입니다. 정확히는 정석대로 이분 탐색을 구현하는 것이 아닌, lower_bound와 upper_bound 함수를 이용하여 구현하는 방식입니다. 문제를 접근한 순서는 다음과 같습니다. 각 단어를 길이에 따라 나눈다. 각 단어 길이 배열을 알파벳 순서로 정렬한다. 이진 탐색을 통해 쿼리의 단어로 시작하는 마지막 단어와 첫 단어의 인덱스를 구.. 2021. 3. 8. [백준 2110번] 공유기 설치 난이도: 실버 1 문제 링크: 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 이분 탐색을 이용하는 문제 중 꽤 애를 먹은 문제입니다. 어느 부분에서 이분 탐색을 이용해야 하는지 고민을 많이 했는데, 다른 블로그 (링크)의 글을 참고하여 알고리즘을 이해했습니다. 문제의 접근 순서는 다음과 같습니다. 주어진 집들의 좌표를 오름차순으로 정렬한다 (이분 탐색의 기본 조건). 집들 사이의 거리를 초기화한다. 최솟값.. 2021. 3. 8. 이전 1 다음
