컴공일기 247
게시글 주소: https://h.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를 선물하세요.
-
언어: 142 수리: 86 이래서 내가 예체능인가봐
-
전역 D-3 8
총기반납까지 완료 이제 진짜 좀 가고 싶다
-
나도국어의신
-
독서 -5 문학 -4 언매 -2 89 으어어어 이정도면 수능이었으면 1컷이었을라나,,,
-
sibal ㅎㅎ
-
존나게 익숙하지않구나 매우 불편
-
사설(이감 상상 더프 등)에서 생명 지문, 특히 질병 관련 지문에서 비타민 K 식...
-
반수 같이 하던 여자친구랑 오늘 내 생일에 헤어졌다..생일에 재수학원 가는 것도...
-
그냥 갑자기 여기선 안되겠지?
-
작수 6등급이었던 예체능 친구가 본인피셜 현재 사설 모고풀면 80점대 후반에서...
-
관통해드림
-
ㅇㅇ
-
이거는 대략 1년 전? 쯤의 나의 검사 결과이다. 언어이해 지각추론 작업기억...
-
극락..
-
그거 과마다 문제 가중치 조금씩 다르지않냐고 물었는데 ??ㄹㅇ ? ㅇㅈㄹ하고...
-
미적이라 모르는데 통통이 친구들 피셜로는 확통 어렵게 내면 어차피 안 풀어서...
-
수도권 1호선 역세권인데 농어촌+지역인재가 가능한 동네.... 3
바로 ”충남 아산시 탕정면“ 읍도 아니고 “면” 수도권 전철 1호선 역세권 KTX...
-
이감 6-1 1
9모보다는 어려웠는데 똑같이 93점 뜸 발전... 하고 있는건가 3등급 탈출시급
-
댓 ㄱㄱ
-
27수능까지 꽉꽉채워서 보면 갈 수 있을까
-
나랑 나이 비슷할텐데 ㅈㄴ 잘하는거 보면 ㅈㄴ 현타옴 이거 어케 극복하누
-
점메추 ㄱㄱ
-
성지글 1
현역 언미영생지 44234 재수 언미영생지 13222 삼수 언미영생지 12121
-
레전드삽질 4
잘 풀고 잇엇는데 그래프만 쳐다보다 보니까 주기를 대칭성으로 잘못 봐갖고 12 13...
-
뒤늦은 9모 인증) 12
망했어요
-
고액과외 같은거 받았을 때 성적이 올랐다-> 다른 수업 들었어도 올랐을 녀석이다...
-
실제로 인플루언서들 많이 봤는데 실제로는 몸 안 좋은 건 고사하고 얼굴까지 축 쳐진 경우도 많더라
-
국어실모에서 턱걸이 1도 아니고 안정적으로 1 떳음 ㅠ 진심 감격스러워서 눈물은...
-
진짜 어려운 지문을 읽을 때 문장마다 자신의 언어로 정리하는 동시에 내가 읽고 있는...
-
언미영생지 기준
-
ㅈㄴ 슬프다 공부 잘하고 싶다 수능잘보고 싶다
-
일단 화작&독서론 -> 가나지문 -> 문학 -> 나머지 독서 두지문이렇게 풀고 보통...
-
자습중에 에어팟 껴도 되나요 노래 듣는 목적으로요 그리고 현강 꼭 매일 3시간씩 다...
-
제 생각은 그렇네요 그 어떤 분야보다 이공계적이면서, 그 어떤 이공계보다...
-
날 더 강하게 만들뿐 밤 새고 똥참으면서 이감 6-4
-
정답률 75프로 미만의 사설 문제는 사설이 사설한거므로 맞은걸로 채크한다. 이감 98흭득 완료
-
바탕 7회 후기 0
언매 2틀 공통 3틀 88점 틀린 문제 해설보면 충분히 납득이 가서 좋은 모의고사같아요
-
디디라는 사람은 납치,공갈,인신매매,살인 혐의로 체포됐다고 함 단순 음모론일지...
-
없다 얻다는 최소 대립쌍이죠?? 발음으로 비교하니까 자음군 단순화 후 된소리화 돼서...
-
사람 한명 살린다 생각하고 지적 좀 부탁 허수담요단 나인거 같음 필기 너무 열심히함
-
6모때 승강심사로 올키 장학 받고있었는데 9모 올키 유지하려면 마찬가지로 국수탐 올...
-
내 공부 장점 2
1) 글을 잘 쓴다 2) 꼼꼼하다 3) 정리를 잘한다 4) 예습복습을 잘한다...
-
배 존나아파서 시험전에 화장실가고 중간에도 화장실가서 학교가서까지 품. 7시실모...
-
수면시간 부족.. 이 젤 큰 거 같은데 무작정 하원시간을 당기자니 순공시간 확보가...
-
국어 3->2 0
바탕 2등급도 나오고 이감은 3등급 정도 나오는데 바탕으로 쭉 밀까요 아니면 이감도...
-
언제쯤뜰까나 주말중에나오나?
-
결국에 가장중요한건 "기본개념/배운거 안쪽으로" 모든문제는 풀린다 이거고...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자