이분탐색

이분탐색 문제이다. 이번문제는 이분탐색인걸 모르는채로 풀었는데 문제를 읽자마자 이거 이분탐색이잖아? 라는 생각이 들었다. 내가 그래도 연습을 하긴했구나 싶어서 뿌듯했다. 항상 느끼는 거지만 이분탐색문제는 어떤 값을 찾을 것인가? 그 값이 내가 원하는 값인지 어떻게 검증할 것인가가 가장 중요하고 어려운것 같다. 이 문제에서는 몇 센티미터로 잘랐을 때 원하는 갯수만큼 가장 길게 줄 수 있냐고 묻는 문제이다. 즉, 몇 센티미터인가를 우리가 찾는 값으로 이 값을 기준으로 자르면 몇개를 만들 수 있냐를 통해 검색을 해나갈 수 있다. 이를 코드로 나타내면, 이렇게 된다. 이전에 풀었던 이분탐색문제들보다는 쉬웠던 문제인것 같다.

이분 탐색 문제이다. 이 문제는 총 M대의 놀이기구가 있을 때, N명이 순서대로 놀이기구를 탈 때, 마지막 사람이 타게 되는 놀이기구의 인덱스를 맞추는 문제이다. 문제를 봤을 때, 프로그래머스의 입국심사와 비슷한 느낌이 있었지만, 차이점이 있다고 느꼈고 나는 입국심사를 푼 테크닉을 바탕으로 약간의 아이디어를 추가하여 이문제를 풀었다. 이문제는 N명의 사람은 빈 놀이기구에 순서대로 들어가고, 각 놀이기구 마다 소요되는 시간이 다르다. 여기서 조심해야 할 점은 입국심사와는 다르게 사람들이 최소 시간을 위해 놀이기구 선택을 하는 것이 아닌, 여러 개가 비어있다면 단순히 인덱스가 작은 놀이기구부터 탄다는 점이다. 내가 문제를 푼 아이디어는 아래와 같다. 1. N-M명을 태울 때는 최소 시간을 위해 놀이기구를 선..

이분 탐색 문제이다. 이 문제는 문제 설명 자체도 간단하지만 더 간략히 정리하자면, N*N크기의 이차원 배열에서 각 값은 row*col의 값을 가질 때(최소 인덱스를 1로 둠) T번째 수의 값을 구하는 것이다. 결국 T번째 수의 값을 이진탐색으로 찾아낼 수 있는 가를 구하는 문제이다. 역시 중간값 검증을 하여, 지금 탐색하고 있는 수가 몇 번째 수인지 찾아내는 것이 문제를 푸는 포인트인 것 같다. 1 2 3 2 4 6 3 6 9 N이 3인 이차원 배열은 이렇게 되고, 마치 구구단과 비슷한 모양이 된다. 이 배열에서 6은 몇번째로 큰 수인지 확인하기 위해서는 어떻게 해야 할까? 1행에서 6보다 작은 수는 3개, 2행에서 6보다 작은 수 역시 3개, 3행에서 6보다 작은 수는 2개로 총 8번째로 큰 수이다...

이분 탐색 문제이다. 이전 문제들과 마찬가지로 중간값 검증을 어떻게 할 것인지, 범위를 어떻게 할지 가장 중요했다. 이분 탐색으로 내가 찾고 싶은 값은 만들어진 구간의 최소 값이다. 즉 중앙값을 기준으로 구간을 만들 때 문제에서 원하는 구간 개수가 가능한지 검증한 후, 더 적게 나온다면 문제에서 원하는 구간 개수를 만들 수 있다는 뜻이므로, 최솟값을 찾기 위해 중간값을 줄이고, 더 많이 나온다면 중간값을 올리는 과정으로 문제를 해결하였다. 다시 정리하자면, 내가 원하는 값(중앙값)으로 구간을 나눌 때 M개 이하로 만들 수 있다면, 내가 정한 값으로 M개의 배열을 만들 수 있다는 것을 확실히 인지하여야 한다. 이를 이용하여 중앙값을 검증할 때, 내가 지정한 중앙값으로 배열의 최소 최대의 최대 차를 만들 수..

아직 각 알고리즘에 대한 이해 및 활용능력이 부족한 것 같아서, 기출에 나온 구현 문제보다는 알고리즘 연습을 할 것 같다. 첫 번째 알고리즘은 바로 이분 탐색이다. 이분 탐색은 학교 예제에서도 다뤄본 적 있는 알고리즘이라 비교적 쉽다고 생각했었는데 최근 프로그래머스 중 이분 탐색 문제(입국심사)를 풀어보고 정말 쉬운 게 없구나 느끼게 됐다. 사실 모든 알고리즘 문제들이 그렇겠지만, 이 문제를 어떤 알고리즘으로 풀지?라는 생각만 잡히게 된다면 어느 정도 쉽게 풀 수 있다. 특히 나는 알고리즘을 연습할 목적으로 백준의 이분 탐색 문제집을 풀었기 때문에 어떤 알고리즘으로 풀지라는 고민의 시간 없이 문제를 풀었기 때문에 그나마 쉽게 풀 수 있었다. 문제에 대해 설명하자면, 총 N개의 강의를 녹화할 때, M장의 ..

이 문제를 처음 본 순간 든 생각은 이게 왜 '이분 탐색'이지? 였다. 다른 방법으로 풀까 했지만 n이 1,000,000,000을 for 문으로 돌릴 자신이 없었기 때문에 결국 다른 풀이들을 레퍼런스 했다. 다른 블로그 글들을 보면서 내가 아직 이분 탐색을 제대로 이해하지못했고, 아직 많이 부족하다는 것을 깨달았다. 우선, 다른 풀이들을 보면서 나 스스로 한번 문제와 이분탐색을 정리해보았다. 이진 탐색은 정렬된 배열에서 내가 원하는 값을 가지고 있는 배열의 인덱스를 찾는 기법이다 즉, 이문제에서 우리가 찾고 싶은 것은 총 소요되는 최소 시간이기 때문에 시간을 인덱스로 생각해야 한다. 시간을 인덱스라고 생각하고 이분 탐색하듯이 LEFT와 RIGHT값을 찾아야 하는데, 시간은 무한하기 때문에 우리가 범위를 ..