컴공일기 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를 선물하세요.
-
남자는 ㅈㅇ이야기 많이하는데 여자는 안하는 이유가 뭐임? 16
반대로 여자는 애인이랑 야스한썰은 푸는데 남자는 그런건 안품
-
문학이랑 독서1은 다 들었는데 재종다니소있는데 강의 러닝타임이 너무 길어서.. 그냥...
-
다들 그냥 혼자 하시는건가...?
-
국어 N제 1
지금 김동욱 취클래스 거의 다 했는데 간쓸개나 이감이나 상상이나 이런 것들은 언제...
-
갑자기 궁금해졌는데 생윤사문 노베가 2달동안 매일 2~3시간씩 공부하면 수능때...
-
구매하실 분 있으신가요 새상품이고 싸게 넘길게요 쪽지 주세요
-
논리가 다 거기서 거기라 삼도극급 국밥인 듯
-
9평 목표 2
문학 화작 다맞기 기하 선택은 다맞기 듣기 일치불일치 대의파악 요함장 필수유형...
-
8월까지는 출결 들어감?
-
밑줄친 두 표현이 뭐가 다른지 모르겠어용
-
ㅠㅠ
-
60점대.. . 어쩌다 찍맞하면 3등급나옴
-
어제 발치하고 저녁에는 눈물나게 아팠는데 자고 일어나니까 안 아픔. 그냥 입벌리기 힘든정도?
-
여친 콧구멍에 담뱃재를…재수학원서 만난 20대 男의 만행 2
[이데일리 강소영 기자] 재수학원에서 만난 미성년자인 여자친구를 심리적으로 지배하기...
-
몰래 오르비 앱으로 커뮤도 한다? 안한다? Yes or No 어쩌면 목적성이....
-
언젠가 독재에 관심가는 분있다고 남겼는데 얼마안되서 학원에서 드물게 그분이랑...
-
제주교대도 상관 ㄴㄴ
-
올클성공 9
유후
-
모두의 의견인감... 일단 국어쌤이 그렇게 말해서 파이널 구매 망설이는중
-
수학이욘
-
독서-2점(9번) 문학-6점 (23 26 33번) 언매-3점(36번) 문학 왤케 어려움...
-
모킹버드 실모 1
저거 사이트에서 추출하는 실모랑 다른거죠?
-
실모 0
구냥 사서 푸는 실모 등급컷 모르면 내가 잘본건지 못본건지 어케 아나여ㅠ
-
혼자 간쓸개 시즌2 풀고 있는 허수 어디 없나 동지가 필요해
-
집에 잇다 스카 왓는데 놓고 왔어요…
-
“일제, 쌀 수탈 아닌 수출” “임시정부는 단체” 식민지 근대화론 주장하며 독립운동 폄훼 3
“한국사 교과서의 서술은 일제시기 농민의 궁핍을 엉뚱하게도 일제가 쌀을 수탈했기...
-
수강료 16만원까지 하면 30 넘을라나요..? 20 중후반이면 해볼려고 하는데
-
'집에 벌레가 없다.' '이 글의 내용을 전혀 모른다.' '그 대표는 비리에 대한...
-
애니플러스 나 원신카페 나 애니메이트나 어디갈지 ㅈㄴ 고민되네 가서 공부할건데
-
처음에 좀 지루하지 않을까 생각하면서 봤는데 적당히 보기 좋은 일상힐링물인듯
-
있나요?
-
현역 사탐런 1
사문으로 사탐런 했는데 사문 인강 추천 좀 해주세요..ㅠㅠ 노베이스고 개념 강의...
-
원래 서바 모의반 다니고 았다가 김현우 정규 대기 풀려서 들어거려고 하는데 모의반...
-
어이가없네.. 시장도 세분화되는거고 그중 자기한테 맞는게 따로 있는거임 그리고 그게...
-
에피 신청할때 1
오르비 가입할때 생년월일 잘못입력했으면 신청 못하나요?
-
붙여만 준다면 매일 한시간씩 서울교대 방향으로 절함 ㅠㅠㅠㅠㅠㅠ
-
3주특강 드가자
-
뭔가 국어는 그냥 선지에서 시키는 판단 하나씩 하면 답이 나오고 수학은 결국 그냥...
-
제발 제발 제발
-
고1이고 무료길래 들어보려고 하는데 어떤가요 무료인 이유가 있을려나..
-
D-15 1
숨 참고 소해다이브
-
상위권은 어렵겠지만 하위권은 상관없을거가틈.. 원래 무림세계에서도 문파의...
-
6모 백분위 97 다른 모고 아무리 못봐도 84이상인데 킬캠만 하방이 76..
-
[단독]“대대 절반이 해외여행 경험”…‘출국 병사’ 올 상반기 첫 1만명 돌파 9
“대대원 절반이 해외여행을 다녀왔어요.” 강원 강릉시의 한 공군 부대에서 복무 중인...
-
영어 듣기 0
좀 어려운 책 없나요? 듣기는 항상 다 맞는데 혹시 몰라서 개어려운 버전으로 연습좀 하려고요 추천좀
-
이감 한줄평에 매회차 욕밖에 없는게 개웃기네 ㅋㅋㅋㅋ 0
호평을 본적이없음 잘본사람은 안쓰나
-
언어 수리 외국어 시절 자기 세대들은 사탐 과탐 전부 공부했었다고, 지금 너희들은...
-
할 에너지가 남아돌지 않는다 ㅅㅂ .. 기출만 봐도 벅참
-
생명 2등급 목표인데 요즘 기본 가계도 비교적 쉽게 나온다고 해서 가계도 2문제 다...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자