컴공일기 247
게시글 주소: https://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를 선물하세요.
-
와 개기대되네
-
https://youtu.be/a2qrP1oCPeE?feature=shared
-
혹시 탐구도 수학처럼 실모마다 스타일이 달라서 하나만 풀기보다 섞어서 푸는게 좋은...
-
ㅆㅂ 뭐라는거야…
-
10모 국어 2
독서론이 젤 어려운거같음 독서론만 1개 틀렸는데... 나머지는 선지에서 애매한건...
-
지구과학 실모 망쳐서 우울하다맨이야 히히
-
백호 ㅋㅋㅋㅋㅋ 0
아니 시즌2 4회 45점인데 6번, 16번 ㅅㅂ 비킬러에서 2개 틀리네 포식자는...
-
누가누가 잘찍나 31
62세 여자가 가슴에 덩이가 만져진다며 병원에 왔다. 2년 전 검진에서는 특별한...
-
개 춥네 진짜
-
어느 정도 가능할까요??
-
영어 매번 30~40 구간만 빼고 다 맞아서 4 나오는데 3
30~40만 찍특 이용해서 풀고 나머지는 그냥 풀면 3 가능? 해당 구간 제외하곤...
-
영어 81이 진짜 ㄱㅁ인듯 2등급 턱걸이 ㅁㅊ다
-
거근 지구과학은 제게 너무 거대한것이와요오오옷♡♡♡
-
D-28 궝부 1
10모 봤음 아이디어 통계파트 끝남(내일부터 킥오프) 동사 문풀 내일은 더 빡세겡
-
생각보다 덕코가 많아져서 시원하게 한 번 가겠습니다 제가 아껴두었던 궁극의...
-
3차전 내내 선풍기 두 놈 한 번을 안 떼놓네 그냥 포수툴로만 두고 8번 밑으로 놓으라고
-
중앙물리가 시립기계랑 비비네
-
10모 53535 수능목표33333 국어 아수라 안 밀리고 하기 수특 수완 수학...
-
기하러입니다 아니 이게 어떻게 1컷이 88에 2컷이 79인가요???? 11번 신유형...
-
아 실수네 보다는 아 실력이네 라고 해보아요
-
https://m.fmkorea.com/best/3363902739 이런 일도...
-
캠퍼스가 예뻐서 그런가 이름이 예뻐서 그런가 그래서 중경외시에서는 이유없이 제일 호감임
-
가변 저항이 커지면서 Vbe가 커져서 Ib Ic가 커지는건 알겠는데 총전압이...
-
8덮 국어 딱대
-
판권만료 뭐시기라네요
-
시즌3 몇 분 잡고 품?? 25분에 들어오려고 노력하는데 잘 안되는데 글고 이거...
-
뭐지 학평이여도 9평 24144가 12111이되나 수학은 걍 3이라고 쳐도.......
-
결혼하고 싶다
-
걍 똑같은거임?
-
적중예감 너무 실망스러운데요…… 지금 2회차까지 풀었는데 50 50뜸… 다음회차는...
-
몇 학년도까지 봐야하는지 감이 안 오네요. 17학년도 정도부터 보면 될까요?
-
당연히 현역 표본에 무의미한 시험인 건 알지만 제가 생각할 때 재수 등을 하게...
-
호훈단들 와보셈 2
분명히 상반기에 프메 이니셔 돌고 할땐 92~96 왓다갓다했는디 지금은 왜 만년...
-
편의점에서 라면이랑 크림빵이랑 칙촉까지 혈당 폭탄
-
수학실모오답 0
다들 언제하심?? 이거 모아서 하려니까 감당이 안되네.
-
개념형 나락가서 3등급나옴 오열
-
보잉님... 3
-
이번에 윈터스쿨 갈때 기출문제집 몇개 챙겨가려하는데요 패스는 대성 or 메가 구매할...
-
물리 시험치는 학교는 연고대 뿐인가요?
-
10모 확통 다 맞은 84(찍맞 빼면 80)이고 9모 84로 3이었습니다..,ㅜ...
-
물화생지2 각각 원과목 개념 얼마나 알아야 하나요?
-
ㅠㅠ
-
주인 잃은 레어 1개의 경매가 곧 시작됩니다. 덕코인"덕코인 상장 가즈아ㅏㅏㅏ"...
-
근데 짜피 얘네 내년에 다 빠지겠죠..?
-
어디쯤 갈 수 있을까요? 심리학부로 가고싶은데
-
통통기준 21 22 29가 많이 어려운데 21,29 꾸역 풀었더니 22는 거의...
-
쿄우노 츠키와 4
토테모 키레이 데스네...
-
2024년 10월 교육청 난이도 3.5 퀄리티 **** 시험 구성 **** 등급컷...
-
두 학교 학과 동급이란 건 알아요 선호하는 학교학과를 골라주시고 학교학과 이름 or...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자