컴공일기 247
게시글 주소: https://i.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를 선물하세요.
-
평가원 기준 1~2 진동이면 뭘로?
-
소규모헌병인데 근무시간제외 매일 7~8시간가능하고 짬차면 초소 선임병으로 들어가는데...
-
왠만하면 작수보다 더 어려운데 1컷 90점대 2컷 80점대가 맞나요 이게?
-
전 공부나 하러 갑니다
-
아침에 침대에서 일어나면 눈앞에 산과 나무들이 보임 캬 새벽 5~6시엔 닭들이...
-
지리 컨텐츠 1
전성오 jit 중에 뭐 푸는게 나을 까요 이모다는 다 풀었습니다 그리고 지금은...
-
내일 쉴 거니까 0
오늘은 마음을 불태워야지
-
과학지문 뭐임 진짜
-
제목처럼 여러 지문(가) 읽고 (가) 관련된 문제 먼저 판단하고 (나) 읽으시나요?...
-
문학 어케 잘함 0
이감 상상 뭘 풀든지 문학이 염*병임
-
선배는 남자아이 정주행할그임 니하하하ㅏ
-
벤치프레스 가동범위 슬픈 만큼 최대로 했어 ㅠㅠ
-
마더텅 제외하고요!
-
대성 QnA는 0
왜 이리 비공개 질문이 많음..? 메가는 상담 아니면 거의 다 열려있어서 내가...
-
평 다시 풀어볼려는데 21년도 6월부터 풀면 되겠죠..?
-
약간 어질어질하네요
-
글 올릴라 했더니 자꾸 금지어 있다고 떠서 걍 캡해서 질문합니다
-
지구 퀴즈 3
1. 양서류는 현재로부터 443.8백만 년 전 ~ 419.2백만 년 전에...
-
수능 최저(4합) 때문에 급하게 지구 노베 상태에서 2~3등급까지 올려야...
-
학기 중 꿀알바 과외. 이제는 잡을 수 있습니다. 과외구하는법부터 현실적인 팁들과...
-
숏컷 플로우 같은 시대컨 인강 컨텐츠 거르면서 까지 5
할만한 가치가 있나요?
-
수1 쎈 c단계 0
수1 시발점 워크북보다 어렵나요
-
맨날 76-79에 점수 고정되서 나오는데 85-88 나오려면 무슨 방법을 써야할까 흠…….
-
본인 기출 + 이감 + 쓸개랑 다른 사설만 보고 수능장 갈까 했는데 사실 올오카...
-
상상 이거 뭐임 6
이거 이러면 한 사람은 해설지도 없이 받았다는 거 아님?
-
기상! 8
-
위치 특정하기가 생각보다 쉽기 때문 평균 걸린 시간 2분 평균 오차 400m
-
수학 n제 4
수분감으로 기출만 하고 n제 시작하는데 모의고사 2등급 정도면 보통 뭘 하나요?...
-
수2 미적다 2권이고?
-
기분이 고양됐어 0
사실 고양이 아닌 고양이야
-
자율이지만 자발적으로 갇히기로 했어
-
2025 6모: 비문학 3개, 문학 4/8 작품 연계 2025 9모: 비문학 3개,...
-
8시에 도착해서 국어 좀 풀다가 카페인 충전하러 잠깐 편의점가는중
-
안녕하세요. 김지헌T입니다. 위는 칼럼에 첨부한 제 자작문제입니다. 해설과 곁들여...
-
선택 화작이고 화작에서 40 , 45 두문제는 고정으로 틀림 문학 다 풀고 비문학...
-
한수 사이트에서 판매하는 파이널 패키지 한수 학원용 파이널이랑 같은건가요 ? 제품...
-
얼리버드 기상 1
다시 취침 준비
-
ㄱㅊ?
-
4000부 판매돌파 지구과학 핵심모음자료를 소개합니다. (현재 오르비전자책 1위)...
-
개인 유튜브 채널에 사설 모의고사 해설강의 올려도되는건가요? 저작권이런거안걸리나요?
-
모닝커피와 시작
-
대머리남자가 아니라?
-
애옹 1
애-옹
-
이감하는 게 나을까요 아수라 총정리 하는게 나을까요?
-
그 전에하면 너무잘생겨서 여붕이들이 잠을 못이룰듯
-
투장연 화이팅 5
형은 작년에 투투장연이었어 투과목 화이팅
-
바탕 6회 후기 3
독서 -3점. 97점. 내가 본 시험지 중 역대급 쓰레기.
-
ㅠㅜㅜ 나도 보고싶러
-
진짜하기 싫다....... 오랜만에 잠 ㅈㄴ 자고싶은데 할게 너무나도 많네요........
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자