이 문서는 세 가지 핵심 알고리즘 문제에 대한 다양한 해결 전략과 최적화 기법을 다룹니다. 소수 판별부터 배열 내 중복 원소 탐색, 그리고 '최대 물을 담을 수 있는 컨테이너' 문제까지, 각 문제에 대한 기본 접근 방식과 개선된 솔루션을 C++ 코드를 통해 설명합니다.
1. 소수 판별 알고리즘
소수(Prime Number)는 1과 자기 자신만으로 나누어떨어지는 1보다 큰 자연수를 의미합니다. 주어진 정수가 소수인지 판별하는 다양한 방법을 살펴보겠습니다.
1.1. 기본 접근: 2부터 N-1까지 확인
가장 직관적인 방법은 2부터 주어진 수 N-1까지의 모든 정수로 N을 나누어보는 것입니다. 만약 N이 이 범위 내의 어떤 수로도 나누어떨어지지 않는다면, N은 소수입니다.
#include <iostream>
// 주어진 수가 소수인지 판별하는 함수 (기본 버전)
bool isPrimeBasic(int numberToTest) {
if (numberToTest <= 1) return false; // 1 이하는 소수 아님
for (int divisor = 2; divisor < numberToTest; ++divisor) {
if (numberToTest % divisor == 0) {
return false; // 나누어떨어지면 소수 아님
}
}
return true; // 모든 검사를 통과하면 소수
}
int main() {
int inputNumber;
std::cout << "정수를 입력하세요: ";
std::cin << inputNumber;
if (isPrimeBasic(inputNumber)) {
std::cout << inputNumber << "은(는) 소수입니다." << std::endl;
} else {
std::cout << inputNumber << "은(는) 소수가 아닙니다." << std::endl;
}
return 0;
}
이 방법은 N이 커질수록 많은 연산을 수행해야 하므로 비효율적일 수 있습니다. 예를 들어, 7을 판별할 때는 2, 3, 4, 5, 6까지 확인하지만, 8을 판별할 때는 2에서 바로 나누어떨어지므로 일찍 종료됩니다.
1.2. 최적화: 2부터 N/2까지 확인
어떤 수 N이 N/2보다 큰 수 K로 나누어떨어진다면, 그 몫은 반드시 2보다 작아 1이 됩니다. 즉, N = K * Q에서 K > N/2이면 Q < 2이므로 Q는 1이어야 합니다. 이는 K가 N 그 자체임을 의미하므로, N이 N/2보다 큰 수로 나누어떨어지는 경우는 1과 자기 자신으로 나누어떨어지는 경우와 동일합니다. 따라서 N/2까지만 확인해도 충분합니다.
#include <iostream>
// 주어진 수가 소수인지 판별하는 함수 (N/2 최적화 버전)
bool isPrimeHalf(int numberToTest) {
if (numberToTest <= 1) return false;
for (int divisor = 2; divisor <= numberToTest / 2; ++divisor) { // 반복 범위를 num/2까지로 제한
if (numberToTest % divisor == 0) {
return false;
}
}
return true;
}
int main() {
int inputNumber;
std::cout << "정수를 입력하세요: ";
std::cin << inputNumber;
if (isPrimeHalf(inputNumber)) {
std::cout << inputNumber << "은(는) 소수입니다." << std::endl;
} else {
std::cout << inputNumber << "은(는) 소수가 아닙니다." << std::endl;
}
return 0;
}
1.3. 최종 최적화: 2부터 제곱근(sqrt(N))까지 확인
소수를 판별하는 가장 효율적인 일반적인 방법은 2부터 N의 제곱근(sqrt(N))까지의 수만 확인하는 것입니다. 만약 N이 sqrt(N)보다 큰 약수 K를 가진다면, N은 반드시 sqrt(N)보다 작은 약수 N/K도 가지게 됩니다. 따라서 sqrt(N)까지만 확인하면 모든 가능한 약수를 검사할 수 있습니다.
#include <iostream>
#include <cmath> // std::sqrt를 사용하기 위해 필요
// 주어진 수가 소수인지 판별하는 함수 (제곱근 최적화 버전)
bool isPrimeSqrt(int numberToTest) {
if (numberToTest <= 1) return false;
if (numberToTest == 2) return true; // 2는 소수
if (numberToTest % 2 == 0) return false; // 2를 제외한 짝수는 소수 아님
// 3부터 numberToTest의 제곱근까지 홀수만 확인 (i*i <= num 대신 i <= sqrt(num)도 가능)
for (int divisor = 3; divisor * divisor <= numberToTest; divisor += 2) {
if (numberToTest % divisor == 0) {
return false;
}
}
return true;
}
int main() {
int inputNumber;
std::cout << "정수를 입력하세요: ";
std::cin << inputNumber;
if (isPrimeSqrt(inputNumber)) {
std::cout << inputNumber << "은(는) 소수입니다." << std::endl;
} else {
std::cout << inputNumber << "은(는) 소수가 아닙니다." << std::endl;
}
return 0;
}
이 방법의 시간 복잡도는 O(sqrt(N))입니다. N이 매우 큰 경우에도 효율적인 판별이 가능합니다.
2. 배열 내 중복 원소 찾기
1부터 1000까지의 숫자 중 유일하게 하나의 값만 중복되는 1001개의 원소를 가진 배열에서, 중복되는 숫자를 찾아내는 문제를 다룹니다. (배열 인덱스가 아닌 중복되는 '값'을 찾는다고 가정합니다.)
2.1. 접근 방식 1: 무차별 대입 (Brute Force)
가장 단순한 방법은 배열의 모든 쌍을 비교하여 동일한 값을 찾는 것입니다. 이중 반복문을 사용하여 각 원소를 다른 모든 원소와 비교합니다.
#include <iostream>
#include <vector>
#include <algorithm> // std::sort를 사용하기 위해
// 무차별 대입 방식으로 중복 원소 찾기
void findDuplicateBruteForce(const std::vector<int>& dataArray) {
bool found = false;
for (size_t i = 0; i < dataArray.size(); ++i) {
for (size_t j = i + 1; j < dataArray.size(); ++j) {
if (dataArray[i] == dataArray[j]) {
std::cout << "중복 원소: " << dataArray[i] << std::endl;
found = true;
return; // 첫 번째 중복을 찾으면 종료
}
}
}
if (!found) {
std::cout << "중복 원소를 찾을 수 없습니다." << std::endl;
}
}
int main() {
std::vector<int> sampleNumbers = {2, 9, 8, 6, 5, 4, 1, 3, 7, 10, 8}; // 1부터 10까지 8이 중복
findDuplicateBruteForce(sampleNumbers);
// 대량 데이터 예시: 1부터 1000까지, 1001개 원소, 500이 중복
std::vector<int> largeArray(1001);
for (int i = 0; i < 1000; ++i) largeArray[i] = i + 1;
largeArray[1000] = 500;
// findDuplicateBruteForce(largeArray); // N이 크면 느림, 테스트 시 주석 해제
return 0;
}
이 방법의 시간 복잡도는 O(N^2)으로, 배열의 크기 N이 커질수록 성능 저하가 심합니다.
2.2. 접근 방식 2: 빈도수 카운팅 (Frequency Counting)
배열의 원소들이 특정 범위(예: 1부터 1000) 내에 있다면, 각 숫자의 출현 횟수를 기록하는 별도의 배열(또는 해시 맵)을 사용할 수 있습니다. 배열을 한 번 순회하면서 각 숫자의 빈도수를 증가시키고, 빈도수가 2가 되는 순간 해당 숫자가 중복 원소임을 알 수 있습니다.
#include <iostream>
#include <vector>
#include <numeric> // std::iota를 사용하기 위해
// 빈도수 카운팅 방식으로 중복 원소 찾기
int findDuplicateFrequency(const std::vector<int>& dataArray, int maxPossibleValue) {
// maxPossibleValue는 배열 내 원소들의 최대 값 (예: 1000)
// 인덱스를 값으로 사용하기 위해 maxPossibleValue + 1 크기의 벡터 생성
std::vector<int> counts(maxPossibleValue + 1, 0);
for (int num : dataArray) {
if (num >= 0 && num <= maxPossibleValue) { // 유효한 범위 내의 값인지 확인
counts[num]++;
if (counts[num] > 1) {
return num; // 중복 원소 반환
}
}
}
return -1; // 중복 원소를 찾을 수 없음
}
int main() {
std::vector<int> sampleNumbers = {2, 9, 8, 6, 5, 4, 1, 3, 7, 10, 8};
// 배열 내 최대 값은 10이므로 maxPossibleValue를 10으로 설정
std::cout << "중복 원소 (빈도수 카운팅): " << findDuplicateFrequency(sampleNumbers, 10) << std::endl;
// 대량 데이터 예시: 1부터 1000까지, 1001개 원소, 777이 중복
std::vector<int> largeArray(1001);
std::iota(largeArray.begin(), largeArray.begin() + 1000, 1); // 1부터 1000 채우기
largeArray[1000] = 777; // 777을 중복시킴
std::cout << "중복 원소 (큰 배열 빈도수 카운팅): " << findDuplicateFrequency(largeArray, 1000) << std::endl;
return 0;
}
이 방법의 시간 복잡도는 O(N)이며, 공간 복잡도도 O(M) (M은 숫자의 최대 범위)로 효율적입니다.
2.3. 접근 방식 3: 비트 연산 (XOR 활용)
배열에 1부터 N까지의 숫자가 있고 하나의 숫자가 중복될 때, XOR(배타적 논리합) 연산의 특성을 활용하여 중복된 숫자를 찾을 수 있습니다. XOR는 동일한 값을 두 번 XOR하면 원래 값으로 돌아오는 성질(A ^ A = 0, A ^ 0 = A)을 가집니다.
#include <iostream>
#include <vector>
#include <numeric>
// XOR 연산을 사용하여 중복 원소 찾기 (1부터 N까지의 숫자 중 하나만 중복되는 경우)
// arr: (1부터 N까지의 숫자와 하나의 중복된 숫자)를 포함하는 배열
// N: 중복되지 않은 숫자들의 최대값 (예: 1부터 1000까지의 숫자라면 N=1000)
int findDuplicateXOR(const std::vector<int>& dataArray, int N_range) {
int xorResult = 0;
// 1. 1부터 N_range까지의 모든 숫자를 XOR
for (int i = 1; i <= N_range; ++i) {
xorResult ^= i;
}
// 2. 배열 내 모든 숫자를 XOR
for (int num : dataArray) {
xorResult ^= num;
}
// 최종 xorResult는 중복된 숫자가 됩니다.
return xorResult;
}
int main() {
// 1부터 10까지의 숫자 중 8이 중복되는 예시 (배열 크기 N_range+1 = 11)
std::vector<int> sampleNumbers = {2, 9, 8, 6, 5, 4, 1, 3, 7, 10, 8};
// 이 경우 N_range는 10 (중복이 없는 1부터 10까지의 숫자 범위)
std::cout << "중복 원소 (XOR): " << findDuplicateXOR(sampleNumbers, 10) << std::endl;
// 1부터 1000까지의 숫자 중 777이 중복되는 예시 (배열 크기 N_range+1 = 1001)
std::vector<int> largeArray(1001);
std::iota(largeArray.begin(), largeArray.begin() + 1000, 1); // 1부터 1000 채우기
largeArray[1000] = 777; // 777 중복
std::cout << "중복 원소 (큰 배열 XOR): " << findDuplicateXOR(largeArray, 1000) << std::endl;
return 0;
}
이 방법의 시간 복잡도는 O(N)이며, 추가적인 공간을 거의 사용하지 않으므로 공간 복잡도는 O(1)입니다. 단, 이 방법은 1부터 N까지의 숫자 중 단 하나의 숫자가 중복되는 특정 상황에만 적용 가능합니다.
3. LeetCode 11: 최대 물을 담을 수 있는 컨테이너
n개의 음이 아닌 정수 a1, a2, ..., an이 주어집니다. 이 숫자들은 좌표 (i, ai)에 해당하는 수직선을 나타냅니다. n개의 수직선을 좌표 평면에 그렸을 때, 이들 중 두 개의 선과 x축으로 만들 수 있는 컨테이너가 담을 수 있는 최대 물의 양을 찾으세요. 컨테이너는 기울일 수 없으며, n은 최소 2입니다.
예시:
입력: [1,8,6,2,5,4,8,3,7]
출력: 49
3.1. 접근 방식 1: 무차별 대입 (Brute Force)
가능한 모든 두 선의 쌍을 고려하여 각각의 면적을 계산하고, 그 중 최댓값을 찾습니다. 컨테이너의 면적은 두 선 사이의 너비와 두 선 중 더 낮은 선의 높이를 곱한 값입니다.
#include <iostream>
#include <vector>
#include <algorithm> // std::max, std::min 사용
class ContainerSolver {
public:
int maxAreaBruteForce(std::vector<int>& wallHeights) {
int maxCapacity = 0;
int numWalls = wallHeights.size();
for (int i = 0; i < numWalls; ++i) {
for (int j = i + 1; j < numWalls; ++j) {
// 너비는 두 인덱스 간의 거리
int currentWidth = j - i;
// 높이는 두 벽 중 더 낮은 높이
int effectiveHeight = std::min(wallHeights[i], wallHeights[j]);
// 현재 컨테이너의 용량 계산
int currentCapacity = currentWidth * effectiveHeight;
// 최대 용량 업데이트
maxCapacity = std::max(maxCapacity, currentCapacity);
}
}
return maxCapacity;
}
};
int main() {
ContainerSolver solver;
std::vector<int> sampleHeights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
std::cout << "최대 용량 (무차별 대입): " << solver.maxAreaBruteForce(sampleHeights) << std::endl; // 출력: 49
return 0;
}
이 방법의 시간 복잡도는 O(N^2)으로, N이 커지면 효율성이 떨어집니다. LeetCode와 같은 플랫폼에서는 '시간 초과'가 발생할 수 있습니다.
3.2. 접근 방식 2: 투 포인터 (Two Pointers)
이 문제에 대한 더 효율적인 해결책은 투 포인터 기법을 사용하는 것입니다. 양 끝에 두 개의 포인터(leftPtr와 rightPtr)를 배치하고, 이들을 서로를 향해 이동시키면서 최대 면적을 찾습니다.
컨테이너의 면적은 (rightPtr - leftPtr) * min(wallHeights[leftPtr], wallHeights[rightPtr])입니다. 면적을 최대로 만들려면 너비와 높이 모두 커야 합니다. 너비는 포인터가 가까워질수록 줄어들기 때문에, 높이를 최대한 유지하거나 늘려야 합니다.
매 단계에서 leftPtr와 rightPtr 포인터가 가리키는 두 선 중 더 짧은 선을 안쪽으로 이동시킵니다. 왜냐하면 더 긴 선을 이동시켜도 현재 높이보다 더 높은 선을 찾을 가능성이 낮고, 너비는 줄어들기 때문에 면적이 줄어들 가능성이 큽니다. 반면, 짧은 선을 이동시키면 너비가 줄더라도 더 높은 선을 찾아 면적을 늘릴 잠재력이 있습니다.
#include <iostream>
#include <vector>
#include <algorithm> // std::max, std::min 사용
class ContainerSolver {
public:
int maxAreaTwoPointers(std::vector<int>& wallHeights) {
int maxCapacity = 0;
int leftPtr = 0; // 왼쪽 포인터
int rightPtr = wallHeights.size() - 1; // 오른쪽 포인터
while (leftPtr < rightPtr) {
// 현재 너비 계산
int currentWidth = rightPtr - leftPtr;
// 현재 높이는 두 포인터 중 더 낮은 높이
int currentHeight = std::min(wallHeights[leftPtr], wallHeights[rightPtr]);
// 현재 컨테이너의 용량 계산
int currentCapacity = currentWidth * currentHeight;
// 최대 용량 업데이트
maxCapacity = std::max(maxCapacity, currentCapacity);
// 더 짧은 선의 포인터를 안쪽으로 이동
if (wallHeights[leftPtr] < wallHeights[rightPtr]) {
leftPtr++;
} else {
rightPtr--;
}
}
return maxCapacity;
}
};
int main() {
ContainerSolver solver;
std::vector<int> sampleHeights = {1, 8, 6, 2, 5, 4, 8, 3, 7};
std::cout << "최대 용량 (투 포인터): " << solver.maxAreaTwoPointers(sampleHeights) << std::endl; // 출력: 49
return 0;
}
이 방법의 시간 복잡도는 O(N)으로, 배열을 한 번만 순회하므로 매우 효율적입니다.