컴공일기 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를 선물하세요.
-
맞팔 ㄱㄱㄱ 9
ㄱㄱ
-
6,9 국어 1인데 12
수능때 4뜰수도 있음? 작년에는 6911 544였음 유튜브보면 맨날 국어는...
-
고령화 시대에 노인 일자리로 메이플 대리 생각해봤음 10
난 메이플은 안하는데 생각해보니 되게 괜찮은거같음 ㅇㅇ초기투자 200만원으로 시급...
-
하루에 네번 32
식사를 하고 여덟번 (똥) 싸고 여섯번의 실모를 쳐줘
-
우리나라 최고의 지식인들이 문제 출제한다는게 진짜 낭만적임요
-
다 올해까지 듣는걸로 돼있네
-
질문받아요 40
해주세요
-
나는 원한다 19
맞팔을
-
07년생인데 질문받음 25
좆반고 2학년 ㄱㄱ
-
질받 받아욤 43
ㄱㄱ 없음 말구
-
50코씩 복사가 된다고?
-
그냥 아무생각없이 써왔는데 혹시 단위원으로 풀면 안되는 경우도 있나요?
-
진로가 다들 보통 어케되심? 남미 시장 쪽으로 진출하시는 분들도 많이 계신가
-
음
-
피자베이글칩 근데 1년에 한번씩감
-
작년에는 추석에 1
시원했던거 같은데..
-
질문받음 13
ㄱㄱ
-
실검 1위 뭔데 2
왜 찐따인데 ㅋㅋㅋㅋ ㅋㅋㅋㅋㅋ
-
바닷가 ㅇㅈ2 4
-
수학 감 떨어졌누
-
찐따든 말든 신경쓸거 머있노 보통 찐따 욕하는애들은 같은찐따거나 어중간한 애들이 더...
-
그 이상 그 이하도 아님 고기 내가 안 구우면 그만이라고? 다른 사람들이 구워주는...
-
바닷가 ㅇㅈ 2
너무 예브네요..
-
시험지나 괴외 문제지, 간단한 개념들 종이로 인쇄해서 학생한테 줄 때 무슨 프로그램...
-
투명인간 취급 받음 앵간해서는 ㅇㅇ 내가 내신 영어 학원에서 16명 중에 나 혼자...
-
건대만 가능한 걸로 아는데 수능 백분위 각각 어느정도 나와야함뇨??
-
수학 질문이요 0
아직 뉴분감 못끝낸 반수생입니다 3분의2정도 했는데 마저 하고 n제 들어가도 될까요?
-
장어다 헤헤
-
오늘 모 장관님 연설문 가지고 연설통역 연습한 1인:) 중간에 실수를 하긴 했지만...
-
남르비들만 22
있으면 먹을건가요?
-
청일점 좀 즐겨보게
-
지금은 8:30정도인데 다들 언제쯤 공부시작함?
-
아수라 과제 꼭 사야하나요? 앱스키마랑 기출 하던거 다 끝내고 들으려면 10월달부터...
-
지금 고2인데 벌써 마더텅 문학 한 권을 다 끝내버렸고 마더텅 독서도 이번해 가기...
-
앞자리가 바뀐다 끼얏호우
-
오류 있다면 알려주시면 감사하겠습니다 +오류가 있어서 다시 업로드했습니다. 아래...
-
이감5-6 79쳐나옴 12
근들갑이 아니라 진짜 국어실력 개박살난거같은데 어캄
-
물리학과 박사과정도 버튜버를 하는 세상이네
-
나쁜놈!
-
본인 반수전에 지잡대 영어회화 동아리 해봤는데 몽골친구가 진짜 발음이 수준급이더군요...
-
라갈비 맛있다 30
배도 불럿으니 슬슬 용돈받는 무빙좀 쳐볼까..
-
문과 기준
-
유튜브댓글보니까 9
여군인식 개안좋네 남인식 신경안쓰고 대학선택하면 무조건 육사인데 다 똑같은...
-
이거 수완실모 1회 11번인데 ㄷ선지가 “크기가” F0인 힘이 한 일을 물었으니...
-
넘 바보같음
-
( 청라 아파트 지하 전기차 화재, 그 이후 25층 화장실 모습 ) 2
지하에서 화재 분진이 25층까지 이렇게 올라올 수 있는거군요.
-
내가 존나 여유롭게 살아보고 내린 결론임 근데 내년 이맘때쯤엔 입시 말고 다른 걸로 바빴으면 좋겠네
-
재업)수학 한 거 19
올려달란 분이 계서서
-
어떤 쌤은 무조건 사람들이 나를 볼 수 있는 탁트인 공간에서 공부하는 게 좋다고...
-
한국 가수였으면 고소먹었으려나 듣다가 갑자기 궁금해짐
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자