C++ 코딩테스트 강좌, 연결 요소의 개수 구하기

안녕하세요! 오늘은 C++ 코딩테스트에서 자주 등장하는 알고리즘 문제 중 하나인 “연결 요소의 개수 구하기”에 대해 알아보겠습니다. 이 문제는 그래프 이론에서 중요한 개념 중 하나인 ‘연결 요소’를 이해하고 구현하는 데 큰 도움이 될 것입니다.

문제 설명

주어진 무방향 그래프에서 연결 요소의 개수를 구하는 문제입니다. 연결 요소란 그래프의 부분 그래프 중에서 서로 연결된 정점들로 이루어진 집합을 의미합니다. 그래프의 정점들 사이에 간선이 있을 때, 직간접적으로 연결된 모든 정점들은 하나의 연결 요소로 간주됩니다. 예를 들어, 아래와 같은 그래프가 있다고 가정해 봅시다.

    1
   / \
  0   2
      |
      3

이 그래프는 1, 0, 2, 3이 연결된 하나의 연결 요소이며, 다음과 같은 독립된 정점이 있을 경우 연결 요소의 개수는 두 개가 됩니다.

그림과 같이 1, 2, 3이 포함된 연결 요소와 4가 포함된 연결 요소로 구분될 수 있습니다.

입력 형식

  • 첫 번째 줄에는 정점의 개수 N (1 ≤ N ≤ 1000)과 간선의 개수 M (0 ≤ M ≤ N*(N-1)/2)이 주어진다.
  • 다음 M개의 줄에 걸쳐 각 간선에 대한 정보를 나타내며, 두 개의 정점 A와 B가 주어진다. 이를 통해 정점 A와 B가 연결되어 있음을 나타냅니다.

출력 형식

연결 요소의 개수를 출력합니다.

예제

입력:
5 3
0 1
0 2
3 4

출력:
2

문제 풀이

이 문제를 해결하기 위해서는 다음과 같은 과정으로 접근합니다.

1. 그래프 표현

그래프를 표현하기 위해 인접 리스트(adjacency list)를 사용합니다. 각 정점에 대한 연결 정보를 저장하는 벡터를 선언하고, M개의 간선 정보를 입력받아 그래프를 구성합니다. C++ STL의 vector를 활용하여 쉽게 구현할 수 있습니다.

#include <iostream>
#include <vector>

using namespace std;

vector> graph;
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

2. DFS 또는 BFS 이용하기

연결 요소의 개수를 구하기 위해 그래프의 모든 정점을 탐색할 필요가 있습니다. 우리가 선택한 탐색 방법은 깊이 우선 탐색(DFS)입니다. 이를 통해 현재 탐색하는 정점과 연결된 모든 정점들을 방문하게 됩니다. 방문한 정점들은 미처리 상태에서 ‘방문’ 상태로 변경하여 중복 방문을 피합니다.

void dfs(int node, vector& visited) {
    visited[node] = true; // 현재 노드를 방문 상태로 변경
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

3. 주요 변수 및 로직 구현

연결 요소의 개수를 세기 위한 변수 components를 선언하고, 모든 정점을 차례대로 탐색합니다. 각 정점을 방문할 때마다 DFS를 호출하고, 호출 전에 components를 증가시킵니다. 이 단계에서 모든 정점을 확인하면 총 연결 요소의 개수를 알 수 있습니다.

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // 새로운 연결 요소 발견
        }
    }

    cout << components << endl; // 결과 출력
    return 0;
}

전체 코드

#include <iostream>
#include <vector>

using namespace std;

vector> graph;

// 간선 추가 함수
void addEdge(int a, int b) {
    graph[a].push_back(b);
    graph[b].push_back(a);
}

// DFS 함수
void dfs(int node, vector& visited) {
    visited[node] = true; // 현재 노드를 방문 상태로 변경
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, visited);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    graph.resize(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        addEdge(a, b);
    }

    vector visited(n, false);
    int components = 0;

    for (int i = 0; i < n; ++i) {
        if (!visited[i]) {
            dfs(i, visited);
            components++; // 새로운 연결 요소 발견
        }
    }

    cout << components << endl; // 결과 출력
    return 0;
}

알고리즘 복습

이제 이 문제를 통해 우리는 그래프를 표현하고, DFS를 통해 연결 요소를 탐색하는 방법을 배웠습니다. 알고리즘의 복잡도는 다음과 같습니다:

  • 시간 복잡도: O(N + M), 여기서 N은 정점의 수, M은 간선의 수입니다.
  • 공간 복잡도: O(N + M) 그래프를 저장하기 위한 공간과 방문 여부를 저장하기 위한 공간이 필요합니다.

문제 해결을 위한 팁

  • 문제를 풀기 전에 그래프가 어떻게 구성되었는지 그림으로 그려보세요. 이를 통해 문제 이해가 더 쉬워집니다.
  • 각 연결 요소를 찾을 때 BFS를 사용해도 좋습니다. BFS는 레벨 순서로 탐색하기 때문에 특정 문제에서 유리할 수 있습니다.
  • 상황에 따라 연결 요소의 개수 외에도 각 요소의 크기 또는 구조를 분석하는 문제가 나올 수 있으니, 그래프 탐색을 익히는 것이 좋습니다.

여기까지가 “연결 요소의 개수 구하기” 문제 풀이였습니다. 이 강좌가 유익했기를 바라며, 앞으로 다양한 알고리즘과 문제들을 함께 살펴보겠습니다. 감사합니다!

C++ 코딩테스트 강좌, 여행 계획 짜기

문제 설명

당신은 다가오는 휴가를 위해 여행 계획을 세우고 있습니다. 여행할 도시와 각 도시 간 이동 비용이 주어질 때, 주어진 예산 내에서 최대한 많은 도시를 방문하는 경로를 찾아야 합니다.

입력 형식

  • 첫 번째 줄에 정점의 개수 N이 주어진다 (1 ≤ N ≤ 100).
  • 다음 N줄에 N x N 크기의 인접 행렬이 주어진다. 인접 행렬의 값은 두 도시 간 이동 비용이며, 이동할 수 없는 경우는 -1로 표시된다.
  • 마지막 줄에 전체 예산 B가 주어진다 (0 ≤ B ≤ 106).

출력 형식

방문할 수 있는 도시의 최대 개수를 출력하시오.

문제 해결 과정

1. 문제 분석

이 문제는 그래프 탐색 및 동적 프로그래밍을 활용하여 해결할 수 있습니다. 각 도시를 정점으로 하고 도시 간의 이동 비용을 간선으로 생각할 수 있습니다. 주어진 예산 내에서 최대한 많은 도시를 방문하기 위해 백트래킹(DFS)을 활용하여 가능한 모든 경로를 탐색할 것입니다. 이동 비용이 -1인 경우는 이동할 수 없는 도시를 의미하므로 이러한 경우를 제외해야 합니다.

2. 알고리즘 설계

문제를 해결하기 위한 기본적인 알고리즘은 다음과 같습니다:

  1. 현재 도시에서 방문한 도시 수와 남은 예산을 추적하기 위해 변수를 선언합니다.
  2. 깊이 우선 탐색(DFS)를 구현하여 현재 도시에서 갈 수 있는 모든 도시를 재귀적으로 탐색합니다.
  3. 부모 노드로 돌아올 때 남은 예산과 방문한 도시 수를 업데이트합니다.
  4. 재귀 호출의 모든 경로를 탐색한 후 최대 방문 도시 수를 비교하여 업데이트 합니다.

3. C++ 코드 구현

다음은 위의 알고리즘을 C++ 코드로 구현한 예제입니다:

 
#include <iostream> 
#include <vector> 
#include <algorithm> 

using namespace std; 

int N, B; 
vector<vector<int>> cost; 
int maxCities = 0; 

void dfs(int currentCity, int currentBudget, int visitedCount) { 
    maxCities = max(maxCities, visitedCount); 

    for (int nextCity = 0; nextCity < N; nextCity++) { 
        if (cost[currentCity][nextCity] != -1 && currentBudget - cost[currentCity][nextCity] >= 0) { 
            // 다음 도시로 이동 
            dfs(nextCity, currentBudget - cost[currentCity][nextCity], visitedCount + 1); 
        } 
    } 
} 

int main() { 
    cout << "지점의 수 N을 입력하세요: "; 
    cin >> N; 
    cost.resize(N, vector<int>(N)); 

    cout << "비용 행렬을 입력하세요: " << endl; 
    for (int i = 0; i < N; i++) { 
        for (int j = 0; j < N; j++) { 
            cin >> cost[i][j]; 
        } 
    } 

    cout << "전체 예산 B를 입력하세요: "; 
    cin >> B; 

    for (int i = 0; i < N; i++) { 
        dfs(i, B, 1); // 각 도시에서 DFS 시작 
    } 

    cout << "방문할 수 있는 최대 도시 수: " << maxCities << endl; 
    return 0; 
} 

4. 코드 설명

위 코드는 입력을 통해 도시 간 이동 비용을 가져오고, 각 도시에서 시작하여 깊이 우선 탐색을 진행합니다.

  • maxCities: 방문한 도시의 최대 개수를 저장하는 변수입니다.
  • dfs 함수: 현재 도시, 남은 예산, 방문한 도시 수를 인자로 받아 모든 가능한 경로를 탐색합니다.
  • 메인 함수에서 사용자로부터 입력을 받고, 모든 도시에서 DFS를 호출하여 최대 방문할 수 있는 도시 수를 구합니다.

5. 실행 결과

코드를 컴파일하고 실행하면 다음과 같은 출력 결과를 얻을 수 있습니다:


지점의 수 N을 입력하세요: 4
비용 행렬을 입력하세요: 
0 10 15 -1
10 0 35 20
15 35 0 30
-1 20 30 0
전체 예산 B를 입력하세요: 50
방문할 수 있는 최대 도시 수: 3

6. 마무리

이번 강좌에서는 C++을 이용해 여행 계획을 짜는 알고리즘 문제를 다뤄보았습니다. 깊이 우선 탐색(DFS)과 백트래킹을 통해 예산 내 최대 도시 방문 수를 계산하는 과정을 익혔습니다. 이를 통해 그래프 탐색 알고리즘을 이해하고, 실제 문제를 해결하는 데 어떻게 적용할 수 있는지 살펴보았습니다.

백트래킹 기법은 비단 이 문제에만 국한되지 않고 다양한 조합 및 순열 관련 문제에서도 활용될 수 있으므로, 알고리즘의 기본 개념을 정확히 이해하는 것이 중요합니다. 추후 알고리즘 문제를 더 많이 연습하여 연습량을 늘려보면 좋겠습니다.

C++ 코딩테스트 강좌, 어떤 알고리즘으로 풀어야 할까

서론

코딩 테스트는 현대의 소프트웨어 엔지니어링에서 중요한 역할을 담당하고 있습니다. 많은 기업들이 구직자의 알고리즘 문제 해결 능력을 평가하기 위해 코딩 테스트를 실시하고 있으며, 이 과정에서 C++ 언어는 그 효율성과 다양한 기능들 덕분에 많은 인기를 끌고 있습니다. 본 포스트에서는 C++를 이용한 알고리즘 문제를 통해 어떤 알고리즘을 사용해야 하는지에 대한 가이드를 제공합니다.

문제 설명

다음은 우리가 해결할 알고리즘 문제입니다. 두 수의 합 문제를 예로 들겠습니다.

문제: 두 수의 합

주어진 정수 배열 nums와 정수 target가 주어질 때, nums 안의 두 수를 더하여 target을 만들 수 있는 두 수의 인덱스를 반환하시오. 같은 요소를 두 번 사용할 수 없으며, 하나의 정답만 존재한다고 가정합니다.

예시:
    입력: nums = [2, 7, 11, 15], target = 9
    출력: [0, 1]
    설명: nums[0] + nums[1] = 2 + 7 = 9 이므로 [0, 1]을 반환합니다.
    

문제 풀이 전략

이 문제를 해결하기 위해 우리는 다음의 몇 가지 접근 방식을 사용할 수 있습니다:

1. 브루트 포스(탐색)

가장 간단한 방법은 모든 가능한 조합을 시도하는 것입니다. 이 방법은 이중 루프를 사용하여 모든 가능한 두 수의 조합을 검사합니다. 시간 복잡도는 O(n^2) 입니다.

2. 해시 맵 사용

해시 맵을 사용하여 각 수를 키로, 그 인덱스를 값으로 저장하면 더 효율적으로 실행할 수 있습니다. 배열을 한 번만 순회하면서 각 원소에 대해 target - nums[i]를 계산하고, 이 값이 해시 맵에 있는지 여부를 확인합니다. 시간 복잡도는 O(n)입니다.

3. 정렬과 이분 탐색

수를 정렬한 후 이분 탐색을 사용할 수 있지만, 정렬 과정에서 시간이 추가로 걸려 시간 복잡도는 O(n log n)으로 증가합니다. 이 방법은 가장 효율적이지 않으므로, 저희는 해시 맵을 활용한 방법을 선택하겠습니다.

구현

이제 C++로 해시 맵을 사용한 최적의 풀이를 구현해 보겠습니다.


#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector twoSum(vector& nums, int target) {
    unordered_map num_map; // 수와 인덱스를 저장할 해시 맵입니다.
    vector result; // 결과를 저장할 벡터입니다.

    for (int i = 0; i < nums.size(); i++) {
        int complement = target - nums[i]; // 필요한 다른 수를 계산합니다.
        if (num_map.find(complement) != num_map.end()) {
            result.push_back(num_map[complement]); // 인덱스를 추가합니다.
            result.push_back(i); // 현재 인덱스를 추가합니다.
            return result; // 결과를 반환합니다.
        }
        num_map[nums[i]] = i; // 수를 해시 맵에 추가합니다.
    }
    return result; // 해답이 없으면 빈 벡터를 반환합니다.
}

int main() {
    vector nums = {2, 7, 11, 15};
    int target = 9;
    vector result = twoSum(nums, target);
    
    cout << "[";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
    return 0;
}
    

코드 설명

제공된 코드는 아래와 같은 구조로 되어 있습니다:

  1. 헤더 파일 포함: 필요한 헤더 파일들을 포함합니다. iostream는 입출력 스트림을, vector는 동적 배열을, unordered_map은 해시 맵을 사용하기 위해 필요합니다.
  2. 함수 정의: twoSum 함수는 인자로 정수 배열과 목표값을 받습니다. 해시 맵을 정의하고, 배열의 모든 원소를 순회합니다.
  3. 해시 맵을 사용한 검사: 각 반복에서 필요한 값을 계산하고, 해시 맵에 존재할 경우 결과를 업데이트합니다.
  4. 메인 함수: main 함수에서는 입력값을 정의하고, twoSum 함수를 호출하여 결과를 출력합니다.

시간 복잡도 분석

이 솔루션의 최악의 경우 시간 복잡도는 O(n)입니다. 여기서 n은 배열의 크기입니다. 해시 맵에서 각 원소를 추가 및 검색하는 데 평균적으로 O(1)의 시간이 소요되기 때문입니다. 사용된 추가 공간은 해시 맵 때문으로 O(n)입니다.

결론

C++로 코딩 테스트 문제를 풀 때 적절한 알고리즘을 선택하는 것은 매우 중요합니다. 특히, 문제의 성격과 데이터의 크기를 잘 분석해야 합니다. 이번 포스트에서 우리는 두 수의 합 문제를 통해 해시 맵을 사용한 최적의 풀이를 학습했습니다. 이러한 접근법은 단순명료하면서도 효율적인 많은 코딩 테스트 문제를 해결하는 데 도움이 됩니다.

추가 학습 자료

알고리즘 문제 해결을 위한 더욱 고급 주제를 배우고 싶다면 몇 가지 리소스를 추천합니다:

  • GeeksforGeeks – 다양한 알고리즘과 문제 풀이를 다룹니다.
  • LeetCode – 다양한 코딩 테스트 문제와 토픽을 제공합니다.
  • HackerRank – 여러 알고리즘 종류와 직접 문제를 풀며 학습할 수 있는 플랫폼입니다.

마무리

알고리즘 문제 풀이에 대한 학습은 지속적인 노력과 연습이 필요합니다. 다양한 문제를 풀어보고, 최적의 해결책을 찾아보는 경험이 여러분의 실력을 향상시키는 데 큰 도움이 될 것입니다. C++와 알고리즘에 대한 깊은 이해를 바탕으로 여러분의 성공적인 코딩 테스트를 기원합니다!

C++ 코딩테스트 강좌, 시간 복잡도 활용하기

코딩 테스트를 준비하면서 가장 중요한 것 중 하나는 문제 해결 능력과 함께 시간 복잡도를 이해하고 최적화하는 것입니다. 이 글에서는 C++을 사용하여 시간 복잡도를 고려하여 문제를 해결하는 과정을 자세히 설명하겠습니다.

문제: 최장 증가 부분 수열 (Longest Increasing Subsequence)

주어진 정수 배열에서 최장 증가 부분 수열의 길이를 구하는 문제입니다.

문제 설명

정수 배열 nums가 주어졌을 때, 증가하는 부분 수열의 가장 긴 길이를 반환하시오. 부분 수열은 배열에서 선택된 원소들이 원래의 순서를 유지해야 하지만 연속적일 필요는 없습니다.

예제

    입력: nums = [10, 9, 2, 5, 3, 7, 101, 18]
    출력: 4
    설명: 최장 증가 부분 수열은 [2, 3, 7, 101]로, 길이는 4입니다.
    

접근 방법

이 문제는 동적 계획법(Dynamic Programming)과 이진 검색(Binary Search)을 조합하여 해결할 수 있습니다. 시간 복잡도를 고려하여 다음과 같은 접근 방법을 사용할 수 있습니다:

1. 동적 계획법을 이용한 접근

우선, 각 원소마다 자신을 마지막 원소로 하는 증가 부분 수열의 길이를 기록합니다. 그러면 각 요소를 순회하며 이전의 모든 요소와 비교하여 가능하면 부분 수열의 길이를 업데이트할 수 있습니다.

2. 이진 검색과 결합

최종적으로 우리는 부분 수열의 끝 원소를 기록하기 위한 배열을 사용하고, 이 배열에서 각 요소에 대해 이진 검색을 적용하여 현재 원소를 삽입할 위치를 찾습니다. 이 방법을 통해 더 최적화된 성능을 달성할 수 있습니다.

구현

다음은 C++로 이 문제를 해결하는 코드입니다:


#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;

    vector<int> dp;
    for (int num : nums) {
        auto it = lower_bound(dp.begin(), dp.end(), num);
        if (it == dp.end()) {
            dp.push_back(num);
        } else {
            *it = num;
        }
    }
    return dp.size();
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << "최장 증가 부분 수열의 길이: " << lengthOfLIS(nums) << endl;
    return 0;
}
    

시간 복잡도 분석

이 문제의 시간 복잡도는 O(n log n)입니다. 각각의 원소에 대해 이진 검색을 수행하여 적절한 위치를 찾고, 이진 검색의 시간 복잡도는 log n입니다. 따라서 전체적인 시간 복잡도는 O(n log n)이고, 공간 복잡도는 O(n)입니다.

결론

이와 같은 문제는 배열에서 최장 증가 부분 수열을 찾는 것처럼, 시간 복잡도를 줄이기 위해 동적 계획법과 이진 검색을 조합하는 것이 중요합니다. C++의 STL에서 제공하는 유용한 함수와 자료구조를 잘 활용하면 더욱 효율적인 코드를 작성할 수 있습니다.

이 글에서는 C++를 사용하여 시간 복잡도 분석과 이를 활용한 알고리즘 문제 해결 방법을 설명했습니다. 앞으로의 코딩 테스트 준비에 도움이 되었기를 바랍니다!

C++ 코딩테스트 강좌, 신기한 소수 찾기

안녕하세요, 여러분. 이 강좌에서는 C++을 이용한 코딩 테스트 문제를 풀어보도록 하겠습니다.
주제는 바로 “신기한 소수 찾기“로, 소수에 대한 깊이 있는 이해와 더불어
알고리즘 설계 및 최적화까지 다루어 보겠습니다.

문제 설명

주어진 범위 [L, R] 내의 모든 소수를 찾는 문제입니다.
소수는 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 수를 의미합니다.
이번 문제에서는 소수를 찾는 과정에서 다음 두 가지 조건을 충족해야 합니다:

  • 범위 내부의 소수를 찾아야 한다.
  • 각 소수를 출력하기 전에 ‘신기한 소수’인 경우 (“신기한”)라는 문구를 붙여야 한다.

과제를 위해 코드의 시간 복잡도를 고려하면서 효율적으로 소수를 찾아보겠습니다.

입력

두 정수 L, R (1 ≤ L ≤ R ≤ 1000000) 주어집니다.

출력

L과 R 사이의 모든 소수를 출력합니다.
특히, 2 이상의 소수 중에서 그 소수의 모든 자리가 1, 2, 3, 5, 7의 조합으로 이루어진 경우 “신기한”을 출력합니다.

예제

        입력:
        10 30

        출력:
        11 신기한
        13 신기한
        17 신기한
        19 신기한
        23 신기한
        29 신기한
    

문제 풀이 계획

  1. 입력 받은 범위 L과 R을 처리합니다.
  2. Sieve of Eratosthenes 알고리즘을 사용하여 소수를 찾습니다.
  3. 신기한 소수를 판별하기 위한 기능을 구현합니다.
  4. 찾은 소수를 출력합니다.

알고리즘 설명

소수를 찾기 위해 Sieve of Eratosthenes 알고리즘을 사용할 것입니다.
이 방법은 주어진 범위 내에서 소수를 효율적으로 찾는 데 매우 유용합니다.
알고리즘의 기본 원리는 다음과 같습니다:

  1. 2부터 시작하여 각 수를 소수 리스트에 추가합니다.
  2. 그 수의 배수를 지움으로써 소수를 걸러냅니다.
  3. 이 과정을 범위의 최댓값까지 반복합니다.

C++ 코드 구현


#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 주어진 숫자가 신기한 소수인지 체크하는 함수
bool isMagicalPrime(int num) {
    string s = to_string(num);
    for(char c : s) {
        if(c != '1' && c != '2' && c != '3' && c != '5' && c != '7') {
            return false;
        }
    }
    return true;
}

// 소수를 찾는 Sieve of Eratosthenes 알고리즘
vector<bool> sieve(int maxNum) {
    vector<bool> isPrime(maxNum + 1, true);
    isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님
    for(int i = 2; i * i <= maxNum; i++) {
        if(isPrime[i]) {
            for(int j = i * i; j <= maxNum; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

int main() {
    int L, R;
    cin >> L >> R;

    vector<bool> prime = sieve(R);
    
    for(int i = L; i <= R; i++) {
        if(prime[i]) {
            cout << i;
            if(isMagicalPrime(i)) {
                cout << " 신기한";
            }
            cout << endl;
        }
    }
    return 0;
}
    

코드 설명

위의 코드는 두 개의 주요 함수를 포함하고 있습니다:

  • isMagicalPrime(int num): 주어진 수가 신기한 소수인지 체크합니다.
    주어진 숫자를 문자열로 변환하여 각 자리수를 분석합니다.
    자리수가 ‘1, 2, 3, 5, 7’ 중 하나인 경우에만 true를 반환합니다.
  • sieve(int maxNum): Sieve of Eratosthenes 알고리즘을 구현한 함수로,
    주어진 최대 숫자까지 소수를 계산하여 bool 벡터를 반환합니다.

결론

이번 강좌에서는 간단한 소수 찾기 문제를 통해 C++ 언어와 자료구조에 대한 감각을 키울 수 있었습니다.
또한 Sieve of Eratosthenes 알고리즘을 실제로 사용하여 효율적인 소수 검색 방법을 체험해 볼 수 있었습니다.
다음 시간에는 좀 더 복잡한 문제를 다루어 보도록 하겠습니다.

내용이 유익하셨다면 댓글로 의견 남겨주세요. 질문 여부도 환영합니다!