프로그래민👨‍💻

이분탐색을 활용하는 문제였다. 맨처음 문제를 접하였을 때 부술수 있는 바위를 고르는 방법을 우선적으로 생각했는데, 바위의 갯수가 50,000이기 때문에 50000C2 라는 조합을 한다면 시간초과가 날것이라고 생각했다. 그래서 다른 바위말고 distance를 기준으로 문제를 접근해보았고 distance가 1,000,000,000으로 주어졌기 때문에 시간복잡도가 효율적인 이분탐색을 사용해보았다. low값을 바위사이의 최소 거리인 1, 그리고 high값을 바위 사이의 최대거리인 distance로 두고, 이분탐색을 돌면서 mid 값보다 크거나 같도록 바위를 배열하게 된다면 몇개의 바위를 부숴야 하는지 확인하고, 바위를 부술 수 있는 최대값 n 과 비교하여 바위 사이의 최대 간격을 찾는 방법으로 문제를 해결해보았..

lowerBound와 upperBound를 활용하여 풀 수있는 문제였다. 총의 사정거리 L에대해 사대의 위치 와 동물의 위치 x,y에 대해 다음과 같은 공식이 문제에 주어져있다. | 사대 - x | + y

이분탐색을 이용한 문제였다. 집 좌표의 범위가 10억 그리고 최대 값을 구하는 문제여서 이분탐색으로 접근할 수 있었다. 우선 첫번째 집에 공유기를 설치한 것을 가정한 후 이분탐색을 이용해 설치길이를 정하여 다음집에 설치할 수 있는지 없는지 여부를 확인하며 답을 찾아갔다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 package algosutdy1; import java.io.BufferedReader; import java.io.InputS..

2020 카카오 인턴 3번 문제였다. 이 문제를 맨처음 봤을 때 배열 크기 N의 범위때문에 어떻게 접근할까 고민을 하였다. 최대 100000이기 때문에 2중 포문만 되어도 시간초과가 발생하기에 이분탐색을 떠올렸다. 이분 탐색을 이용하여 문제를 풀었을 때 기본 테스트 케이스는 통과하였지만 효율성검증에 있어 탈락을 하였다. 그래서 이분 탐색 후 checking하는 과정에서 배열에서의 고정길이 탐색을 효율적으로 할 수 있는 슬라이딩 윈도우 알고리즘을 사용하였다. 이 문제는 배열에서의 조건을 만족하는 최소길이를 찾는 문제이므로 크게 두가지 방법을 사용할 수 있다. 첫째로, 길이를 이분탐색으로 구하고, 그 고정길이를 이용하여 슬라이딩 윈도우를 사용하는 방법이 있다. 두번째로, 고정길이의 탐색이 아닌 가변길이 탐색..

이분 탐색을 사용하는 문제이다. 최소값을 찾는것에 이분탐색을 사용하는것이 좋을것이라 생각했는데, 이분탐색의 다음조건을 넘어가는 check함수를 구현함에 있어서 고민을 많이했다. 맨처음엔 단순하게 arr를 M개로 쪼개는 모든 경우의 수를 생각하였는데, N이 최대 100,000이여서 최악의 경우 이분탐색을 사용하더라도 check함수로 인한 시간초과가 발생할 수 있다고 생각하였다. 그래서 단순하게 현재검증해야하는 값(mid)으로 arr를 나눈다면 몇조각이 나오는지 확인하였고, 그것을 M과 비교하여 M이하면 참, 초과면 거짓을 반환하는 check함수를 만들어 사용하였다. 이 check함수에선 또 하나 체크해야 할 것이 있는데 만일 mid값이 arr의 원소보다 작다면 무조건 거짓을 반환하는 조건을 추가하는 것이다..

이분탐색을 사용하여 최소값을 탐색하는 문제였다. 이 문제를 접근할때 이분탐색을 접근한이유가 있다. 문제의 조건에 의해 나올수 있는 최대시간은 1,000,000,000명 * 1,000,000,000분 임으로 1중 for문으로 돌릴 수 있는 1억이 그냥 넘어가게 되어, 자연스럽게 최적을 찾을 수 있는 이분탐색을 사용해보았다. 문제에서 조심해야 할 것이 있는데 파라미터로는 int형이 들어오고 리턴형은 long형이기에 이것을 처리해주지 않으면 테스트케이스를 해결하지 못한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 package programmers;..

정확성과 효율성을 같이 보는 문제이다. 이 문제를 요구조건 그대로 구현한다면 어렵지 않게 풀수있고, 정확성부분에선 전부다 맞칠 수 있다. 하지만 효율성 부분에 있어선 시간초과가 나기 쉽다. 이 문제 같은 경우는 효율성을 위해선 알고리즘 기법을 사용해야하는데 나는 파라메트릭 서치 를 사용하였다. 파라메트릭 서치란 다음과 같다. 파라메트릭 서치 : 최적화 문제를 결정 문제로 바꾸어 푸는 것. left, right, mid 값을 사용하여 특정값을 찾는 이분탐색과 상당히 유사하며 logN의 시간복잡도를 가짐. 이분 탐색과의 차이점은 결정문제인지 아닌지의 차이. 문제로 다시 돌아가서 제한사항을 본다면 지나가는 친구들의 수는 무한이라고 주어졌다. 하지만 생각해보면 배열의 최소수인 200,000,000까지 친구들이 ..