컴공일기 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를 선물하세요.
-
킬캠이랑 비슷하거나 좀 더 쉬운걸로요
-
워뗘? 총정리 필수임요?? 이미 파이널 패키지를 사버렸는디..
-
인생 얘기 하실 분 20
심심
-
강e분 0
강e분 독서에서 지문내용 10분정도에 개념정리 해주시는거 왜 안올라오는지 아시는 분 계신가요??
-
저같은 경우에는 베르세르크가 인생작...보고나서 운동 시작해서 멸치에서 사람되기도...
-
정신 똑바로 차리고 난이도조절 똑바로해라 다음에도 이러면 빠따들고 대치동...
-
정시원서에 이번년도에 2023졸업으로 냈는데 괜찮나요? ㅠㅠ 제발 알려주세요
-
자체 추석특강 8
지2 매개완 인강복습
-
설마 요거트 아이스크림의 ‘정석’이라 그런가
-
등운동밖에 방법이 없는건가요
-
간쓸개처럼 하루컷할수 있는 분량인가요 연계 100%라길래 ebs학습용으로 1~8호...
-
걍 4번부터 n제화 강요하노
-
실포 풀면서 부족한 부분 보인히는 용으로 쓸려는데 난이도가 뭐가 더 어렵나요?...
-
에이 국어가 아무리 어려워도 그것 때문에 수학이 어려워보인다니! 그건 핑계지~~...
-
농특 되는 학생인데 농특보다 일반 전형 경쟁률이 더 낫다면 일반전형을 쓰는게 나을까요??
-
슬프네요 상훈쌤 작년엔 현강인강 둘 다 일습 내줫잖아요!!!! 작년엔 일습 필수편...
-
좀더 늘려보자..
-
인스타스토리보면 현직경찰 찾고계시네
-
??
-
아오씨 ㅋㅋㅋ 힘들어 죽겠네 어사대 비서성.
-
그래서 점심 저녁 시간엔 공부 안하고 걍 엄선경쌤 ebs연계만 들음..
-
가형 시절 1받고 논술 몰빵했는데 연논 예비로 떨어지고 N수 스타트
-
요아정 보면 2
벌집 맛이 궁금하다 꿀인거 알지만 맛을 보고 싶긴하다..
-
그렇게 잘하는 건 아니었지만 그래도 나름 현역 때 1년 내내 적어도 1등급은 받던...
-
고대논술 시간 3
자연계열 오전타임 오후타임 있던데 각각 하나씩 써도 상관없는건가요?
-
성대 공학계열이랑 전전 논술 컷보니까 2점차이나던데 이정도면 유의미한 점수인가요?...
-
1컷 몇 예상하시나요
-
안녕하세요, Uni-K LAB 입니다 메디컬 논술을 노리는, 화학1을 경험해본...
-
과탐11이 압도적으로 어려운가
-
연세 반도체 성대 반도체 원세 의예 3논술 let's go
-
과탐1과목 사탐1과목인데 사탐1과목빼고 나머지 4개로 최저맞출수있나요 ?
-
모든 상황을 대비시키는 대히카
-
1아니면 3이었기에
-
궁금합니다요...
-
난이도도 적당히 있고 문제 퀄도 좋고 무엇보다 내 수준에 너무 어려운 모고는 못풀어서 딱 맞음
-
라고 봄 보드 딴 전문의들, 개원한 개원의들은 돈 잘만 벌고 잘만 일하고 있음...
-
이전부터 궁금했음
-
수학은 죽었다 깨도 3은 안나오는데 국어는 툭 하면 3나옴
-
공통 문제 배치가 거의 비슷함 6월보다 덜 ㅈ같게 낸게 끝임 그리고 미적분에서...
-
와 난생 처음보는 점수 받아봐서 너무 당황스럽네요 그래도 69모 1등급...
-
의대 증원 + 영재고 의대 학종 지원 불가능 첫 해 후 정시만 올해 역대급 피터지겠네
-
엄마가 옛날에 오은영이 티비에서 부모의 자녀 핸드폰 관리가 필요하다는거 듣고 진짜...
-
다 늘어짐 걍 학교 가서 꾸득꾸득 자습하는 게 훨 나음
-
문학 연계작품 웹툰으로 보는 국밥이라는 앱인데, 이용권 비싸서 1/N 하려고...
-
갑자기 미디어콘텐츠학과에 관심이 생겼다. 내 적성에 맞는 학과 진짜 찾기 힘든데...
-
강대x 풀면 84~88 진동하는데 수능때 백분위 98가능인가..
-
국어 빼고 다 12고 군대 가서 수능 볼 건데 평가원 기출 솔직히 어느정도 기억...
-
수학 ㅈ된건가 0
기출에 나오는 수능틱한 문젠 익숙해서 ㄱㅊ은데 시중문제집, 내신틱한 문제..같은건...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자