컴공일기 247
게시글 주소: https://w.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를 선물하세요.
-
안녕히 주무십쇼 선배님덜~ 전 내일 6시에 얼.버.기 하겠습니다
-
나중에 입을 잘 털어야 해서…
-
그래서 삼-사수생인줄 알았는데 1이 없어... 6자리야... 옾끼야아아아아악
-
나를설레게해 0
너가 해원이형
-
아직 해설 강의 풀린게 없는것 같은데 맞나요?
-
85?
-
공부의욕이 마구 꺾이네요
-
오타니 말이되나 2
51-51뿐만 아니라 오늘 경기에서만 6안타 3홈런 10타점 ㅋㅋㅋ
-
대학붙을 당시 상평영어 96점 1찍고 관악 입성함
-
고3때 3이였음 고3내내 공부해서 2띄우고 재수때 1찍음 님들도 할 수 있슴 근데...
-
오늘 푼 엔제 다맞음 16
수험생활 3년동안 처음이야 기부 좋게 잘 수 있겠군 어서 나를 칭찬하시오
-
제대로 받아주는게 중요하지이 ~
-
가장 병신같은 댓글 1....
-
19도? 갑자기 수능체감되네 수능날씨 뭔데
-
야식 먹어 한 번 먹는다고 살 안 쪄
-
제가 키가작아서 키큰사람이 좋아요<<이말 이상하긴한듯 ..ㅋㅋ 9
평소에는 그냥 그렇구나 생각했는데 자세히 생각하니 제가 못생겨서 잘생긴 사람이...
-
추천 많이들하네 패파파 들을까 원솔멀텍 들을까
-
학점주작은 뭐임 4
씨
-
보이지않는 물웅덩이 피하기 캬
-
도표 <<< 가장 많이 틀림ㅋ 듣기 하면서 풀다가 덧셈 잘못해서 틀리고, 5번...
-
영어 시발 외울게 왜이렇게많아 ㅈ된거같음 수능날 4등급받을거같은데 하 영어가 급방...
-
오늘 취하면 1
오늘 취하면- 수란 이거 노래 좋음 님들도 좋아하는 노래 추천 ㄱㄱ
-
대학가서 학점 잘맞는것도 사회에서 중요할텐데 잘 노는애들이 학점도 잘맞음
-
그냥 생윤 윤사 합쳐서 윤리 한지 세지 합쳐서 지리 세계사 동사 합쳐서 역사 사문...
-
전부 초6 한명에게서 들은 것들. 친구1: 들리는 말로는 남미새 여미새를 뛰어넘은...
-
이미 투투전사 된 시점에서 영어는...
-
하남자들을 위한 물1 : 비역학 근본 물2 : 역학 + 전자기학 + •••
-
생2 벽느낌 0
아직 제효 기출 하는 중이고 코돈은 맛도 안봤는데 이거 시험장에서 못풀겠다..다시 물1로 도망가야지
-
최저떨 정시 이월 & 정시에서 다같이 공평하게 2등급 아 ㅋㅋ
-
주무세요 2
-
한수vs바탕 0
상상 파이널 패키지랑 이감 오프 사서 푸는 중인데 양치기용으로 실모 더 살까...
-
영어 어려워지고 3
영어 열심히하는 사람 늘었을듯... ㄹㅇ 9평도 그렇게 쉽진 않았는데 %가 잘나와서...
-
시간상 한권만 풀수잇을듯,,
-
올 6평처럼 아예 1퍼로 내서 수시이월 노리던가 아니면 아예 12퍼 15퍼로 내던가...
-
그냥 눈떠보니까 11월 15일이었으면 좋겠음 몇달 쉬다가 전과목 처음부터 다시...
-
6월 9월에 같은 단원에서 같은 주제가 나와도 수능에서 노선 변경해서 다른 주제로 내버림,,
-
추특 들엇는데 뭐보내셧길래.. 일단 감사합니다(?)
-
그래야 절평 의미가 있지
-
무려 여기 대학 총장이 지폐에 2명이나 들어있고 총장의 어머니도 지폐 최고액권에 들어가 있기 때문
-
유명한데 방학에 부모님이 의대반 들어가게 한다는데 성적은 댐 전자기기 같은걸 아ㅖ모스고 집에 못옴?
-
20% 또는 0.2% ㅇ
-
길이 엄청 긴 시나리오 핵 투척 독서는 법/경제 아닌 사회 + 과학 + 철학...
-
10퍼 출처:내머릿속
-
제가 일단 실모 풀때 공통에서 22번은 거르고 다 풀어요 근데 제가 공통에서...
-
수학 실모 풀어봤는데 평균 80~84점 정도 나오는데 그냥 실모 계속 풀면 될까요?
-
정법 n제 0
시대인대 엣지인가? 괜찮나요 김용택t 기출예감할지 엣지할지..
-
참고 바랍니다.
-
7~8%가 젤 적당한거 같은데...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자