안녕하세요, 여러분! 이번 포스트에서는 퇴사 준비에 도움이 되는 알고리즘 문제를 하나 풀어보도록 하겠습니다. 알고리즘 문제는 코딩 테스트에서 자주 출제되는 유형 중 하나로, 실력을 쌓는 데 필수적입니다. 특히 C#을 이용한 문제 풀이에 집중해서 다루어 보겠습니다.
문제: 배열에서 두 수의 합 찾기
문제 설명: 정수 배열과 특정 정수(target)가 주어졌을 때, 배열 안에서 두 수의 합이 target과 같은 두 수의 인덱스를 찾으세요. 각 입력은 반드시 하나의 정답이 있다고 가정하며, 같은 요소를 두 번 사용할 수 없습니다. 결과는 인덱스 배열로 반환해야 하며, 인덱스는 작은 수부터 정렬하여 반환합니다.
예제:
입력: nums = [2, 7, 11, 15], target = 9
출력: [0, 1] // nums[0] + nums[1] = 2 + 7 = 9
풀이 과정:
본 문제는 다양한 방법으로 접근할 수 있습니다. 하지만 가장 효율적인 방법은 해시맵을 사용하는 것입니다. 해시맵을 사용하면 O(n)의 시간 복잡도로 해결할 수 있습니다. 아래는 단계별로 풀이 과정을 설명합니다.
1단계: 문제 이해하기
우선, 주어진 배열 안에서 두 수의 합이 target인 경우를 찾아야 합니다. 이때 인덱스를 반환해야 하므로, 두 수의 합을 계산할 때 각 숫자의 인덱스도 기억해 두어야 합니다.
2단계: 해시맵 구조 설정하기
C#에서는 Dictionary를 사용하여 해시맵을 구현할 수 있습니다. 이 구조를 통해 중복된 수를 허용하지 않고, 빠르게 값을 찾을 수 있습니다.
3단계: 반복문을 통한 체크
배열을 하나씩 순회하면서, 각 수에 대해 target에서 해당 수를 뺀 값을 찾습니다. 이 값이 해시맵에 존재한다면, 그 두 수의 인덱스를 반환하면 됩니다.
4단계: 코드 구현하기
using System;
using System.Collections.Generic;
public class Solution
{
public int[] TwoSum(int[] nums, int target)
{
Dictionary numDict = new Dictionary();
for (int i = 0; i < nums.Length; i++)
{
int complement = target - nums[i];
if (numDict.ContainsKey(complement))
{
return new int[] { numDict[complement], i };
}
if (!numDict.ContainsKey(nums[i]))
{
numDict[nums[i]] = i;
}
}
throw new ArgumentException("No two sum solution");
}
}
5단계: 코드 설명하기
위 코드는 다음과 같은 방식으로 작동합니다:
- 먼저, Dictionary를 초기화합니다.
- 배열을 순회하면서, 각 수에 대해 complement를 계산합니다.
- complement가 Dictionary에 존재하는 경우, 인덱스를 반환합니다.
- 존재하지 않는 경우, 현재 수와 인덱스를 Dictionary에 저장합니다.
복잡도 분석
시간 복잡도: O(n), 배열을 한 번만 순회하므로.
공간 복잡도: O(n), 최악의 경우 모든 숫자를 Dictionary에 저장해야 하므로.
마무리
이번 문제를 통해 C#에서 효율적인 알고리즘을 구현해 보았습니다. 코딩 테스트에서는 다양한 문제들이 출제되므로 평소에 꾸준히 연습하는 것을 추천드립니다. 퇴사 후에도 실력을 유지하는 것이 중요하니까요!
다음 포스트에서는 다른 유형의 문제를 다루어 보도록 하겠습니다. 기대해 주세요!