[알고리즘] C++ 손코딩 예제 정리

간단한 알고리즘을 사용하는 손코딩 문제의 예제를 정리

1. 배열에서 최대값 찾기

#include <iostream>
#include <vector>
using namespace std;

int findMax(const vector<int>& nums) {
    int maxVal = nums[0]; // 임시변수 생성
    for (int num : nums) {
        if (num > maxVal) maxVal = num; // 값갱신
    }
    return maxVal; // 반환
}

2. 문자열 뒤집기

#include <iostream>
#include <string>
using namespace std;

void reverseString(string& str) {
    int n = str.length(); // 문자열의 길이를 저장
    for (int i = 0; i < n / 2; ++i) {
        swap(str[i], str[n - i - 1]); // 문자열을 반으로 나누어 스왑한다.
    }
}

3. 팩토리얼 계산 (재귀)

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1; // 재귀는 꼭 함수의 탈출 조건을 먼저 제시해야한다.
    return n * factorial(n - 1);
}

4. 피보나치 수열 (반복)

#include <iostream>

int Fibonacci(int n) {
    if (n <= 1) return n; // 탈출 조건문
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

5. 이진 탐색

#include <iostream>
#include <vector>
using namespace std;

int binarySearch(const vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1; // 임시 변수 2개 생성
    while (left <= right) {
        int mid = left + (right - left) / 2; // 반복문의 임시 변수 생성
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1;
}

6. 연결 리스트에서 N번째 노드 찾기

#include <iostream>
using namespace std;

struct ListNode {
    int val; // 노드의 값
    ListNode* next; // 다음 노드의 주소
    ListNode(int x) : val(x), next(nullptr) {} // 초기화
};

ListNode* findNthNode(ListNode* head, int n) {
    while (head != nullptr && n-- > 0) {
        head = head->next; // 순차적으로 넘어가기
    }
    return head; // 반환
}

7. 괄호 유효성 검사

#include <iostream>
#include <stack>
using namespace std;

bool isValid(string s) {
    stack<char> st; // char 자료형을 저장하는 스택 임시 변수
    for (char ch : s) {
        if (ch == '(' || ch == '{' || ch == '[') st.push(ch); // 괄호 시작 3종
        else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            
            // 괄호의 끝부분이고 시작이 아닌 조건문
            if ((ch == ')' && top != '(') || 
                (ch == '}' && top != '{') || 
                (ch == ']' && top != '[')) return false;
        }
    }
    return st.empty(); // 빈 스택 반환
}

8. 두 정렬된 배열 병합

#include <iostream>
#include <vector>
using namespace std;

vector<int> mergeSortedArrays(const vector<int>& nums1, const vector<int>& nums2) {
    vector<int> merged;
    int i = 0, j = 0;
    while (i < nums1.size() && j < nums2.size()) {
        if (nums1[i] < nums2[j]) merged.push_back(nums1[i++]);
        else merged.push_back(nums2[j++]);
    }
    while (i < nums1.size()) merged.push_back(nums1[i++]);
    while (j < nums2.size()) merged.push_back(nums2[j++]);
    return merged;
}

9. 문자열 내 문자 빈도수 세기

#include <iostream>
#include <unordered_map>
using namespace std;

// 정렬되지 않은 키를 추가하는 unordered_map 키,와 값으로 이루어져있으며 키는 중복되지 않는다
unordered_map<char, int> countCharFrequency(const string& str) {
    unordered_map<char, int> freq; // 임시 변수 맵을 생성하고
    for (char ch : str) {
        freq[ch]++; // 맵의 값(int)를 ++ 시킨다.
    }
    return freq; // 값(카운팅)저장이 완료된 임시변수의 맵을 반환 시킨다.
}

10. 두 문자열이 애너그램인지 확인

애너그램(Anagram)은 두 문자열이 같은 문자들로 구성되어 있고, 각 문자의 빈도수도 동일한 경우를 말합니다.

즉, 한 문자열을 다른 문자열의 문자들을 재배열하여 만들 수 있다면, 그 두 문자열은 애너그램 관계에 있습니다.
예를 들어:
"listen"과 "silent"는 애너그램입니다. 두 문자열 모두 같은 문자 'l', 'i', 's', 't', 'e', 'n'을 동일한 빈도로 포함하고 있습니다.
"triangle"과 "integral"도 애너그램입니다. 두 문자열 모두 't', 'r', 'i', 'a', 'n', 'g', 'l', 'e'를 포함하고 있습니다.

#include <iostream>
#include <unordered_map>
using namespace std;

bool isAnagram(string s, string t) {
    if (s.length() != t.length()) return false; // 문자열의 길이가 다르다면 애너그램X
    unordered_map<char, int> count; // 정렬되지않은 맵으로 키,값을 사용
    for (char ch : s) count[ch]++; // 첫문자열에서 하나의 키가 몇번이나 있는지 검증
    for (char ch : t) {
    // 두번째 문자열의 길이를 하나씩 내려가고 첫문자열보다 길이가 길경우  애너그램x
        if (--count[ch] < 0) return false; 
    }
    return true; // 모든 조건문 통과시 애너그램o
}

11. 주어진 배열의 모든 부분집합 생성

#include <iostream>
#include <vector>
using namespace std;

// 재귀적으로 부분집합을 생성하는 함수
void generateSubsets(vector<int>& nums, vector<vector<int>>& result, vector<int>& subset, int index) {
    // 현재 부분집합을 결과에 추가
    result.push_back(subset);
    
    // 주어진 인덱스부터 끝까지 반복
    for (int i = index; i < nums.size(); ++i) {
        // 현재 요소를 부분집합에 추가
        subset.push_back(nums[i]);
        // 다음 인덱스를 기준으로 재귀 호출
        generateSubsets(nums, result, subset, i + 1);
        // 재귀 호출 이후 마지막 요소 제거 (백트래킹)
        subset.pop_back();
    }
}

// 주어진 벡터의 모든 부분집합을 반환하는 함수
vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;  // 결과를 저장할 벡터
    vector<int> subset;          // 현재 부분집합을 저장할 벡터
    // 부분집합 생성을 시작 (인덱스 0부터)
    generateSubsets(nums, result, subset, 0);
    return result;               // 모든 부분집합을 반환
}

int main() {
    vector<int> nums = {1, 2, 3};
    vector<vector<int>> result = subsets(nums);
    
    // 결과 출력
    for (const auto& subset : result) {
        cout << "{ ";
        for (int num : subset) {
            cout << num << " ";
        }
        cout << "}" << endl;
    }
    
    return 0;
}

12. 최대 공약수(GCD) 계산

최대 공약수(GCD, Greatest Common Divisor)는 두 정수 또는 그 이상의 정수 집합에서 공통으로 나누어 떨어지는 가장 큰 양의 정수를 의미합니다. 예를 들어, 12와 18의 최대 공약수는 6입니다. 왜냐하면 6은 12와 18을 나눌 수 있는 가장 큰 양의 정수이기 때문입니다.

두 수 a와 b의 최대 공약수 GCD(a, b)를 구하는 대표적인 방법은 유클리드 호제법(Euclidean algorithm)입니다. 유클리드 호제법은 다음과 같은 절차를 따릅니다:

a를 b로 나눈 나머지 r을 구합니다.
만약 r이 0이라면, b가 최대 공약수입니다.
그렇지 않다면, a를 b로, b를 r로 바꾸고 1단계로 돌아갑니다.
유클리드 호제법을 이용한 C++ 코드 예제는 다음과 같습니다:

#include <iostream>
using namespace std;

// 유클리드 알고리즘을 사용하여 GCD(최대 공약수)를 계산하는 함수
int gcd(int a, int b) {
    // b가 0이 될 때까지 반복
    while (b != 0) {
        // a를 b로 나눈 나머지를 r에 저장
        int r = a % b;
        // a를 b로, b를 r로 갱신
        a = b;
        b = r;
    }
    // b가 0이 되었을 때의 a가 GCD
    return a;
}

int main() {
    int num1 = 48;  // 첫 번째 숫자
    int num2 = 18;  // 두 번째 숫자

    // num1과 num2의 GCD를 계산하고 출력
    cout << "GCD of " << num1 << " and " << num2 << " is: " << gcd(num1, num2) << endl;

    // 출력 결과: GCD of 48 and 18 is: 6
    return 0;
}

13. 주어진 문자열이 회문인지 확인

회문(Palindrome)이란, 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 말합니다. 

예를 들어, "level", "radar", "madam"과 같은 단어들은 회문입니다. 

문자열의 길이가 홀수일 때는 중앙의 문자를 기준으로 양쪽이 대칭이고, 

짝수일 때는 완벽하게 대칭인 형태를 가집니다.

#include <iostream>
#include <string> // 문자열 사용을 위해 포함
using namespace std;

// 주어진 문자열이 회문인지 확인하는 함수
bool isPalindrome(const string& str) {
    int left = 0; // 문자열의 왼쪽 시작점
    int right = str.length() - 1; // 문자열의 오른쪽 끝점

    // 왼쪽 인덱스가 오른쪽 인덱스보다 작은 동안 반복
    while(left < right) {
        // 왼쪽과 오른쪽 문자가 다르면 회문이 아님
        if(str[left] != str[right]) {
            return false;
        }
        // 왼쪽 인덱스를 오른쪽으로, 오른쪽 인덱스를 왼쪽으로 이동
        left++;
        right--;
    }
    // 모든 검사를 통과하면 회문임
    return true;
}

int main() {
    string input;
    cout << "Enter a string: ";
    cin >> input; // 사용자로부터 문자열 입력 받음

    // 회문 검사 후 결과 출력
    if(isPalindrome(input)) {
        cout << input << " is a palindrome." << endl;
    } else {
        cout << input << " is not a palindrome." << endl;
    }

    // 예시 입력: "level"
    // 예상 출력: "level is a palindrome."
    // 예시 입력: "hello"
    // 예상 출력: "hello is not a palindrome."

    return 0;
}

14. 주어진 수가 소수인지 판별

#include <iostream>
using namespace std;

bool isPrime(int n) {
    if (n <= 1) return false; // 매개변수가 1보다 작거나 같으면 false
    for (int i = 2; i * i <= n; ++i) {
    // 매개변수의 값n을 i로 나눈값이 0 즉, 나누어 떨어지면 false
        if (n % i == 0) return false;
    }
    return true; // 위의 조건문에 적합하지 않다면 해당 숫자는 소수 이다.
}

15. 주어진 배열에서 중복 요소 제거

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

vector<int> removeDuplicates(vector<int>& nums) {
    sort(nums.begin(), nums.end()); // 먼저 정렬을 진행한다
    nums.erase(unique(nums.begin(), nums.end()), nums.end()); // 중복을 제거한다
    return nums;
}

int main() {
    vector<int> nums = {1, 2, 2, 3, 4, 4, 5};
    vector<int> result = removeDuplicates(nums);
    
    for (int num : result) {
        cout << num << " "; // 1, 2, 3, 4, 5 출력
    }
    
    return 0;
}

16. 문자열에서 특정 단어나 문자를 스위칭

#include <iostream>
#include <string>
using namespace std;

// 주어진 문장에서 특정 단어를 다른 단어로 바꾸는 함수
string replaceWord(const string& sentence, const string& oldWord, const string& newWord) {
    string result = sentence; // 결과 문자열을 원본 문장으로 초기화
    size_t pos = result.find(oldWord); // oldWord의 첫 번째 위치를 찾음

    while (pos != string::npos) { // oldWord가 더 이상 존재하지 않을 때까지 반복
        result.replace(pos, oldWord.length(), newWord); // oldWord를 newWord로 대체
        pos = result.find(oldWord, pos + newWord.length()); // 다음 oldWord 위치를 찾음
    }

    return result; // 변경된 문자열 반환
}

int main() {
    string sentence = "The quick brown fox jumps over the lazy dog.";
    string oldWord = "fox";
    string newWord = "cat";

    // 단어 교체 함수 호출 및 결과 출력
    string modifiedSentence = replaceWord(sentence, oldWord, newWord);
    cout << "Original sentence: " << sentence << endl;
    cout << "Modified sentence: " << modifiedSentence << endl;

    // 출력 결과:
    // Original sentence: The quick brown fox jumps over the lazy dog.
    // Modified sentence: The quick brown cat jumps over the lazy dog.

    return 0;
}