컴공일기 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를 선물하세요.
-
언미영물지 95 88 98 42 33 언매 전반적으로 문학이 빡빡했고, 철학에서...
-
F들한테 궁금한건데 17
진짜 그냥 그래그래 너 참 힘들었구나 둥가둥가 해주면 기분 좋음? 문제상황이...
-
제 수준은 2024수능 75876 입니다 재수한답시고 깝쳤는데 롤만하며 올해를...
-
(이탈리아어에서)spaghetti는 복수형. 단수형은 spaghetto 비슷하게...
-
나만 어려웠나? 평가원 고정 50 인데 낯선선지 몇개 보이네
-
ㄴ 선지 해결해주실 분 ㅠㅠㅠㅠㅠ
-
10덮 개미쳤네 1
수학 13번: fx식에 대입해야 하는데 Fx식에 대입함 지2 5번: 중력이상 =...
-
이비인후과 장사잘되네 11
앞에 27명있다고? 대기가 한 시간 반이라고?
-
교통사고 났는데 2
나 무면허인데 킥보드 사고남 근데 40만원으로 퉁쳤음
-
17 19 손못댄 2틀에서 17 손못대고 19 절반푼 2틀로 가려면 19를...
-
화미생지 이과입니다
-
100 94 82 30 35 50 ㅋㅋ 언미영한생지 생명 뭐랄까 유전은 쉬운데...
-
현고3이고 정시판 뛰어들기 전부터 언매밀린다 파이널이어쩌구 등 얘기 들아왔지만...
-
10이투스 사문 14
어려웠죠??? 나만어려웠나
-
자극적인 말 한번이라도 언급하는 애들은 곧장 차단해버렸기 때문 ㅇㅇ
-
공부하명할수록 모르겠는 마법의과목 실모는 왜이렇게만드는건지 이해가안됨 아예 못풀게만들어놈 ㄹㅇ
-
서강뱃 특) 5
애기한테 스윗함
-
이감 수학 실모 2
강k보다 쉬운게 맞는거죠?? 강k만 보면 꼬라박는데 이감파이널만 보면 잘 봐서..
-
마더텅이랑 한완기 고민하고잇는데 해설이 한완기가 좋다는 글이 많은데 주변은 다...
-
3월, 4월 중반 걍 눈치보면서 중건에 결석 몇번하면서 꾸역꾸역 나감 5월부터...
-
이명학 커리 타는 중이었는데 리로직에서 늘어지면서 그불구 할 시기가 애매...해짐...
-
수학개념 인강 2
지금 고1인데 선행을 아예안해서 이번에 수1수2 해야되는데 시발점 하려햇는데 양이...
-
국영 3 깔아놓고 쌍윤 11 내신 사탐만큼은 전교1등도 놓치지 않음 (ㅈ반고긴한데...
-
11회인데 아에 도표 건들여보지도 못한채 끝났네요..ㅋㅋㅋㅋㅋ 9 10 11 20...
-
하 10
올해 대학 가겠지 ?
-
탐구가 너무 망했다.. 물리 42 지구 33 아오 진짜 ㅋㅋ ㅠㅠ 지구는 실수...
-
"3년에 한번은 느낌이 와요, 오는데 올해는 ~~~..." 당신 분명 3년동안 ..... ??
-
미적 3등급에서 2등급? 아니면 영어 2등급에서 1등급?
-
푸하핫
-
놀라운 사실) 2
종로 모의고사로도 에피.센츄를 신청할 수 있다
-
부끄럽지만 아직 수학 기출을 풀어본 적이 없는데 4점 기출만 풀어봐도 되나요?...
-
지금부턴 제가 하늘에 서겠습니다~ 제 위에 계신 분들은 모두 내려가주세요~
-
복잡한 문제(개정 이전 문제들)너무 많아서 도표 빼고 일단 다 풀었는데..그래도...
-
하소연좀 하겠음. 화나서 이렇게라도.. 1학기 때 샘한테 정시준비한다고 말씀드리고...
-
화1, 지1 화1은 그래도 난이도 이슈보단 표본이슈가 더 크리티컬한데 지1은 “이걸...
-
10모 1받고 학교 솩쌤이랑 상담을 햇는데 남은 기간 동안 수완 수특 re하시는걸...
-
수학은 기출을 진짜 세세하게 더 팔 거 같고 국어는 내가 너무 미시적?인 독해를...
-
생명 점수변화 3
6모 50 7월례 50 8월례 50 8덮 50 9모 50 10덮 31
-
뭐가 더 이득임?
-
...
-
93점 법지문에서만 두개 나갔네 1컷 81점짜리라던데 그정도 난이도는 아닌듯
-
지금 국어랑 물2가 개JOAT라서 국어는 감 끌올하고 과탐은 하면 지금도 오르는데...
-
could never be read out of A 1. A의 밖에서는 읽힐 수...
-
시대 수학 0
시대 수학이랑 인강이랑 차이 크나요? 강제성하고 할거 따로 안찾아도 된다는점 빼면 딱히 차이없나요
-
5전공은 하지말걸
-
제가 직접 만든 문항 중 가장 어려웠던 것들, 풀어 보면 좋을 것들만 가려서...
-
강k+ 등급컷 0
강케플 등급컷 제공 되나요?
-
확실히 주변에 기숙 들어간 애들이 수능 더 잘보셨어요? 1
하기 나름이란걸 알지만....그래도 궁금하네요ㅠ
-
매운 음식이었으면 좋겠어용
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자