개요
컴퓨터 공학에 입문하게 되면 알고리즘에 대해 한 번쯤은 학습하게 되며, 이러한 알고리즘엔 많은 종류가 있습니다. 자료구조의 종류로는 스택, 큐, 힙, 정렬, 탐색 등이 있고 알고리즘 패러다임으로는 동적 계획, 분할 정복, 분기 한정 등이 있습니다.
하지만 알고리즘에 대해서는 많이 알고 있지만, 정작 이러한 알고리즘을 코딩에 어떻게 적용하는지 모르는 경우가 많습니다(저 포함). 따라서 이번 포스팅에서 알고리즘을 코테에 적용하는 실습을 해보고자 합니다.
적용
문제
예시로 간단한 문제를 다뤄보고자 합니다.
주어진 정수 배열 arr과 목표값 k가 주어졌을 때,
arr 내에서 두 수의 합이 k가 되는 쌍이 존재하면 true를, 없으면 false를 반환하라.
구현 방법 1
해당 문제를 구현하는 방법에는 여러 가지가 있습니다. 가장 간단하고 직관적인 방법으로는 완전 탐색으로 이중 for문을 사용하여 k가 되는 두 수를 찾는 방법이 있습니다.
public class TwoSumBruteForce {
public static boolean hasTwoSum(int[] arr, int k) {
int n = arr.length;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (arr[i] + arr[j] == k) {
return true;
}
}
}
return false;
}
}
이 경우 이중 for문을 사용했기 때문에 n x n 이 되어 시간복잡도는 아래와 같습니다.
구현 방법 2
또 다른 방법으로는 정렬 알고리즘을 활용하는 방법이 있습니다. 처음 주어진 배열을 정렬한 후, 작은 순서대로 인덱스들을 더하여 합이 k가 되는 두 수를 찾습니다.
import java.util.Arrays;
public class TwoSumSorted {
public static boolean hasTwoSum(int[] arr, int k) {
Arrays.sort(arr); // O(n log n)
int left = 0, right = arr.length - 1;
while (left < right) {
int sum = arr[left] + arr[right];
if (sum == k) {
return true;
} else if (sum < k) {
left++;
} else {
right--;
}
}
return false;
}
}
이 경우 이중 루프를 사용하지 않고 정렬 메서드만을 사용했기 때문에 시간복잡도는 아래와 같습니다.
분석 및 결론
두 가지 방법 모두 문제에서 요구한 결과를 도출해내는 코드이기 때문에 정답이라고 할 수 있지만, 시간복잡도 차원에서 비교해봤을 때 주어진 n 값의 크기가 커질수록 상대적으로 시간복잡도 n log n의 값이 낮기 때문에 정렬 알고리즘을 활용한 코드가 더 효율적이라고 할 수 있습니다.
하지만 시간복잡도가 낮다고 해서 무조건 옳은 코드인 것은 아닙니다. 다만, 문제에서 요구한 내용을 구현하기에 앞서 어떤 알고리즘을 사용하는 것이 가장 적합한지 미리 구상을 하고 구현하는 것이 중요합니다. 최근 코테 문제들에서는 테스트 케이스가 여러 가지 주어지면서 n값의 크기가 매우 큰 경우가 테스트케이스로 주어지는 경우도 있고, 코드 에러 검사와 별개로 효율성 검사로 시간 복잡도를 측정하는 경우도 있습니다. 또한 대놓고 특정 알고리즘과 자료구조를 묻는 문제도 많습니다.
따라서 여러 가지 자료구조와 알고리즘을 학습하고 그것을 코드로 구현하는 연습을 많이 해야 합니다. 그래야 문제의 조건과 입력 범위를 파악하고, 그에 가장 적합한 방법을 선택하여 문제의 요구사항에 맞는 코드를 작성할 수 있습니다.
