컴공일기 247
게시글 주소: https://ys.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를 선물하세요.
-
약사들처럼 단독법에 의료인 지위까지
-
고등학교 올라오고서 하나도 안하다가.. 공부 6월부터 제대로 시작했어요...
-
치대 섞을까요 말까요
-
ㅈㄱㄴ ++그리고 일반고 내신 3.0에 생기부 평범한 수준이면 bb맞죠?
-
한완수 pt2 살 때 같이 사버려야지
-
원래 이렇게 문제 뒤죽박죽 띄엄띄엄 풀고 넘어가나요?
-
정경대는 내꺼야
-
실모 주기적으로 푸는거말고 ㅇㅇ 잠깐안했더니 개념 휘발 ㅆㅃ이. 걍 하루에 단원별로...
-
김상훈t 파이널… 77
지금까지 유네스코 알파(문학,독서)제외하고 모든 커리를 다 따라온 시점에서 상훈쌤...
-
지원인원이아니라 응시인원이 15명인데 5명뽑는데 3명최초합이면 12명은 최저 못맞춘건가요?
-
하루에 물리1 100문제 챌린지 오늘부터 하고 있고 쉬운 수특부터 하고 있는데도 빡세네
-
수시 11
가톨릭대 의과대학 중앙대 의과대학 성균관대 의과대학 연세대 치과대학 나머지 2개 어디쓰지
-
특성화 중에선 좋은 학교긴 한데 1학기 내신이 3.2가 나왔습니다 모고는 평균적으로...
-
생지 69모 22133 10
11122 가능할까...^^ 그래도 국수는 둘다 백분위 95였음....ㅠㅠ 지학은...
-
ㅋㅋㅋㅋㅋ
-
50분이라는데 맞나요…? 9모 2등급인데 50분 잡고 풀까요?
-
제곧내
-
사문 질문 5
ㄱ이 왜 아닌지 모르겠어요..
-
곡선 외부의 점에서 곡선에 접선을 그을 때 접선의 개수는 2개인데 만약 그 점이...
-
일단 현 2학년까지 한 홍대 경영이고 수능 본 지 2년 넘었는데 당시 백분위 국어...
-
학종 수시 원서 접수하는데 전자공학을 쓰려고 하니깐 경쟁률이 많이 높을 거 같아서...
-
우주에 존재하는 물질 중 인간과 같이 살아있는 것은 극히 드물며 그 비율은 0에...
-
인기학과는 경쟁률이 쫄려서 어디 학과 써야할지 쫄리네요 자연계열이면 상관없어서 추천 해주십쇼‘ㅜ!
-
강남예서 고대 논술 다 쓴다했는데 경쟁률 ㅈㄴ 높네 학원가에셔도 강남애들...
-
서강대 논술 4
사회과학부라고 되있는데 합격하면 과 정해서 가는거임여?
-
기출이해하기전 개념공부하기에 뭐가좋나요? 이유도알려주세요
-
확통,미적,기하 전부다 인가요?
-
22번은 수열의 귀납적 정의 활용문제로 콜라츠 추측 문제 나왔다던데 ㄷㄷ
-
작수이후 한글자도 안봤다는데 감 되찾는데 얼마나 걸린다고 보십니까? 제 이야기는...
-
벌써힘드네 큰일났다
-
받을 수 있을까 하루라도 빨리..
-
이번에 9모 4 떴구요 피지컬을 좀 키우고 싶어서요 문제 양이랑.. 어삼쉬사,...
-
현장 체감 난이도 차이가 심하지.. 하.. 지1 진짜어렵다 공부할땐 알겠는데...
-
AI학과 0
학교 다닐수록 도망갈 생각만 커짐 반수 성공해서 좋은데 가야겠다
-
내일은 일찍 일어나야지
-
P(x바)=1/8이거 해석이 안되는데 추출 크기 상관 없지 않나요? 걍 3×c하면 1/8?
-
수시 원서 사진 6
수시 원서 사진 파일이 없는데 증명사진 폰카로 촬영한거 써도되나요? 군대라 새로...
-
9모로 최저 2
생각하고 수시 써도됨? 국수 변별력도 그렇고 영어도 쉬웟어서 9모를 기준으로...
-
강k 17회 요약 10
일단은 그리 어렵진 않은 문제들을 최대한 학생들이 절 요소가 많게 설계함 덕분에...
-
올해만 많이 뽑고 내년부터는 다시 줄어들까요?
-
초기에는 그렇게 많이는 안했지만 여튼 12월부터 삼수 공부 시작했습니다 대학...
-
공하싫 과하싫 4
공부하기싫고 과제하기싫다라는 뜻
-
질문받아주세여
-
9월달에는 5개년 6,9,11 기출 봐라. 기출분석이 전체 국어 공부의 50%여야...
-
둘다 최저가없어서 조금 쓰기 싫은데 그나마 어디가 합격확률 높을까요? 미적분 9모 88점입니다
-
ㅈㄱㄴ 3개 중 하나 합격한다면 어디 가는게 좋나요
-
지금부터 논술 준비하려고 하는데 유명하다해서요
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자