binary search
-
BOJ) 선분 위의 점알고리즘/백준 2020. 8. 28. 02:01
선분 위의 점 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 풀이 2달 전에 이 문제를 풀다가 계속 시간초과랑 오답이 번갈아 뜨면서 포기했던 문제였다. 오늘도 풀면서 3번이나 틀렸지만 결국 풀어냈다..!! 우선, 문제의 조건에 따라 각 점들은 int형으로 주어지고, 선분의 left, right 범위는 long 타입으로 주어진다. 그리고 완전탐색을 하게되면 가지치기를 엄청나게 잘하지 않는 이상은 시간초과가 뜬다고 생각했다. 그래서 binary search를 이용했다. 점들의 배열을 오..
-
BOJ) 수 찾기알고리즘/백준 2020. 8. 26. 15:31
수 찾기 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 풀이 binary search인 것을 몰랐으면, 아마 시간 초과가 뜨고 나서야 시도했을 것 같다. 하지만, binary search라는 것을 알고 문제를 풀 때는 어렵지 않은 문제다. binary search에서 가장 중요한 것은 여러번 언급했듯, 기준점이다. 이 문제에서는 기준점이 명확하게 특정 숫자다. 특정 숫자를 담고있는 배열의 index를 찾는 문제라고 생각하면되겠다. 기준이 되는 배열은 Arrays...
-
BOJ) 달팽이는 올라가고 싶다알고리즘/백준 2020. 7. 26. 17:27
달팽이는 올라가고 싶다 2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 �� www.acmicpc.net 풀이 달팽이가 막대의 높이 V까지 올라가는 데, 걸리는 날을 구하는 문제다. A는 달팽이가 낮에 올라갈 수 있는 높이이고, B는 밤에 잠을 자는 동안 아래로 미끄러지는 높이다. 정상에 올라간 후에는 미끄러지지 않는다. 위의 조건으로 미루어 봤을 때, 막대까지 오르는 날 * A 만큼 위로 올라가고, (막대까지 오르는 날 -1) * B 만큼 아래로 미끄러진다. 잠을 자는 동안만 미끄러지고, 높이까지 올랐을 때는 미끄러지지 ..
-
BOJ) 랜선 자르기알고리즘/백준 2020. 6. 24. 16:50
랜선 자르기 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 풀이 문제를 접했을 때 이분 탐색이라는 느낌이 강하게 들었는데, N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다는 조건이 있어서 이분탐색으로 푸는 것이라고 확신을 느꼈다. 랜선의 길이가 2^31 -1인 것에 대수롭지않게, int의 최대값이겠거니 하고 int형으로 모든 코드를 짰다. 하지만, 틀렸다고 뜨길래 설마하면서 int형의 최대 값을 찍어봤더니 80정도 차이가 났다.. 2^31 -1은 int가 아닌 long형이..
-
알고리즘) 프로그래머스 BinarySearch, 징검다리알고리즘/프로그래머스 고득점 Kit 2020. 4. 25. 15:35
프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색) 징검다리 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이분 검색에서 mid값은 문제에서 요구하는 답으로 설정하는 것이 기본이다. 이 문제에서 원하는 답은 n개의 바위를 제거한 뒤 각 지점 사이의 거리의 최솟값이다. 따라서 left와 right, mid는 거리로 설정한다. 1. 돌위치를 돌면서 이전 돌과 거리를 비교한다. 2. 구한 거리가 가정 답안인 mid보다 작으면 최솟값이 mid가 될 수 없으므로 돌을 제거해준다. (counting을 해줌) 3. 거리가 크거나 같다..
-
알고리즘) 프로그래머스 BinarySearch, 입국심사알고리즘/프로그래머스 고득점 Kit 2020. 4. 24. 00:37
프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색) 입국심사 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이분 검색에 대한 이해가 완전히 되지 않아서 다른 분들의 로직을 보고, '아! 이렇게 하는거였지' 느꼈다.. 갈길이 아직도 멀다... 제한사항 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.심사관은 1명 이상 100,000명 이하입니다. 제한사항을 따로 적은 이유는 주로 데이터 타입과 대략적인 ..
-
알고리즘) 프로그래머스 BinarySearch, 예산알고리즘/프로그래머스 고득점 Kit 2020. 4. 24. 00:06
프로그래머스 고득점 Kit - Binary Search(이분 검색, 이진 검색) 예산 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr (2020.04.24) 풀이1 이진 탐색(Binary Search)라는 생각없이 푼 풀이다. 사실 문제를 보고 이진 탐색을 써야지!! 이런 느낌이 안들어서 자연스럽게 푼 문제다. 로직은 아주 간단하다. 1. 예산의 액수에 따라 오름차순으로 도시를 정렬해준다. 2. 남은 예산으로 평균을 구했을 때 해당 도시의 예산 요청액이 더 적으면 허가해준다. 3. 만약, 요청한 예산이 남은 예산을 나눠줄 수 있는 금액보다 크다면 남은 총액..