컴공일기 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를 선물하세요.
-
ㅜㅜ 그리고..전과목 통틀어서 찍맞 한개도 없음(영어제외)ㅜㅜㅜ
-
아 왜이래 0
원래 배그도 돌아가는 컴이었는데 모니터 신호연결문제로 이것저것 건드렸다가...
-
있을것 같다는 생각이 드네요 신입학은 오히려 감축이나 모집정지각도 보이는데 편입학은...
-
여기서 택 4던데 극단적으로 확통 고적 고급수학 경제수학 이렇게 들어도 되는건가요...
-
맨날 눌려지니깐 슬슬 못 참겠네
-
-
잠 마치 마약
-
정말 힘들었는데 마지막 멘탈까지 긁어모아서 겨우겨우 수능 치룸... 근데 제일...
-
ㅂㅂㅇ 3
언제잘지는잘모르겟다
-
이미지 써주세요 13
추첨해서 1명에게 만덕을 드립니다
-
. 5
논술 ㅈㅂ
-
6수하고 수능본 다음날 7수결심함 전재산 300만원 미국주식 3배 레버리지 풀베팅후...
-
화2 현강 0
현역 화2 현강 들을 수 있는 곳 있나요?? 목동이나 대치쪽이면 좋겠네요.
-
a < m <b 이게 신뢰구간이고 신뢰도 95%이면 실제 모평균이 a < m <b에...
-
내일 장실 예약이요~
-
ㅎㅎ
-
근 3달동안 혼자서 공부했었는데 한계가 좀 와서 겨울신록 들어왔는데 플래너를 좀...
-
헉 0
그냥글쓰기
-
전 소오오올직히 얘기해서 의대 가려는데 3합5 맞출 수 있을까요ㅠㅠㅠㅠ 수학 3컷이...
-
추천해주삼
-
오늘 마법천자문 16
10권부터 46권까지봤는데 ㅁㅌㅊ
-
화1 버리고 국영탐위주 +수학은 조교/과외 할듯요 ㅠ
-
챗지피티 아직 한 번도 안 써봄 무선이어폰은 qcy 샀다가 계속 잃어버리길래...
-
저 이미지 적어줘요 22
사랑스러운우리옵붕이들 이미지적어주고가세요
-
하 냥대인문도힘들겠지
-
수능을 5개미만으로 틀린 집단에 들어가서 그냥 뱃지달고 꺼드럭대고싶당
-
작년엔 여행한번 가고 감기몸살 걸리고나니 실채점 나왔던거같은데 올해는 유독 기네
-
함께 고민해드려요. 쪽지 환영~ 댓글도 좋아요.
-
지피티 추천 질문도 있어요
-
국어 만점 과외 2
4->3->만점 (6,9,수)인데 과외 구해질까요.. 뽀록으로 보여서 안구해지려나여
-
반갑습니다
-
현역때 웬만한 방법론 같은건 다 들은거 같은데.. 문풀이 부족할 뿐이지
-
잠 자는 시간은 늘어나는데 으어.. 아침에 에너지드링크 마시면 저녁이나 밤에 졸리고...
-
난 키타좋아하니까 건방진건가
-
솔직히 반환점 돌 때까지만 해도 쉬운 미분파트 난이도와 어떻게 보면 조금 과도한?...
-
어떨까요..?? 아무래도 인하대=공대 이미지가 있다보니까 좀 걱정되네요ㅠ
-
앵간한 수제버거집 메뉴는 덥콰치로 대체 가능함 심지어 지금 앱 쿠폰 써서 7900원에 먹는중
-
특목고 다녔고 성적이 좋은 편이 아니라 전문대 지원해보려 합니다 수시 성적은 5점...
-
빨리 깨달으시길 본인 실력의 몇퍼센트가 수능에 나오는지가 다름 뭔가 운명도 있는거...
-
내일부터 다시 활기차게 18일을 보내보자 18!
-
솔직히 많이 배고프진 않았는데 넘 과한 선택이었음 낼 점심까지 굶을까 걍
-
555랜만에 질받 33
-
ㅅㅂㅅㄲ 3
삼반수고고!!
-
거의 붙는다고 봐도 되나요?.... 아님 아직 모르나요
-
궁금합니다
-
올해는 쌍윤으로 봤지만 예전엔 생윤사문이였는데 사문칠 때 같은 고사장 아저씨가 좀...
-
의대관련 질받 17
어느점수로어디쓰면좋을지 어느의대가좋은지 등등 사실 아무질문이나 ㄱㄴ
-
생윤 가채점 밀린거 좀 쫄리는데 어떻게 하면 좋을까요 간다면 공부는 어느정도 할까요?
-
실험할 방법 없나
-
물리 지구 실수때매 백분위 20씩 떨굼 사탐으로 바꿔서 삼반수
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자