컴공일기 247
게시글 주소: https://iu.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를 선물하세요.
-
ㅇㅇ 뭘 더봄?
-
다들 키도 훤칠하시고 잘생기셨더군요 굉장히 즐거운 시간이었습니다
-
이감 수학 무료로 나온거 등급컷 있나요? 15, 19, 21, 22 , 30...
-
미필4수문과 우울증심함 자살충동매일듬 모솔 집안부자x 없을듯아마
-
이창무t 심특으로 뉴런대신 들어도 되나요? 대충 맛보기 보니깐 오하려 기출 풀이?...
-
실전개념 듣고 기출풀기 어느 쪽이 나을까요
-
틀린게 다 3점일 때가 제일 빡침
-
1. 저는 기초수급생활수급자 신분입니다. 연세대학교 연세한마음전형 자격이 있을까요?...
-
대체 무슨 일이 있었던 거임 ㄷㄷ
-
화생은 어케함?? 내신공부할때 유전나오면 쌍욕나오던디
-
이제 남자도 견제해야 함?? 나같은 도태모쏠개씹찐따녀는 어쩌라고 ㅠ
-
공부도 안 되고ᆢ제대로 쉬는 것 같지도 않고ᆢ
-
"ㅅㅂ 공부한만큼 나오면 ㅈ된다고요"
-
이감 시즌 5 마지막연장? 그런걸로 샀는데 4~7주차밖에 못받음 … 이럴수가있나.....
-
어릴적부터 차근차근 쌓여온 실패로 인한 패배근성 몇년 전부터 쌓여온 심한 우울증...
-
https://orbi.kr/00069180655/ 인사말
-
혹시 올해 수능보시나요? 혹시 올해 수능보시나요?
-
논술 갈 때 4
수험표 같은 거 챙겨가야 함??
-
난 왜 모르지
-
이감 ㅈㄴ 어렵내
-
1단원 첨 공부했는데 아무리 봐도 모르겠고 조금이나마 이해된건가 싶어서 문제...
-
ㄱㄱ
-
찐따의 적은 찐따 차피 여기서 찐따니뭐니하는게 의미없으니까 그냥 사이좋게 지내요
-
추석 용돈 받음 3
나이스
-
최근기출에서는 어법 문제 틀린적이 없는데 예전 기출 풀다보면 급하게 풀다가 하나씩...
-
제가 수학을 쉽게쉽게만 하는걸까요 머리가 안아퍼요 그렇다고 잘하는건 아니고...
-
로 중대 아님 경외시 라인까지 가려면 어느정도 받아야 하나요? 학원을 안다녀서...
-
공식계정 말고 본닉이 따로 있으싱가
-
나 멜론 알러지 있나 18
먹으니까 입가가 가려워요
-
모집요강 다시 보니 클립 끼우고 제출해야한대서... 설마설마 클립 안끼워도 불합처리되려나요...??
-
그냥 방향은 보이는데 계산하기 싫어서 멍때리고 있음...
-
남장여자 vs 여장남자 38
남장 여자 : 민지같은 잘생쁨 스타일 아니고 그냥 ㄹㅇ 남자같고 개못생긴 스타일...
-
오늘의공부 0
국어:기출 비2 문5..?분석 영어:10지문+단어암기 수학:실모1개+브릿지1개 원래...
-
우울해 2
걍 에휴 자살마려움
-
어그로 ㅈㅅ.. 너무웃겨서ㅜ그런데 이짤 있으신분?? 어디서찾나여..
-
요즘은 추석이나 설에 가족끼리 안 모이는 경우도 많나 1
우리집만 그런건가..마지막 용돈 주고받은게 거의 10년전..
-
동그랑땡이라고 생각해요
-
반박 받을수도있고 안 받을수도 있습니다
-
6평 37 (3) 9평 41 (3) 오지훈 개념 기출하고 (기출 두번 품) 수특...
-
인문논술 각각 79/100 278/300인데 가망없겠죠?? 넣긴 했는데 빠른손절 할까요 ㅠㅠ
-
과외쌤이 스카이 중 하나 다니시고 나름 잘 가르치시는데 무섭게 생기시고(외모 비하...
-
올해 수능은 8
국어 언매기준 85 수학 미적기준 87 물화생지 47간당 사탐들은 1컷 50
-
너 외동이야? -> 욕 (특히 여자한테) 너 누나 있어? -> 초특급 칭찬
-
상품 자체 레버리지와 주식의 변동성x3과 꿈과 희망이 숨쉬는 해외선물 데이트레이딩은...
-
난이도도 비교 부탁드려요
-
여동생 있는 사람들은 13
여름에 땀에 흠뻑 젖어서 선풍기에 대고 아와와와왕 하는 여동생을 직관할 수...
-
시간 = 푸는 문제 대비 시간 오늘 한거 2022 3모 오답처리...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자