서론
코딩테스트는 현대의 프로그래머가 필수적으로 겪게 되는 과정입니다. 그 중에서도 시간 복잡도를 이해하고 활용하는 것은 매우 중요합니다. 이 글에서는 자바를 사용하여 알고리즘 문제를 해결하는 방법과 함께, 시간 복잡도를 분석하는 방법을 자세히 설명합니다.
문제 설명
주어진 정수 배열 nums와 정수 target가 있습니다. 배열의 두 수를 합쳐 target이 되도록 하는 인덱스 쌍을 찾는 문제입니다. 만약 없다면 -1, -1을 반환합니다.
문제 요구 사항
- 1 ≤ nums.length ≤ 104
- -109 ≤ nums[i] ≤ 109
- -109 ≤ target ≤ 109
- 하나의 정답만 존재한다고 가정합니다.
예제
Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]
Explanation: nums[0] + nums[1] = 2 + 7 = 9, 따라서 [0, 1]을 반환합니다.
해결 접근법
이 문제를 해결하는 방법은 두 가지로 나눌 수 있습니다. 첫 번째는 이중 반복문을 사용하는 방법이고, 두 번째는 해시맵을 활용하는 방법입니다. 각 방법의 시간 복잡도를 분석하고 우선 해시맵을 사용하는 방법으로 구현하겠습니다.
방법 1: 이중 반복문
이 방법은 배열의 모든 쌍을 검토하여 합이 target과 같은지 확인합니다. 코드 구현은 다음과 같습니다:
public int[] twoSum(int[] nums, int target) {
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{-1, -1};
}시간 복잡도 분석
이중 반복문에서는 각 요소에 대해 모든 다른 요소를 검사합니다. 따라서 시간 복잡도는 O(n^2)입니다. 이는 최악의 경우에 비효율적일 수 있습니다.
방법 2: 해시맵 사용하기
시간 복잡도를 줄이기 위해 해시맵을 사용하여 이번 문제를 해결할 수 있습니다. 이 방법은 각 요소의 인덱스를 저장하고, 현재 요소에 대해 target - nums[i]의 값을 키로 검토하여 존재하는 경우 인덱스를 반환합니다.
import java.util.HashMap;
public int[] twoSum(int[] nums, int target) {
HashMap map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
} 시간 복잡도 분석
이 방법의 시간 복잡도는 O(n)입니다. 각 요소를 한 번만 검사하면 되기 때문에 효율적입니다. 해시맵의 삽입과 검색은 상수 시간에 수행되므로, 이 접근법이 우수합니다.
복잡도 분석 및 결론
이 문제를 통해 시간 복잡도의 중요성을 알 수 있었습니다. 이중 반복문을 사용하는 방법은 간단하지만 성능이 저하될 수 있으므로, 실무에서는 해시맵과 같은 데이터 구조를 활용하여 최적화하는 것이 필요합니다.
추가적인 팁
- 문제를 처음 접했을 때는 다양한 접근 방식을 생각해보세요. 이중 반복문에서 해시맵으로의 전환은 시간 복잡도를 많이 줄일 수 있습니다.
- 주어진 데이터 구조나 알고리즘이 문제 해결에 적합한지 항상 검토하세요.
- 시간 복잡도를 계산할 때는 최악의 경우를 항상 고려하세요. 최선의 경우와 평균적인 경우도 고려하면 좋습니다.
마무리
이번 글에서는 자바를 이용한 코딩 문제 해결을 통해 시간 복잡도의 중요성을 강조했습니다. 알고리즘 문제를 해결하는 과정에서 최적의 접근 방법을 고르는 것이 얼마나 중요한지 확인할 수 있었습니다. 다음 시간에는 다른 알고리즘 문제를 통해 더 많은 팁과 트릭을 알아보겠습니다.