[파이썬 알고리즘 문제풀이 입문] 이분탐색(결정알고리즘) & 그리디 알고리즘 - 이분검색

*문제 본문은 강의 내용과 관련되어 있어 자세하게 적지 않았습니다.

 

 

 

문제

임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.

 

 

 

풀이

• 답안 : Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()

left = 0
right = N-1

while lt<=rt:
    mid = (left+right)//2
    
    if nums[mid] == M:
        print(mid+1)
        break
    elif nums[mid] > M:
        right = mid-1
    else:
        left = mid+1

• 답안 : Kotlin (내가 바꿔본 것 / 정확X)

import java.io.*
import java.util.*

fun main(args: Array<String>) = with(BufferedReader(InputStreamReader(System.`in`))){
    val (N, M) = readLine().split(" ").map { it.toInt() }
    var nums = readLine().split(" ").map { it.toInt() }.sorted()
    
    var left = 0
    var right = N-1

    while(lt<=rt) {
        var mid = (left+right)/2

        if(nums[mid] == M) {
            println(mid+1)
            break
        } else if(nums[mid] > M) {
            right = mid-1
        } else {
            left = mid+1
        }
    }
}

- 이분탐색만 아니라면 index()로 쉽게 풀었을테지만, 정렬을 굳이 한 이유가 있을 것 같다는 생각이 들어 index()로 문제를 풀지 않았다.

- 이분탐색 (= 결정 알고리즘)

   : 정렬되어 있는 리스트에서 절반씩 크기를 줄여가며 답을 탐색하는 방법

   : 변수 세 개(left, right, mid)가 필요한 방법이다. (변수 이름은 짓기 나름이라.. start, end, mid 로 해도 된다.)

   : mid값과 데이터를 반복적으로 비교하면서 찾는 방법이다.