컴공일기 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를 선물하세요.
-
기세문게슝
-
개좆됏다
-
기적이 아닌 당연한 결과
-
좋은 아침이에요 다들
-
졸립니다 시발
-
바로 7시경에 도착하자마자 번역 빠르게 끝내야 함... ㅡㅡ
-
9시 수업인데 8
이제 취침??
-
기차지나간당 5
부지런행
-
사랑이 변하나요? 죽을때까지 약속아닌가요?
-
2골넣고 3골 먹히기
-
잘자 4
-
긴팔 입으니까 2
기분이 이상하넹
-
찾아보는데 존재하는지도 모르겠네요..
-
2차로 피방 갔다가 지금 집가는 내가 할말은 아닌거 같긴하네.. 난 쓰레기야
-
왜 안 자요.. 몸 상해요
-
아무도 없다 흐흐
-
흠 아무도 없나? 19
-
아 피곤하다 5
잠은 안온다. ㅎ 오늘 1교신데
-
그거 되게 맛있었는데
-
벨로드롬 0
캬
-
국어 한 등급 상승 13
현 고2 최저러입니다! 국어 고2내내 낮3-4등급(찍맞 3개 이상 기준 고정...
-
있나요 사람 안보고 몇달동안 혼자 공부하니까 자존감이 끝도 없이 바닥을 치는 중임...
-
지금 영화 한편 뚝딱하고 한능검 강의 좀 듣고 오늘 하체 하는 날인데 오늘 쉬고...
-
음 굿 10
-
문디컬 4
수능 본지 4년된 아저씨가 문디컬 도전해보려합니다. 본래 이과였고 대학도 공대아닌...
-
아니 내가 준다는데 헌혈의 집 당신들이 왜 거부하는데. 왜 혈관이 안 보이냐고
-
현재 고2고 진로가 아직 명확히 정해지지 않았습니다,,,,,ㅜ.ㅜ 아마!! 넣는다면...
-
보는거지? 할시간 없지 않나
-
햅삐
-
2019학년도 교육청 모의고사 문제르고 해서 열심히 찾아봤는데 2019학년도 3 4...
-
고2 정시 목표 2
가고싶은 과는 일단 수의학과밖에 없어서 쩔수없이 과탐을 해야할 거 같은데 국영수...
-
v=sqrt(지랄탄젠트)
-
원운동 싫어 0
포물선으로 돌아갈래
-
내신공부를 해야하나요? 아니면 모고/수능을 해야하나요?
-
m이 아니라 ml입니다!
-
수능중독인듯 5
수능수학이랑 국어만 보면 너무 재밌음 정복하고싶음 이런 전국단위 싸움이 너무 재밌음
-
지구과학 질문 2
이거 ㄷ이 맞는 이유가 뭔가요?
-
으으 0
-
안정 3목표고 3~4정도 뜹니다. 옛날에 션티 강의 듣고 도움많이 되긴했는데 요즘은...
-
대강 틀은 잡고 검토하는데 g(1) 최대 나오는 그래프개형을 직감으로밖에 찾지를...
-
이해원 s2기준 한회차 평균 2개 틀림
-
9덮 수학 0
확통 76이면 보정 몇인가요? 131415 4로 밀었는데 두개 맞아서 사실상 68..
-
행복하세요 8
-
이해원보다 어려운거 같은데..반타작 나는데 유기해야 되나
-
시그모 개맛있다 2
아껴둔 보람이 있어 실모를 너무 많이 풀어서 그런가 밋밋함도 없지 않긴 한데 그래도 좋아
-
내 세상이 무너졌어
-
걔네도 n수하면 잘해짐
-
수원대 논술 8
수원대 수리논술 할만한가요 경쟁률 9:1이고 수학3고정 국어4고정으로 뜨는데
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자