컴공일기 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를 선물하세요.
-
신 1
-
재수하면서 인스타 끊으니까 정신에 너무 좋아서 대학가고나서도 쭉 안하려고 하는데...
-
ㅇㅈ 9
사진 남는거때매 링크로 대체함 https://bit.ly/4gCN92q
-
이제 좀 무서움
-
3등급대인데 N제는 n티켓밖에 안풀어봣고 킬러들 맞히는거보단 계산실수줄이고 시간내에...
-
오늘부터 아수라 개강이던데 김승리 현대시,고전시가 좋나요?? 독서는 도움 많이...
-
즐거운 한가위 쇠셔요
-
인증을 어케함 6
무서워서 못함 ㄹㅇㅋㅋ
-
캬 은테됐다 11
진정한 옯창이 되어버렸다 이말이야~~
-
살자 0
자살 할복
-
ㅇㅈ 36
초딩 19 18 20
-
이때를 틈타 10
맞팔9
-
잘생기면 열등감에 화나고 아니면 빨간약 먹은 것 같아서 화남 탈갤
-
저 본계로 60개 공스타로도 50개는 팔로우하는듯 옯스타 본계로 팔로우 건것도 좀잇슴...
-
22 DK 양대인 vs 딸깍조합 5꽉의 신 대대대
-
디시펌
-
난그럼두개ㅇㅈ 7
유전..!
-
남자애들은 돈 제외하고 먹을 거 주는게 베스트에요?
-
부산대 나노메카 왜 입결이 낮은건가요? 4년동안 장전캠에서 수업 듣는걸로 알고있는데...
-
씹덕이라 애니/만화 계정 팔로우를 벅벅
-
추석에 유아인·김호중 구치소서 뭐 먹나…점심 수제비, 저녁 곤드레밥 4
'마약 혐의' 배우 유아인(38·본명 엄홍식)과 '음주운전' 가수 김호중(32)이...
-
팔로워는 걍 초중고 잘 나왔으면 200은 되던데 다들 6
많은 친구들은 한 400? 저도 250언저리임
-
초성부터 여자임
-
ㅇㅈ 10
-
ㅇㅈ 4
대충 얼굴 하관 가리고 눈만 있는 사진
-
성형 안해도됨 3
오프라인의 인간관계를 버린다면 성형 할 필요 업슴
-
평소에 뭐 찐따니 아싸니 하면서 뭐 인스타 팔로워 100 미만은 조용한 사람????...
-
ㅇㅇ
-
???????? 아 화나네 나도 이쁜사람 인증 보고싶다고
-
ㅇㅈ 3
유전
-
진짜 ㅈㄴ어려운데 어려운 거 맞죠?
-
ㅇㅈ 7
-
재밌습니다
-
수1수2는 문해전 시즌2 , 확통은 n티켓 시즌2 듣고 있는데 수1은 정답률...
-
할머니 댁에 공유기 설치 좀;;
-
남자들이 솔선수범해서 몇명 인증하고 분위기 띄우면 예쁜 여르비들이 인증했는데
-
이제 네이트온 버디버디가 틀딱 카카오스토리가 정상범주
-
한 번 써보고 싶은데 갤럭시는 공기계로 둬서 필요할 때 쓰고... 바꿀 때 장점이 뭐가 있을까요?!
-
SNS메타 뭔데 6
롤 메타로 가자
-
송하영 2
개귀엽다…
-
06 현역도 나이 많이 먹었다고 생각해요 이제 다 노인들이야..
-
시즌2여… 전 50분으로 ㄹㅇ 안되겠던데
-
양승진쌤 시공사 수준정도 n제 뭐가 있을까요?? 수능전 마지막 수학 엔제 하나 더...
-
라고 하면 안 되겠죠?
-
문상으로 도토리 사서 꾸미고..
-
난 페북세댄데 2
콕 찌르기<<<<GOAT
-
언미사탐으로 되나요?
-
이거 신고하면 정지시킬 수 있나요? 생윤 지피티답변은 너무 무책임한 것 같은데,,...
-
인스타도 시작한 지 얼마 안 돼서 굳이 의미 부여할 필요를 못 느끼겠음
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자