[백준/C++] 10988(팰린드롬인지 확인하기) (단순 인덱스 비교 / 캐시 최적화 / reverse() / deque / 투 포인터 / 재귀)

https://www.acmicpc.net/problem/10988

 

---

 

내가 해냄 : 단순 인덱스 비교 방식

#include<iostream>
using namespace std;

int main()
{
    // 문자열을 입력받는다.
    string s;
    cin >> s;

    // 문자열의 길이를 변수에 저장한다.
    int len = (int)s.size();

    // 문자열이 팰린드롬인지 확인하기 위해 절반만 검사한다.
    for (int i = 0; i < len / 2; i++)
    {
        // i번째 문자와 (len-1-i)번째 문자가 다르면 팰린드롬이 아니다.
        if (s[i] != s[len - 1 - i])
        {
            // 팰린드롬이 아님을 의미하는 0을 출력하고 프로그램을 종료한다.
            cout << 0;
            return 0;
        }
    }

    // 모든 비교를 통과하면 팰린드롬이므로 1을 출력한다.
    cout << 1;
    return 0;
}

 

사용한 핵심 개념

// 단순 인덱스 비교 방식

• 문자열의 앞쪽(s[i])과 뒤쪽(s[len - 1 - i])을 직접 인덱스로 접근하여 비교한다.
• 반복문을 문자열 길이의 절반(len / 2)까지만 실행하여 비교 횟수를 최소화 하였다.
• 만약 하나라도 다르면(대칭이 깨지면) 즉시 0을 출력하고 종료 (`return 0;`)하여 추가적인 반복을 배제한다.
• 모든 비교를 통과하면 팰린드롬이므로 1을 출력하고 함수를 종료한다.
• 투 포인터 방식과 비슷하지만, 두 개의 포인터를 따로 선언하지 않고 인덱스를 직접 계산하여 접근한다.

 

---

 

AI 피드백 : 캐시 효율 증가

#include <iostream>
using namespace std;

int main() {
    // 문자열 입력
    string s;
    cin >> s;

    int len = (int)s.size();
    int half = len / 2; // 미리 계산하여 반복 조건을 줄임

    // 팰린드롬 검사
    for (int i = 0; i < half; i++) {
        char front = s[i], back = s[len - 1 - i]; // 변수에 저장하여 캐시 효율 증가
        if (front != back) {
            cout << 0;
            return 0;
        }
    }

    cout << 1;
    return 0;
}

 

주요 최적화 내용

 

// 반복문에서 반복 조건 계산 줄이기

• `len`을 반복문 내부에서 계속 참조하는 대신, 미리 `half = len / 2;`를 계산하여 반복 시 불필요한 연산을 줄인다

// for 문 내부에서 변수를 미리 선언하여 캐시 최적화

• 루프 안에서 `s[i]`와 `s[len - 1 - i]`를 매번 접근하는 대신, 한 번 변수에 저장하여 CPU 캐시 효율을 높일 수 있다

 

 

루프 내부 변수 선언을 통한 캐시 최적화란?

// 기존 방식

for (int i = 0; i < len / 2; i++)
{
    if (s[i] != s[len - 1 - i]) // 매번 s[i]와 s[len - 1 - i]에 직접 접근
    {
        cout << 0;
        return 0;
    }
}

• `s[i]`와 `s[len - 1 - i]`를 매번 직접 배열 인덱싱하여 비교하는 방식이다.
• 문자열 s의 메모리 주소를 반복적으로 참조하게 된다.
• CPU 캐시에서 데이터를 불러오는 과정이 반복되므로 성능이 미세하게 저하될 수 있다.

 

// 캐시 최적화를 적용한 방식

for (int i = 0; i < len / 2; i++) {
    char front = s[i], back = s[len - 1 - i]; // 변수에 저장하여 캐시 효율 증가
    if (front != back) {
        cout << 0;
        return 0;
    }
}

• `s[i]`와 `s[len - 1 - i]`를 변수(`front`, `back`)에 한 번만 저장한다.
• 이후 메모리에서 불러오는 대신 변수로 비교하므로 캐시 효율이 증가한다.
• CPU가 필요 없는 메모리 접근을 줄이게 되어 성능이 미세하게 향상된다.

 

// 캐시 최적화의 원리

• CPU 캐시(Cache)란?
  • CPU는 데이터를 빠르게 읽기 위해 캐시(Cache)라는 작은 고속 메모리를 사용한다.
  • 하지만, 캐시에 없는 데이터는 RAM에서 불러와야 하고, 이는 상대적으로 느리다.
• 배열 접근과 캐시 미스(Cache Miss)
  • 배열 인덱스를 여러 번 참조하면, 해당 데이터가 캐시에 없을 가능성이 높아진다(캐시 미스 발생).
  • 따라서 반복문 안에서 동일한 값을 여러 번 참조하는 경우, 변수에 저장해두면 캐시 접근을 최소화할 수 있다.
• 변수를 활용한 최적화 효과
  • `s[i]`와 `s[len - 1 - i]` 값을 미리 변수에 저장하면 CPU가 캐시에서 빠르게 값을 읽을 수 있다.
  • 메모리 접근 비용을 줄여 성능이 향상된다.

 

// 성능 차이 분석 (실제 적용 효과)

방식	메모리 접근 횟수	CPU 캐시 최적화 효과
기존 방식	O(N) (반복문마다 s[i]와 s[len-1-i]에 접근)	낮음
변수 저장 방식	O(N) (한 번만 배열 접근 후 변수로 비교)	높음

• 기존 방식과의 성능 차이가 크지 않지만, CPU 캐시 미스를 줄이려면 변수에 저장하여 비교하는 것이 더 효율적이다.
• 고성능이 중요한 환경에서는 이런 작은 최적화들이 누적되면서 차이를 만들 수 있다.

 

---

 

또 다른 풀이 1 : `reverse()` 이용

• 문자열을 뒤집어서 원본 문자열과 비교하는 방식이다.
• C++의 reverse() 함수를 사용하여 빠르게 문자열을 뒤집고, 원본과 비교하면 된다.

#include <iostream>
#include <algorithm> // reverse() 함수 포함
using namespace std;

int main() {
    string s;
    cin >> s;

    string rev = s; // 원본 문자열을 복사
    reverse(rev.begin(), rev.end()); // 문자열을 뒤집음

    cout << (s == rev ? 1 : 0); // 원본과 비교하여 출력
    return 0;
}

// 장점

• 코드가 매우 간결하고 직관적이다.
• STL을 활용하여 가독성이 높아진다.

// 단점

• 문자열을 복사하는 과정에서 O(N)의 추가적인 공간이 필요하다.
• `reverse()` 연산도 O(N)이므로 시간 복잡도가 O(N)으로 동일하다.

---

 

또 다른 풀이 2 : `deque`(덱)를 이용한 풀이

• deque(덱)를 사용하여 문자열을 앞뒤에서 비교하는 방식이다.
• 덱은 양쪽에서 데이터를 추가 및 제거할 수 있는 자료구조이며, 이를 활용하면 투 포인터 방식처럼 앞과 뒤를 비교하면서 값을 제거하는 방식으로 풀이 가능하다.

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

int main() {
    string s;
    cin >> s;
    
    deque<char> dq(s.begin(), s.end()); // 문자열을 덱에 저장

    while (dq.size() > 1) { // 덱의 크기가 1보다 클 때까지 비교
        if (dq.front() != dq.back()) { // 앞과 뒤가 다르면 팰린드롬 아님
            cout << 0;
            return 0;
        }
        dq.pop_front(); // 앞 문자 제거
        dq.pop_back();  // 뒤 문자 제거
    }

    cout << 1; // 팰린드롬이면 1 출력
    return 0;
}

// 장점

• 덱을 활용하면 큐와 유사한 방식으로 앞뒤를 제거하면서 비교할 수 있다.
• 직관적으로 앞과 뒤에서 접근하는 방식이 명확하다.

// 단점

• 덱을 생성하는 과정에서 O(N)의 추가 공간이 필요하다.
• `pop_front()`와 `pop_back()`이 실행될 때마다 오버헤드가 발생할 수 있다.

---

 

또 다른 풀이 3 : 투 포인터(Two Pointer) 이용

투 포인터(Two Pointers) 방식은 두 개의 포인터(left, right)를 사용하여 비교하는 방식이다.

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;

    int left = 0, right = (int)s.size() - 1; // 두 개의 포인터 설정

    while (left < right) { // 두 포인터가 교차하기 전까지 반복
        if (s[left] != s[right]) { // 대칭이 깨지면 팰린드롬이 아님
            cout << 0;
            return 0;
        }
        left++;  // 왼쪽 포인터 이동
        right--; // 오른쪽 포인터 이동
    }

    cout << 1; // 팰린드롬이면 1 출력
    return 0;
}

 

투 포인터 방식의 장점

// 가독성

• `left`와 `right` 두 개의 포인터를 사용하므로, 코드의 흐름이 명확하다.
• 기존 코드에서는 `s[len - 1 - i]`처럼 인덱스를 직접 계산해야 했지만, 여기서는 두 개의 포인터가 이동하면서 비교하므로 논리적으로 직관적이다.

// 다양한 문제 해결에 적용 가능

• 투 포인터 방식은 문자열 비교뿐만 아니라, 정렬된 배열에서 특정 값을 찾는 문제, 두 개의 배열을 합치는 문제 등 다양한 곳에서 활용 가능하다.
  • ex) 정렬된 배열에서 특정 합을 가지는 두 수를 찾는 문제(Two Sum)

// 성능 향상 가능성

• 기존 코드와 시간 복잡도는 동일하지만, 특정한 경우에는 캐시 효율이 증가할 가능성이 있다.
• 캐시 미스를 줄이기 위해 두 포인터를 사용하면 배열을 순차적으로 탐색하므로 공간 지역성(Spatial Locality)이 더욱 극대화된다.

 

---

 

또 다른 풀이 4 : 재귀(Recursion) 이용

 

• `isPalindrome()` 함수를 재귀적으로 호출하면서 앞과 뒤의 문자를 비교한다.

 

#include <iostream>
using namespace std;

bool isPalindrome(const string &s, int left, int right) {
    if (left >= right) return true; // 기저 사례: 모든 문자가 일치했을 경우
    if (s[left] != s[right]) return false; // 문자가 다르면 팰린드롬 아님
    return isPalindrome(s, left + 1, right - 1); // 재귀 호출
}

int main() {
    string s;
    cin >> s;
    cout << (isPalindrome(s, 0, s.size() - 1) ? 1 : 0);
    return 0;
}

 

// 장점

• 재귀 호출을 활용하여 다른 문제에도 쉽게 응용할 수 있다.

// 단점

• 재귀 호출이 많아지면 스택 오버플로우(Stack Overflow) 위험이 존재한다.
• 반복문보다 성능이 떨어지며, 비효율적인 메모리 사용이 발생할 수 있다.

---

 

 

(맨 아래부터) 단순 인덱스 비교 / 캐시 최적화 이용 / reverse() 이용 / deque 이용 / Two pointer 이용 / Recursion 이용

 

간단한 문제였는데 생각보다 다양한 풀이 방법이 있어서 흥미로웠다.