C언어, 파이썬 이진탐색에 관하여 (샘플문제, 수도코드)

문제는 다음과 같습니다.

N * N 행렬이 있습니다. 각각의 행과 열은 오름차순으로 구성되어 있습니다.

그리고 정수 k가 주어집니다. 행렬 내에서 이 k의 위치를 구하는 것이 알고리즘의 목표입니다.

만약 k가 2개 이상일 시, k의 위치는 두개의 위치 중 하나의 위치를 랜덤하게 출력합니다.



첫번째 입력으로는 행렬이 들어옵니다.

두번째 입력으로는 정수 k의 값이 들어갑니다.

그리고 output은 (행,열) : position of ‘입력받은 정수‘ 입니다.

input과 output은 다음과 앝이 입력되어집니다.


이 알고리즘 문제의 풀이과정과 수도코드를 알려주시면 진심으로 감사드립니다.
------------------------------------------------

이 문제를 효율적으로 해결하려면

이진 검색(binary search)

을 사용할 수 있습니다.

다음은 행렬에서 정수 k의 위치를 찾는 알고리즘의 풀이 및 수도코드입니다.

알고리즘:

1. 행렬의 왼쪽 상단(0, 0)에서 시작합니다.
2. 현재 위치의 값이 k와 같다면, 해당 위치를 반환합니다.
3. 현재 위치의 값이 k보다 작다면, 오른쪽으로 이동합니다.
4. 현재 위치의 값이 k보다 크다면, 위로 이동합니다.
5. 행렬의 경계를 벗어나면, k가 행렬에 없는 것으로 판단하고 위치를 반환하지 않습니다.

수도코드:

function find_position(matrix, k):
    if matrix is empty or matrix[0] is empty:
        return None

    row, col = 0, len(matrix[0]) - 1
    while row < len(matrix) and col >= 0:
        if matrix[row][col] == k:
            return (row, col)
        elif matrix[row][col] < k:
            row += 1
        else:
            col -= 1

    return None

예시:

matrix = [
    [1, 3, 5, 7],
    [2, 4, 8, 9],
    [3, 5, 9, 11],
    [6, 8, 10, 12]
]

k = 8

result = find_position(matrix, k)
if result:
    print(f"(행, 열) : position of {k} is {result}")
else:
    print(f"{k} is not in the matrix")

이 알고리즘의 시간 복잡도는 최악의 경우 O(N)입니다.