배열(array)은 프로그래밍에서 가장 기본적이고 유용한 자료 구조 중 하나입니다. 배열을 잘 다루는 것은 알고리즘 문제를 효과적으로 해결하는 데 필수적입니다. 이번 블로그에서는 배열을 이용하여 자주 나오는 알고리즘 문제들을 해결하는 방법을 알아보겠습니다.

1. 두 수의 합

먼저, “두 수의 합”이라는 간단한 알고리즘 문제를 풀어보겠습니다. 주어진 정수 배열에서 두 수를 더하여 특정한 합을 만들 수 있는지 찾는 문제입니다.

문제 설명

주어진 배열 nums와 정수 target이 주어질 때, nums 안의 두 숫자를 더해 target을 만들 수 있는 인덱스를 찾아 반환합니다.

코드 예시

def two_sum(nums, target):
    num_dict = {}
    for i, num in enumerate(nums):
        if target - num in num_dict:
            return [num_dict[target - num], i]
        num_dict[num] = i
    return []

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n)입니다. 배열을 한 번 순회하면서 각 숫자의 인덱스를 딕셔너리에 저장하고, 두 숫자의 합이 target이 되는지 확인합니다.

2. 빗물 트래핑

다음으로, “빗물 트래핑”이라는 알고리즘 문제를 살펴보겠습니다. 주어진 높이 맵을 가지고 형성되는 빗물의 양을 구하는 문제입니다.

문제 설명

주어진 높이 배열 height를 가지고 형성되는 빗물의 양을 계산합니다.

코드 예시

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0;
        int result = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    result += leftMax - height[left];
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    result += rightMax - height[right];
                }
                right--;
            }
        }
        
        return result;
    }
}

시간 복잡도

이 알고리즘의 시간 복잡도는 O(n)입니다. 높이 배열을 한 번 순회하면서 빗물의 양을 계산합니다.

마무리

배열을 다루는 알고리즘 문제들은 다양한 유형과 난이도를 가지고 있지만, 핵심은 배열의 각 요소들을 효율적으로 순회하고 관리하는 것입니다. 배열 관련 알고리즘 문제를 풀며 이러한 기본적인 스킬을 익히면 다양한 문제에 대해 보다 효율적으로 대응할 수 있습니다.

배열을 다루는 다른 알고리즘 문제나 해결 방법에 대해 더 알고 싶다면, LeetCode나 Baekjoon Online Judge와 같은 온라인 저지(Online Judge) 플랫폼을 통해 더 많은 연습과 학습이 가능합니다.