코딩 테스트는 최근 많은 기업들의 채용 과정에서 중요한 단계로 여겨지고 있습니다. 오늘은 알고리즘 문제 중 하나인 “최솟값 찾기”에 대해 알아보겠습니다.
이 문제는 배열에서 최솟값을 찾는 간단한 문제처럼 보일 수 있지만, 다양한 변형과 최적화 기법을 사용하여 실제로 매우 유용하게 활용될 수 있습니다.
이 강좌를 통해 이론적 배경과 함께 코드 구현 방법을 자세히 살펴보겠습니다.
문제 설명
주어진 정수 배열 arr가 있을 때, 이 배열의 최솟값을 찾아 반환하는 함수를 작성하시오.
배열의 크기는 1 ≤ len(arr) ≤ 10^6, 배열의 각 원소는 -10^9 ≤ arr[i] ≤ 10^9 범위 내의 정수입니다.
입력
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
출력
1
문제풀이 과정
1. 문제 이해하기
주어진 문제는 배열에서 최솟값을 찾아 반환하는 것입니다. 배열의 원소 개수가 1백만 개까지 가능하므로,
효율적인 알고리즘이 필요합니다. 최솟값을 찾기 위해 여러 접근 방법이 있을 수 있지만,
가장 기본적인 방법부터 시작해 보겠습니다.
2. 알고리즘 설계
최솟값을 찾는 가장 간단한 방법은 배열을 순회하며 각 원소와 현재 최솟값을 비교하는 것입니다.
이 방법은 시간 복잡도가 O(n)이며, 여기서 n은 배열의 요소 개수입니다.
이 방법의 장점은 구현이 매우 간단하고 직관적이라는 것입니다.
그러나 최솟값을 찾는 방법은 다양하므로, 다른 접근 방법도 고려할 수 있습니다.
3. 코드 구현
이제 알고리즘을 Python 코드로 구현해 보겠습니다.
def find_min(arr):
# 배열이 비어있는 경우 예외 처리
if not arr:
return None
# 첫 번째 요소를 최솟값으로 초기화
min_value = arr[0]
# 배열을 순회하며 최솟값 찾기
for num in arr:
if num < min_value:
min_value = num
return min_value
# 예제 사용
arr = [3, 1, 4, 1, 5, 9, 2, 6, 5]
result = find_min(arr)
print(f"최솟값은: {result}")
4. 코드 설명
위 코드에서 find_min 함수는 배열 arr를 입력으로 받아 최솟값을 찾습니다.
먼저 배열이 비어있는 경우를 대비하여 None을 반환하도록 예외 처리를 합니다.
그 다음, 배열의 첫 번째 요소를 최솟값으로 초기화하고, 배열의 모든 요소를 순회하며 현재 최솟값과 비교합니다.
만약 현재 요소가 최솟값보다 작다면, 최솟값을 업데이트합니다.
최종적으로 최솟값을 반환합니다.
5. 시간 복잡도 분석
이 알고리즘의 시간 복잡도는 O(n)입니다.
이는 배열의 모든 요소를 한 번씩 순회해야 하기 때문에 나타나는 복잡도입니다.
적어도 n개의 원소가 존재하는 배열에서는 최솟값을 찾기 위해 모든 원소를 확인해야 하므로,
이보다 더 좋은 시간 복잡도를 갖는 방법은 존재하지 않습니다.
리스트의 최솟값을 찾는 다른 방법들
1. 내장 함수 사용
Python에서는 내장 함수 min()를 사용하여 간단하게 최솟값을 찾을 수 있습니다.
이 경우에도 시간 복잡도는 여전히 O(n)입니다.
result = min(arr)
print(f"최솟값은: {result}")
2. 재귀적 방법
재귀를 사용하여 최솟값을 찾는 방법도 있습니다. 이 방법은 코드가 더 복잡하지만,
동일한 시간 복잡도를 유지합니다. 아래는 간단한 재귀적 접근 방식입니다.
def find_min_recursive(arr, low, high):
# 배열의 한 요소인 경우
if low == high:
return arr[low]
# 배열의 중간 인덱스 계산
mid = (low + high) // 2
# 왼쪽 반과 오른쪽 반에서 각각 최솟값 찾기
left_min = find_min_recursive(arr, low, mid)
right_min = find_min_recursive(arr, mid + 1, high)
return min(left_min, right_min)
# 재귀를 사용한 최솟값 찾기
result = find_min_recursive(arr, 0, len(arr) - 1)
print(f"최솟값은: {result}")
3. 정렬 후 첫 번째 요소 사용
배열을 정렬한 후 최솟값을 찾는 방법도 있습니다. 이 방법은 시간 복잡도가 O(n log n)이며,
따라서 일반적인 최솟값 찾기 방법보다 비효율적입니다. 그러나 정렬이 필요한 다른 작업과 연관되었다면 유용할 수 있습니다.
sorted_arr = sorted(arr)
min_value = sorted_arr[0]
print(f"최솟값은: {min_value}")
문제의 변형
최솟값 찾기 문제는 다양한 변형을 가질 수 있습니다. 예를 들어, 다음과 같은 변형 문제가 있을 수 있습니다.
1. 최솟값의 인덱스 찾기
최솟값뿐만 아니라 최솟값의 인덱스를 반환하도록 문제를 변형할 수 있습니다. 이 경우,
최솟값을 업데이트할 때 해당 인덱스를 기록하면 됩니다.
def find_min_index(arr):
if not arr:
return None, None
min_value = arr[0]
min_index = 0
for i in range(len(arr)):
if arr[i] < min_value:
min_value = arr[i]
min_index = i
return min_value, min_index
# 예제 사용
min_value, min_index = find_min_index(arr)
print(f"최솟값은: {min_value}, 인덱스는: {min_index}")
2. 여러 개의 최솟값 반환
배열에 여러 개의 최솟값이 존재하는 경우, 이들을 모두 반환하는 방법을 고려할 수 있습니다.
이때는 최솟값이 결정된 후 해당 최솟값을 가진 모든 인덱스를 저장해 반환하면 됩니다.
def find_all_min(arr):
if not arr:
return [], None
min_value = arr[0]
min_indices = []
for i in range(len(arr)):
if arr[i] < min_value:
min_value = arr[i]
min_indices = [i] # 최솟값이 바뀌면 새로운 인덱스 기록
elif arr[i] == min_value:
min_indices.append(i) # 동일한 최솟값 추가
return min_indices, min_value
# 예제 사용
min_indices, min_value = find_all_min(arr)
print(f"최솟값은: {min_value}, 인덱스는: {min_indices}")
결론
오늘은 “최솟값 찾기” 문제를 통해 배열 내 최솟값을 찾는 다양한 방법에 대해 알아보았습니다.
기본적인 순회 방법뿐만 아니라 내장 함수, 재귀적 접근, 정렬을 통한 방법과 같은 여러 접근 방식을 다뤘습니다.
또한 문제의 변형을 통해 더욱 복잡한 상황을 해결할 수 있는 방법도 제시하였습니다.
이러한 문제는 코딩 테스트에서 자주 출제되므로, 다양한 접근 방식을 이해하고 연습하는 것이 중요합니다.
연습문제
아래의 연습문제를 풀어보세요.
- 주어진 배열에서 중복된 요소를 제거한 후 최솟값을 찾는 함수를 작성하시오.
- 2차원 배열에서 최솟값을 찾는 함수를 작성하시오.
- 미정렬된 배열에서 k번째 최솟값을 찾는 함수를 작성하시오.