컴공일기 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를 선물하세요.
-
42 43 나오는데 1컷이 44… 멘탈 나가는데요
-
저 궁금한게 생겼는데 잠깐 얘기 가능하신분 있나요? 1
정시수학 관련해서요. . . 삐약이라서 정보얻을곳이 없어요 ㅠ
-
다들 어디간거야
-
동생 중간이라 얘네 학교 시험문제 어떻게 나오는지 3개년(6학기정도) 기출 봤는데...
-
왜냐하면 이제부터 기다림이 24시간을 기다릴 때마다 대라기를 존나 쎄게 내리쳐서 제...
-
11월부터는 휴강이고 2주정도 수업 남았는데 그냥 수능 전까지 가지 말까요 수능...
-
시즌1,2 있는데 현강 다닐 때 무료배포 해주셔서 받아놓고 유기함 1,2나 3,4나 차이없나요?
-
ㄹㅇㅋㅋ
-
식센모 파이널 0
식센모 파이널 화이트 1회 44 블랙 1회 41 진짜 식센모도 어렵긴 하네요….
-
2017학년도 수능 국어에 나오는 반추동물 소화, 반추위 산성증 배움 지금 중간고사...
-
ㄹㅇ로 그 악플러 새끼 근성 하나는 개쩔어서 본 받을 만함 88년생이나 되가지고...
-
본인은 이번에 여기까지 가면 딱 털고 끝낸다 어디임? 5
난 고대공
-
몇 점 정도 나오시나요
-
죽엇다고 들은거같은데 폭발원리를 물어버리네...
-
에휴
-
듣기도 평가원 중심으로 공부하는게 나음? 아니면 듣기는 쉬워서 아예 차이없나
-
이번 10모때는 영어 98 나왔는데 오늘 이명학 파이널 푸니까 74점 나오네요.....
-
맞짱까면 누가이김
-
수능이 가까워질수록 공부 더 열심히 할 줄 알았는데 반대로 공부하기가 더 싫어지는...
-
지금 강기분 듣고 있는데 넘어가면 국어 누구 듣는게 좋음??
-
내년 수능 ㄹㅇ 조댄듯 심지어 의대증원철회여파로 오히려 상위권 대학 정원은 줄어들지도 모르는데
-
딸딸이 7
-
영어 도표문제 정답을 1번으로 낸다면 오답률이 몇퍼정도 올라갈까 0
과연 궁금해진다
-
물2 현정훈 없으면 곤란한데 화2로?
-
내 친구가 위에 말한대로 런치고 싶다 햇는데 얼굴에 주먹 내리꽂을뻔 물리랑 미적...
-
2024 기출 중 가장 어려웠던 2문제 뽑아 봤어용! 시험시간은 90분이고 총 7문제입니다
-
실제 지원 저 이후로는 의미 없는 것 같아서 저기서 자름 전글 환장하는 진학사 그래프 참고
-
50일수학 질문 0
50일수학 3회독중인데 너무 오래걸려서 심각한데 현재 5번 풀어도 안풀리면 해설...
-
ㅇㅇ
-
배성민쌤처럼 여러풀이 말고 하나로만 풀어주는강사있을까요??
-
체한 것 같앙…
-
답은 좋은 남자랑 결혼하는 것 뿐인가..
-
체기가 가시지를 않네... 이정도면 이미 유럽에 도착하고도 남았을듯
-
윤사 사문 달린다 올해는 글렀다
-
투과목 뭐하지 9
시대라이브 현정훈끼고 물2 인강으로 지2 해볼까요
-
생윤 개념을 먼저끝내고 사문을 할지 개념 병행을 할지.. 뭐가 더 나을까요 최근...
-
이번 고2 10모로 내가 국어 왜 안나오는지 알아버림 0
여태껏 지문이랑 선지를 너무 과하게 해석하고 푸는 경우가 너무 많았음 그러니까 분명...
-
9모는 화작 100 (1) 기하 84 (3) 영어 4 정법 2컷 사문 2컷 이랬는데...
-
참… 혼자 정시 준비한답시고 고1부터 틈틈이 오르비 들락날락하면서 고군분투하던...
-
그냥 쓱 둘러봤는데 왜캐 역하지 뭔가 이상하리만큼 권위주의와 천민자본주의에...
-
10모 공통 수학 후기 남겨보겠습니다 다양한 의견 부탁드려요 1
1-15번 너무 익숙하고 기출변형 냄새가 많이 나서 올해 모고 중 가장 쉬운...
-
동생 문과인데 2
대성패스사게해야겠다
-
대성 수학 2
수학 5등급에서 4등급 왔다갔다 하는데 대성 수학 인강쌤 추천해주세요
-
1-3. 독서론 4-7. 경제, 오버 슈팅 8-11. 기술, 어라운드 뷰...
-
별로 못했네...
-
6,9모 백분위 79 76 나왔는데 수능때 높3까지는 받고 싶습니다. 지금은 빡모...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자