컴공일기 247
게시글 주소: https://orbi.kr/00068916354
회문(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를 선물하세요.
-
수학 N제 0
하사십S1, S2, 드릴4 중에 하나만 더 하고 실모 양치기 갈 생각인데 어떤 거...
-
Prime 수능 스터디그룹 참여 인원을 모집합니다! 128
안녕하세요! Headmaster입니다. 어제 사회·문화 스터디그룹 관련 사전 수요...
-
킬캠, 빡모, 이해원 등등 쉽든 어렵든 70점대를 못 벗어납니다 정신병...
-
라유에게 덕코주는 놀이 하기
-
어쨌거나 공부란 ‘빈 부분을 채우는 것’이 목적이니까… 그래서 저도 과외할 때...
-
시발 좆같네 0
케이스 나누고 그래프 그리면 딸깍인 문제를 ㅅㅂ 어휴
-
부 진 장 강 곤 곤 래 씨발 알리바바햄 믿고잇엇다고
-
확통 0
확통 김기현쌤 아이디어 2회독 어삼쉬사까지 풀었는데 기출생각집 교재가 품절이라...
-
사탐 선택과목 1
안녕하세요 사탐 선택과목을 고민하다가 글 써봐요 그냥 원래 역사 좋아해서 쌍사로...
-
니세코이? 이거 미식이네요
-
나진환은 후기가 별로 많지 않네
-
뭐가 유명한가요?
-
여기서 말하는 메디컬은 한의대랑 약대 한정 개원, 개국할때 엄청난 돈이 필요하니...
-
이번 6모 9모 기출된 단어 모아놓은거 볼 수 있나요? 어디서 볼 수 있을가여?
-
빡모 3-1 미적 30번 이런 문제는 어케 푸는 거지 10
실력 때문일지는 모르겠지만 필연성 ㅈㄴ 떨어지는 것 같은데 흠... 해설지를 봐도...
-
시간 ㅈㄴ 빠르네
-
각설, 안녕하세요 혹시 이창무 선생님 클리어 모의고사 풀어보신분들 있나요??...
-
틀린문제 다시 풀면 또 틀릴텐데 그냥 오답하고 버리고나서 다른문제 더 많이푸는게...
-
저메추 부탁
-
역학은 ㄱㅊ은 전자기부터 외계어파티임 그냥 눈이 받아들이기를 거부함
-
Fait 0
-
제가 재수학원(시대인재아님) 을 다니는데 거기다가 지금 국어 수학 시대 단과를...
-
9평도그렇고 식센모 오늘 본것도 그렇고 16부터 푼건 많은데 맞은게 적음....ㄹㅇ...
-
천안문 당하지 않는 건지 수능 전에 확실히 말씀해주시면 좋을 거 같습니다 수능...
-
고속 시대인재 0
검정고시
-
13,29틀 29는 1/2빼먹은거 주의해야하고 13은 나만 어렵나...? 모킹버드...
-
평가원은 항상 모두의 뒷통수를 때려왔었지
-
ㄹㅇ뭔뜻임:(
-
이거 끝내고 수1 해야 하는구나
-
자신의 노래가 이렇게 쓰일 줄은...
-
유독 순서 유형만 감이 안오고, 해석풀이를 봐도 납득이 안가는 게 많아서 확실히...
-
그냥 자기전 폰 좀 보다자고 아침에 일어나면 폰 쉬는시간마다 폰 너무 중독임 ..
-
여긴 패션시티 4
~~~
-
아 현타온다.. 12
공부하면 할수록 멍청해지는 기분
-
인데 은근 있는듯 기하러가 투과목하면 지2 많이 하는데 지2러가 투투러면 물2를 많이 함
-
김승리 ㄹㅇ 광기에 가득차있네…….
-
핑크바지 샀다 0
내눈에만 개이뻐서 만족
-
금테제한인 이유 0
많른 팔로워들과함께 조리돌림이 가능하기때문 따흑.,,
-
힘도없고 머리도 멍하고 온몸이 다아프고 하루가 다르게 몸이 병들어가는걸 보니 수능...
-
둘 다 합격하면 어디 가시나요?
-
억울하네 3
옯창이면 과외모집 허용이라고?
-
내가 출제자라면 4
올수능 삼도극 무등비 낸다
-
걍 시험지에 글자 너무 많고 풀이공간은 너무 좁고 고이다 못해 썩어서 컷은...
-
풀때마다 40번 틀리는데 ㅅㅂ 뭔 문학처럼 허용가능성 따져야됨 5선지 다...
-
148
-
시즌1 1회만 풀어봤는데 미적 80점 나왔어요 빡모 시즌2 랑 비슷하거나...
-
ㅇㅇ..
-
중철 표기인 것심
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자