이분탐색3 [개념 정리] 이분 탐색 이분 탐색이 뭘까요? 이 글은 큰돌의 터전님의 강의인 10주 완성 C++ 코딩테스트 알고리즘 개념 교안을 참고하여 작성했습니다. 이분 탐색정렬된 배열에서 탐색 범위를 절반씩 줄여가는 방식으로 특정 값을 찾는 알고리즘입니다.이진 탐색이라고도 불리면, 시간 복잡도는 O(log N)이 걸립니다. 주로 크기가 큰 배열에서 어떠한 값을 찾아야하는 경우에 해당 배열을 정렬하고 이분 탐색을 사용하면, O(logN)의 시간복잡도로 효율적으로 값을 찾을 수 있습니다. 이분 탐색 동작원리1. 가장 왼쪽 인덱스인 left와 가장 오른쪽 인덱스인 right를 설정합니다. 2. (left + right) / 2로 중간값인 mid를 계산합니다. 3. 값을 비교합니다.목표값과 중간값이 같은 경우, 탐색을 종료하고 mid를 반환합.. 2025. 3. 10. [프로그래머스] Lv3 선입 선출 문제 풀이 방법 문제에선 마지막 작업을 처리하는 코어의 번호를 return하라고 합니다.마지막 작업을 처리하는 코어번호를 알기 위해선 이 작업들을 전부 완료했을때, 언제 끝나는지 알아야 합니다.즉, 이 작업들을 끝낼 수 있는 최소 시간을 먼저 찾아야 합니다. 처음엔 우선순위큐를 사용해서 문제를 풀었지만 효율성 처리 부분에서 시간초과가 떴습니다."작업들을 끝낼 수 있는 최소 시간"을 찾아야 하기 때문에 효율적으로 탐색할 수 있는 방법인 이분 탐색을 통해 최소 시간을 찾아줍니다. 잠깐! 이분 탐색을 사용하려면 정렬을 하고 탐색을 해야하지 않나요? 이분 탐색을 하기 전에 정렬을 하고 찾는 것은 맞는 말이지만, 이 문제에서 찾고자 하는 값은 최소 시간입니다.최소 시간을 찾는 시간의 범위 자체는 이미 정렬이 되어.. 2025. 2. 19. [프로그래머스] Lv4 징검다리 접근 방식문제에서 바위 n개를 제거했을 때, 각 바위 사이의 거리가 최소인 값들 중 최댓값을 구하라고 합니다.즉, 각 바위 사이의 거리가 최소인 값들에 대해 알아야 합니다. 어떻게 각 바위 사이의 거리가 최소인 값을 알 수 있을까요? (1) 브루트 포스맨처음 제가 생각했던 방식은 단순한 조합을 사용해서 n개의 조합을 전부 확인해 바위 사이의 거리가 최소인 값을 하나의 리스트에 담아 정렬을 한 후, 제일 큰 값을 도출해야겠다고 생각했습니다. 문제에서 주어진 조건은 아래와 같습니다. 바위의 갯수가 최대 50,000개 이므로 제거할 바위의 조합의 시간복잡도는 50,000Cn이 됩니다.최악의 경우 O(50,000^n) 에 가깝게 증가합니다. n이 2만되도 시간 초과가 발생할 것 같아서 스킵합니다. (2) 투포.. 2025. 2. 17. 이전 1 다음
