작성자: 조광형
작성일: 2024년 11월 26일
1. 알고리즘 문제 소개
이번 포스트에서는 C++을 사용하여 해결할 수 있는 알고리즘 문제를 하나 살펴보겠습니다. 이 문제를 통해 C++의 기본 문법과 알고리즘 접근 방식을 알아보고, 디버깅 기술을 통해 문제를 해결하는 과정도 경험해 보겠습니다.
문제: 두 수의 합
주어진 정수 배열과 정수 목표값이 있을 때, 배열 내에서 두 수를 선택하여 그 합이 목표값이 되도록 하는 인덱스를 반환하는 문제입니다. 만약 그러한 쌍이 없다면, -1을 반환해야 합니다.
입력 예시:
nums = [2, 7, 11, 15]
target = 9
출력 예시:
[0, 1]
두 수 2와 7의 합이 9이므로 인덱스 0과 1을 반환합니다.
2. 문제 접근 방식
이 문제는 다소 직관적입니다. 중첩 반복문을 이용해 모든 쌍을 검사할 수 있지만, 이 방법은 O(n^2)의 시간 복잡도를 가집니다. 더 나은 방법은 해시맵을 사용하는 것입니다. 각 숫자를 순회하며 해시맵에 저장하면서, 목표값과 현재 숫자의 차이를 검사하는 방식입니다. 이 방법은 O(n)의 시간 복잡도로 해결할 수 있습니다.
3. C++ 코드 구현
이제 이 문제를 C++로 구현해 보겠습니다.
#include
#include
#include
using namespace std;
vector twoSum(vector& nums, int target) {
unordered_map map; // 숫자와 그 인덱스를 저장할 해시맵
vector result;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i]; // 목표값에서 현재 숫자를 뺀 값
if (map.find(complement) != map.end()) { // 탐색
result.push_back(map[complement]);
result.push_back(i);
return result; // 결과 반환
}
map[nums[i]] = i; // 해시맵에 현재 숫자와 인덱스를 저장
}
return {-1}; // 쌍이 없는 경우
}
int main() {
vector nums = {2, 7, 11, 15};
int target = 9;
vector result = twoSum(nums, target);
cout << "[" << result[0] << ", " << result[1] << "]" << endl;
return 0;
}
4. 코드 설명
위의 코드는 먼저 정수 배열 nums와 목표값 target을 입력받습니다. unordered_map을 사용하여 각 숫자와 그 인덱스를 저장하는 해시맵 map을 생성합니다. 그리고 배열을 순회하면서:
- 현재 숫자의 보수를 구합니다:
complement = target - nums[i]. - 해시맵에서 보수가 존재하는지 확인합니다. 만약 존재하면 해당 인덱스와 현재 인덱스를 반환합니다.
- 보수가 없으면 현재 숫자와 인덱스를 해시맵에 저장합니다.
마지막으로 모든 숫자를 확인한 후 쌍이 존재하지 않으면 -1을 반환합니다.
5. 디버깅 활용 사례
이제 디버깅에 대한 중요성과 방법에 대해 알아보겠습니다. 코드를 작성할 때 몇 가지 문제가 발생할 수 있는데, 예를 들어 보수가 해시맵에 잘 저장되지 않거나, 잘못된 인덱스를 반환할 수도 있습니다.
이럴 경우, iostream을 이용하여 중간 결과를 출력해 볼 수 있습니다. 다음과 같이 코드를 수정하여 중간값을 출력할 수 있습니다:
// 중간 결과 출력 추가
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
cout << "현재 숫자: " << nums[i] << ", 보수: " << complement << endl;
if (map.find(complement) != map.end()) {
result.push_back(map[complement]);
result.push_back(i);
return result;
}
map[nums[i]] = i;
}
위와 같이 출력문을 추가하면 각 반복에서 어떤 값들이 처리되고 있는지를 파악할 수 있어, 문제를 해결하는 데 큰 도움이 됩니다.
6. 결론
이번 포스트에서는 C++을 사용한 알고리즘 문제 해결 과정과 디버깅의 중요성에 대해 알아보았습니다. 프로그래밍에는 다양한 문제들이 있으며, 각 문제마다 접근 방식이 다르지만, 효과적인 디버깅 기술을 통해 어려운 문제도 해결할 수 있습니다. 앞으로도 많은 연습을 통해 알고리즘 문제 해결 능력을 기르시길 바랍니다.
감사합니다!