컴공일기 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를 선물하세요.
-
어째 날이갈수록 저능아가 되는거같은데 어떡하냐
-
끝났음?
-
다 알고 듣는거 아닌가? 학벌을 숨긴 것도 아니고 왜 논란이지?
-
동전이 아연과 구리의 비율이 35:65인거 알고 계심? 아연 35, 구리 65...
-
'XXX 듣고 1등급 나온사람 없을거다' 이런게 의미가 없는게 0
막상 인증하거나 '저는 잘 듣고 올랐는데요?' 이런글 올라오면 '님은 그거...
-
메신저는 공격하지 말라며...
-
어린 나이에 전자기학 마스터해서 수능 물리학 해강 찍는 미코토가 대단하네 외모도 이쁘고
-
잡다한 팁이나 스킬같은 거는 대황oz 강의가 최고지만 천체파트를 관통하는 가장...
-
국어 > [이감국어 프로그램 시즌4 1] 모의고사 1차 공통, 화작 > [ebs를...
-
의료대란에 대학병원 파견나가는이유가 대한민국을 생각해서? 지역의료를 위해서?...
-
원래 쎈발점 -> 뉴분감 고정으로 쳐내왔는데, 학교 자습시간에 패드 사용이...
-
모두 까기 시대의 막이 올랐다 그런거 할 시간에 문제 풀고 실모보고 애니보고 맛난거 먹는 나
-
이거 딴 부분은 알겠는데 페이지번호 바로 위에 ?? 표시한 각주 부분이요 F(x)랑...
-
밀양 사건과 조두순 사건을 시작으로 조주빈 우울증갤에 변하는 게 하나도 없는 건지 왜 이리 슬픈가요
-
이번에 학과 보단 좋은 대학을 가기 위해 공부를 시작해보려고 하는데 과목마다 선택이...
-
여자들은.. 9
독재에 크롭티는 방해할려고입고오는거지? 심지어 이쁘네..
-
이게 대학생들의 대화가 맞나
-
옯밍아웃!
-
혹시 더운데 3
더위로 땀 흘리고 피로 느끼시는 분 없음?
-
유튜브 하이라이트나 잡도해 맛보기 예전에 들어봤었는데 계속 수강하고 있진 않지만...
-
앱스키마 분량이 너무 많아서 교재만 풀려고 하는데 앱스키마에서 김승리가 추천해주는...
-
슬슬 25지인선 s1 배포한지 반년인지라 불을 지필 때가 온 듯 하네요 ㅎㅎ 9평...
-
심지어 5수 기안대도 그렇게 비난할일은 아님 그런데 3수해서 상위 10%조차 못한...
-
오르비?
-
어디 건가요? 쌤이 주셨는데 궁금합니다
-
왜냐면 지에부터 기다림이 24시간이 넘을 때마다 대가리를 존너 쎄게 쳐서 재...
-
몇분 정도 걸리시나요? 독서 주요지문 3개 남기는데 45분 잡고 이감 푸는데 빡빡하네요 ;;
-
위 식처럼 저는 계산했는데 정답은 아래 식입니다… ㅠㅠ 몇 번을 봐도 왜 틀렸는지...
-
조금 덜 졸린 것 같긴 하지만 큰 차이 없고 살이 너무 잘 빠져서 놀람... 일주일...
-
아 내가 기삼이 출신이었지
-
이번 수능때도 선선해야 할텐뎅..
-
뭐 그럼 만점들만 강사할 수 있고 공부법에 대해 말할 수 있는거임? 그러면 지금...
-
더 이상 지각하면 좆될것같아서 아침에 허겁지겁 뛰어갔더니 아스팔트 위에 엎어짐 왼쪽...
-
1. 표지가 이쁜가 2. 언비져블 섬띵으로 인한 끌림이 있는가 3. 기타 상황
-
이거 아닐까 싶네요… 너무 중요해서 강조하는게 무의미할정도로…
-
넘 비싸서 퀄 애매하면 안사려구요 참고)제 선택과목은 경제 사문입니다
-
2등급 실력으로 1등급 받는건데 이득아님?
-
드릴후에 이해원하는 분들도 있고 이해원후에 드릴하시는 분들도 있는데 4규 끝내고...
-
sky 간 애들 ㅈ빠지게 과외 돌리거나 편돌이 알바 하고 잇을때 그냥 "용돈" 딸깍...
-
수시 박람회 2
이번주 토요일에 저희 지역에서 수시박람회가 열려서 가보려고 하는데 수시박람회는 대충...
-
9평목표 0
국어 화작파트 다 맞기 (문법은 버림ㅋ), 독서 킬러(?)빼고 다 맞기, 문학...
-
어쩨 가면갈수록 배가 너무고픈데 살은안쩌요....
-
아아
-
진짜 미친건가
-
영어가 계속 2등급만 나오는데 시간 부족이 가장 큰 문제 같습니다. 그래서 문제집을...
-
유튭 배민 광고 1
잘가 배달비~~ ㅇㅈㄹ ㅋㅋㅋ
-
사관 수학 이렇게 풀면 안돠나요?
-
불변의 진리 2
어느과목이든 극한의 양치기 하면 2까진 가는 듯 1은 좀 생각을 많이 해야함
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;