안녕하세요! 오늘은 자바 알고리즘 문제 중 하나인 “원하는 정수 찾기”에 대해 알아보겠습니다. 이 문제는 다양한 상황에서 응용될 수 있는 기본적인 탐색 알고리즘을 이해하는 데 도움을 줄 것입니다. 여러분의 코딩 실력을 한 단계 끌어올리는 데 이 글이 기여할 수 있기를 바랍니다.
문제 설명
주어진 정수 배열 nums와 찾고자 하는 정수 target가 있을 때, 배열에서 target이 존재하는지 확인하고, 존재한다면 해당 수의 인덱스를 반환하는 문제입니다. 만약 존재하지 않는다면 -1을 반환해야 합니다.
입력
nums: 정수 배열 (예: [2, 7, 11, 15])target: 찾고자 하는 정수 (예: 9)
출력
- 정수 배열에서
target의 인덱스, 존재하지 않을 경우 -1
예시
nums = [2, 7, 11, 15], target = 9출력:
0
nums = [1, 2, 3, 4, 5], target = 6출력:
-1
문제 해결 접근법
이 문제를 해결하기 위한 접근법은 여러 가지가 있지만, 가장 기본적인 방법은 배열을 순회하여 target 요소를 찾는 것입니다. 하지만 이 방법은 시간복잡도가 O(n)이고, 또한 요소가 정렬되어 있지 않은 경우에는 Binary Search(이진 탐색)를 사용할 수 없습니다. 그렇다면 배열이 정렬되어 있다면 어떻게 할까요? 이때는 이진 탐색을 활용할 수 있습니다.
이진 탐색 개념
이진 탐색은 정렬된 배열에서 원하는 값을 찾는 효율적인 알고리즘입니다. 다음은 이진 탐색의 기본 과정입니다:
- 배열의 중간 인덱스를 계산합니다.
- 중간 값이
target이면 해당 인덱스를 반환합니다. target이 중간 값보다 작으면 배열의 왼쪽 절반을 탐색하고, 크면 오른쪽 절반을 탐색합니다.- 이 과정을 반복합니다.
자바 구현
이제 자바로 이진 탐색을 구현해 보겠습니다. 아래는 해당 알고리즘을 코드로 나타낸 것입니다.
public class Solution {
public int search(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
return mid; // target을 찾음
} else if (nums[mid] < target) {
left = mid + 1; // 오른쪽 절반을 탐색
} else {
right = mid - 1; // 왼쪽 절반을 탐색
}
}
return -1; // 찾지 못함
}
}
코드 설명
위의 코드에서 search 메서드는 두 개의 인자를 받습니다: nums 배열과 target입니다. 메서드는 다음과 같은 과정을 수행합니다:
left와right변수를 사용해 탐색할 범위를 관리합니다.- 메인 루프에서는
left가right보다 작거나 같은 동안 계속 탐색합니다. - 중간 인덱스
mid를 계산하고, 중간 값이target과 같으면 해당 인덱스를 반환합니다. - 중간 값이
target보다 작으면 왼쪽 범위를 조정하고, 더 크면 오른쪽 범위를 조정합니다. - 모든 탐색이 끝나도
target을 찾지 못하면 -1을 반환합니다.
복잡도 분석
이진 탐색 알고리즘의 시간 복잡도는 O(log n)입니다. 이는 배열의 크기가 두 배로 증가할 때마다 탐색해야 할 구간이 절반으로 줄어들기 때문입니다. 이 알고리즘은 매우 빠르며, 특히 큰 배열에서 그 효율성이 두드러집니다. 공간 복잡도는 O(1)로 추가적인 공간이 필요하지 않습니다.
결론
이번 글에서는 원하는 정수를 찾는 자바 알고리즘 문제를 다루었습니다. 이 문제를 통해 배열 탐색의 기초인 이진 탐색을 이해하고 구현할 수 있었습니다. 이진 탐색은 코딩테스트에서 자주 출제되는 주제이므로, 충분히 연습하시기를 추천드립니다. 다양한 케이스에 대해 자신만의 코드를 작성해볼까요?
마지막으로, 여러분의 코딩 능력을 향상시키기 위해 문제를 더 풀어보는 것을 잊지 마세요! 궁금한 점이 있다면 언제든지 댓글로 질문해 주세요. 감사합니다!