컴공일기 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를 선물하세요.
-
근데 짜피 얘네 내년에 다 빠지겠죠..?
-
어디쯤 갈 수 있을까요? 심리학부로 가고싶은데
-
통통기준 21 22 29가 많이 어려운데 21,29 꾸역 풀었더니 22는 거의...
-
쿄우노 츠키와 4
토테모 키레이 데스네...
-
2024년 10월 교육청 난이도 3.5 퀄리티 **** 시험 구성 **** 등급컷...
-
두 학교 학과 동급이란 건 알아요 선호하는 학교학과를 골라주시고 학교학과 이름 or...
-
삼반수라 짧지 않은 시간인 건 아는데 성적이 정체기라서 너무 힘드네요… 그래도...
-
한 -> 영 번역이 안 돼서 그럼 우리는 12년동안 영 -> 한 번역만 배웠고...
-
다음주부터 고3은 수능 시간표대로 해준다는데 이런 학교 많음? 사실 난 일찍 보내주면 좋겠는데
-
어차피 난 애플쓴다
-
서킷X 15회 0
9,10번 풀고 ㅈㄴ 어려워지는데 이거 맞냐... 3따리인데 희망이...
-
Top 30까지가 사실상 연구기능이 제대로 돌아가는 곳이라네요 서울대 연세대...
-
항상 한자문을 못풀고 끝나노 원래는 푼것도 틀리는데데이번 10모때 푼건 화작...
-
현재 지거국 1학년 재학중인학생입니다 저같은경우는 초중고 수도권 대학만 지거국인데...
-
10모 국어 4 영어 4 -> 수능 국어 2 영어 3 ㄱㄴ? 4
국어는 4 문열고 영어는 늘 그렇듯 30~40 사이 문제 빼고 다 맞춤 국어 ㅅㅂ...
-
김준이 어렵단 회차는 쉽고 안어렵단회찬 존나어려움 뭐임?
-
군수생 달린다 9
오늘 달 엄청 밝네요...
-
그치만 탐나죠?
-
수학은 일단 김범준 런칭 이정환 복귀 확정 더 올지는 모름 국어는 박광일 복귀 거의...
-
1학년 총합 5.9 2학년 1학기 6.5 그리고 지금 2학기는 수행평가랑 시험다...
-
아아빼고
-
대범준 캬
-
독서 ebs 복습 / 문학 ebs(수특 고전소설 02, 현대시 01)설맞이 시즌1...
-
이분은 왜 혼자 실루엣 처리가 안 되어 있나요?
-
수능 날 아픈 상태면 수능 망할 가능성 높다는 건 다들 말 안 해도 아시죠? 공부도...
-
11~12월쯤 물1 무료 그룹 과외를 해볼까 합니다 1
교재 : 피직솔루션 범위 : 운동역학 기본+심화 기간 : 6~8주 예상 피직솔루션은...
-
전부 비연계라고 가정하더라도 왜 등급컷이 비슷할 것 같죠..?? 약간 그냥...
-
지듣노 1
에휴이 이제 공부해야지
-
아직 앱 안 되는 거 맞죠?
-
하루 12~13시간씩 꽉꽉 채워 하고 사람 만나는거 좋아하는데 카톡도 지우고 아예...
-
계산을 적당히시켜야지..
-
죽을것 같아요 1
수능 28일 정도 남은 것 같은데 혈당 수치 높아지고, 소화 안되고, 머리 아프고...
-
6,9월 보니깐 소설 내용은 둘째치고 왜인지 모르겠는데 시점하고 보기에서 불 지를거 같음
-
내일도 고고
-
시험망했군 14
수학은 자신있었는데 1학기가 또 발목을잡는구나 그래서 아크탄젠트 미분 어케함 물리는...
-
통사 통과는 2
유일하게 잘한 개정이라고 생각. 애초에 문과면 과학 지식 모르고 이과면 문과 지식...
-
달이 예쁘네요 5
슈퍼문이래여
-
1일 1실모 하면서 배기범 일당백 푸는데 역학파트 고난도 문제들 너무 어렵고...
-
현돌은 계속 보고있는데 헉시 개념이 부족할까봐 걱정되서 리밋도 볼까 고민중인데 굳이일까요?
-
내년에 메가랑 시대라이브로 다 채울 생각이었는데 굳이 끊는건 돈낭비일까요?
-
고2 베이직 내년까지 듣는거랑 수능 끝나고 나오는 고3 매가 패스 중 뭐가 더...
-
ㅈㄱㄴ!!
-
주겨줘...
-
헉
-
미쿠미쿠
-
소개팅할때도 연애할때도 ㅋㅋ 다 맞쳐줘야하노
-
상계 지문 좀만 어렵게 내도 등급컷이랑 난이도 모두 좀 더 괜찮았을 것 같은데...
-
사람도 되고 대학도 된다
-
달이 밝다 4
동그래
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자