컴공일기 247
회문(Palindrome).
우영우 기러기 12321과 같이 대칭적인 문자열을 일컫는데,
주어진 문자열에서 범위를 설정하고, 그 범위 내 부분문자열이 회문인지를 검사하는 알고리즘입니다.
우선 완전 탐색을 해야하는 상황이고, 전체 SIZE가 2000 정도로 시간복잡도에 대한 부담감이 없는 상황이네요.
또한 회문 알고리즘의 특성 상 점화 관계를 이용해야 하기 때문에 Dynamic Programming 기법으로 구하는 것이 합당하다고 보여집니다.
아래는 C++로 구현한 코드입니다. 정답이네요.
오랜만에 왔는데, 방금 푼 코드나 올리고 도망가겠습니다. 안녕히 주무십쇼.
#include <iostream>
#define SIZE 2001
using namespace std;
int isPalindrome[SIZE][SIZE];
int arr[SIZE];
int N; //수열의 크기
int M; //질의 개수
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> N;
// 편의상 index는 1부터 시작
for(int i = 1; i <= N; i++)
{
cin >> arr[i];
}
// 길이 1인 부분 수열은 항상 회문
for(int i = 1; i <= N; i++)
{
isPalindrome[i][i] = 1;
}
// 길이 2인 부분 수열 판단
for(int i = 1; i <= N - 1; i++)
{
if(arr[i] == arr[i + 1])
{
isPalindrome[i][i + 1] = 1;
}
}
// 길이 3 이상인 부분 수열에 대한 회문 판단
for(int length = 3; length <= N; length++) // 부분 수열의 길이
{
for(int i = 1; i <= N - length + 1; i++) // 시작 인덱스
{
int j = i + length - 1; // 종료 인덱스
if(arr[i] == arr[j] && isPalindrome[i + 1][j - 1] == 1)
{
isPalindrome[i][j] = 1;
}
}
}
// 질의 처리
cin >> M;
for(int i = 0; i < M; i++)
{
int S, E;
cin >> S >> E;
cout << isPalindrome[S][E] << "\n";
}
return 0;
}
0 XDK (+0)
유익한 글을 읽었다면 작성자에게 XDK를 선물하세요.
-
오직 막연한 사이만 있을 뿐이다
-
국어 실모 0
이감 밖에 풀어본 적 없는데 상상이랑 이감 중 뭐가 더 나은가요? 비슷비슷한가요?
-
서울대 인문계열 입학 vs 세무사 자격증 획득 무엇을 선택할 것인가요?? 진짜 궁금하네요
-
꼬기 등장 3
나 취해써
-
아가취침 6
1교시 ㅋㅋ
-
내신 2.5 2
내신 2.5 인서울 적정권이 어디인가요??? 생기부는 평범하다는 가정하에 알려주세욥
-
맞아도 되나여 딴건 1컷 수준에 국어 백분위 98이상은 나오는데
-
메가나 19패스 보통 언제쯤 나오나요?
-
오르비는 성비가 3
어케 되나요 걍 궁금해서요
-
수리논술 어케 나오나요?? 작년에 냥대 안 써서 잘 모르겠음여... 통통이고 수학...
-
책이 안팔려 4
누군가 좀 사줘요ㅠㅠ 아예 가격을 더 낮게 불러야하나
-
3급 고졸인데 갈 수 있으면 무조건 가는 게 좋음? 대학 갈지 말지 고민임
-
신창섭을 모욕하는 넌 그냥 리
-
요즘 게임하던 시간까지 끌어와서 커뮤 눈팅 많이하는듯 버릇이 돼서 고칠수가 없네요...
-
경기대 영어영문학과 KGU학생부종합전형한국외국어대학교 글로벌캠퍼스 융합인재대학...
-
강제기상은 시러,,
-
한번더 치셔야하거나 지금 고2들은 수능끝나고 연락주세요
-
한약학과 3
실시간 인기 검색어 1위 이건 ㄹㅇ 처음인것 같은데요?ㅋㅋㅋ
-
문제 계속 풀고 복습하면서 체화하는 방법 밖에 없나요,,,,, 매번 볼때마다 새로운 느낌이 드네요ㅜ
-
오늘의공부 2
국어2지문 영어 5지문+실모+수업 수학 숏컷 15문제+실모 사문 실모 한지 노트 복습
-
제목이 곧 내용입니다 너무 셀프로 신상 공개하는 거 같으면 조금 넓은 영역도 좋아요...
-
요즘 왜 인증메타 없음 ㅠㅡㅠ
-
친구중에 2.6으로 고대, 서강, 중앙, 경희, 시립, 건국 쓴 얘 있었는데 고대...
-
92점………. 미적분 ㅂㅅ실력 재등장 공통 50분정도 걸렸고 나머지 미적분 영혼까지...
-
수능볼때까지는 0
어떤 생각도 없이 그냥 공부만 해야겠다 수능 이후엔 그냥 혼자 길거리 배회나 해야지 암..
-
이메일 딱히 필요없었던거 같은데 괜히 찜찜합니다 내일 유웨이나 입학처로 연락 드리면...
-
내신은 과탐했고 수능은 사탐 치는데 수시로 경영 논술지원 가능함?
-
경외시 다 1호선인데 1호선이 악명이 워낙 높잖아요 통학하다 대중교통때문에...
-
작년수능 기준으로 설의 문 닫는 성적이 어떻게 되나요? 언 미 화 생 1 기준으로...
-
강x 이감 빼고 없나용 96이 보고싶은데 서바강k좃같음 ㅜㅜ
-
하
-
퇴근 6
너무 힘드러
-
수학 1등급대가 수리논술 준비 잠깐 바짝하면 붙는 경우 꽤 많나요 쓰긴 했는데...
-
ㅅㅂ 눈물난다
-
핀셋 넘모어렵다 0
대가리가깨져
-
고경영논 드가자 0
아빠 후배가 되어봅시다
-
07자퇴생 9평 20
07년생인데 이정도면 오르비식노베 가능한가요?
-
ㅜㅜ 입학처에서 못찾겠어요
-
기운이없다 3
캠퍼스라이프 러쉬 저번주에 끝나고 다시 씹아싸복귀함. 오랜만에 학식혼밥으로 다시복귀...
-
고논 써 말어 1
하 고민이네 높은 확률로 돈 낭비이기는한데...
-
수시원서 2장. 3
고려대논술 모 학과 경한인문 끗
-
오전 8시 30분 성균관대 공대 수리논술 오후 12시 30분 고대 자율전공 인문논술...
-
서성한 중경외시 그 어디쯤인가요?
-
인문계열(4합8) 경쟁률 몇이나 될까요
-
나름 지방 고등학교 중 공부 좀 하는 지방 일반고 내신 2.1임. 주요교과로 하면...
-
6논술 하려고 했는데 너무 쫄려서.... 하나는 교과로....
-
김상훈t 듣다가 파이널만 아수라 들으려는데 아수라하면서 유네스코 옛기출+수특 독서 병행 가능할까요?
-
전자기학 암튼그래요 나만 이 파트 못해..
-
다들 파이널기간 국어 화이팅!!
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자