[Algorithm] 팰린드롬 알고리즘 - 문자 대칭

1. 팰린드롬

ex1> 

앞에서 읽으나 뒤에서 읽으나 똑같은 단어(회문= 팰린드롬), 

문자열을 입력 받아서 입력된 문자가 팰린드롬인지 아닌지 여부를 확인하는 함수를 작성하라. 

(입력된 문자열이 팰린드롬이면 true 를 리턴하고, 아니면 false 를 리턴해야한다.) 

 

c>

/Users/kim-yunhee/CLionProjects/uni_study/cmake-build-debug/uni_study

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int isPalindrome (char* inputStrig);

void main (int argc, char** args){
    int result;

    if(argc<2){
        printf("Usage: palindrome inputString \n");
        return;
    }
    result=isPalindrome(args[1]);

    if(result){
        printf("it is palindrome \n");
    }
    else{
        printf("is is NOT plindrome \n");
    }
}

int isPalindrome (char* inputString){
    int index;
    int length=strlen(inputString);
    int testEndingIndex=length/2;

    for(index=0;index<testEndingIndex;index++){
        if(inputString[index] != inputString[length-1-index]){
            return0;
        }
    }
    return1;
}

 

Run-Edit Configurations-Program arguments

입력: madam / 출력: it is palindrome

-> 

실행은 잘 되지만 효율성을 따져봤을 때,

 

효율성 해결1>

for 루프 내부에 존재하는 if 조건문을 보면,

루프가 반복될 때마다 비교하는 문자의 위치를 

입력된 문자열의 맨 끝에서부터 왼쪽으로 한 칸씩 옮기는 계산을 수행.

                              length-1-index

다시 말해, 적어도 length-1 은 for 루프 바깥에서 미리 수행될 수 있기 때문에 그렇게 하는 것이 조금이라도 효율적.

 

효율성 해결 2>

수학적 관찰

컴퓨터 학자 그루엔버거의 알고리즘

 

1. 숫자를 아무거나 고른다.

2. 그 수를 뒤집어라.

3. 두 수를 더한 결과가 팰린드롬이 아니라면2로 되돌아가 동일한 과정을 반복/ 팰린드롬이라면 알고리즘 종료.

 

ex> n=19,

19 + 91 = 110

110 + 011 = 121 -> 팰린드롬이므로 알고리즘 종료

 

-> 그러나 196알고리즘(196문제) 

: 그루엔버거 알고리즘을 반복해서 실행하다 보면 수의 크기가 점점 빠른 속도로 증가-> 저장 가능한 비트의 단위를 뛰어넘음-> 커다란 수를 저장할 수 있는 특별한 알고리즘을 동원하지 않으면 계산 진행 불가

 

공간, 시간 둘다 중요

 

출처. 누워서 읽는 알고리즘(임백준) 

/ argv 인자 입력 실행 https://morecode.tistory.com/m/160