컴공일기 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를 선물하세요.
-
아무런 비하도 없는데
-
"가능" 6
(저 말고 겜프릭이)
-
올해는 글렀다 생윤 사문 하면 타임어택은 없나요?
-
개념강의 -> 쎈 -> 자이스토리 -> 고쟁이or블라 -> 학교 프린트 이렇게면...
-
백건아 하이엔드?
-
??
-
손하트 17
-
자연 말구??
-
날이 너무 좋음ㅋㅋㄴㅋㅋ 따뜻하고
-
오르비 쪽지 1
쪽지로 사진 파일 보낼 수 있나요??
-
사문 적중예감 2
적중예감 풀고 해설 듣고 좀 지나서 다시 풀어보는거 어떻게 생각하나요? + 사문...
-
오전에 뻘글 ㅈㄴ 쓰고있는 거 보고 댓글 좀 달다가 할 일 하다 방금 왔는데...
-
설수리지망이에요? 한자리 날라갔네..
-
정직하게 답변 드리겠습니다.
-
1 ㄱㄴ? 서술형 4점중에 2점 인정 안되는게 이해는 안되는데 나머지 2점은 새로...
-
예전에 당근에서 받은 2024시냅스 있는데 여태 안풀다가 어삼쉬사 대체용으로 푸는거...
-
목표는 3등급 이상입니다 생명은 자이스토리 마더텅 수완 수특만 여러번 봤어요...
-
평소에 폰이나 테블릿으로 보면 눈아파서 책 못봣는데 이북리더기 아주 좋음. . ....
-
국어 - 운이 좋았다. 수학 - 답없음 찍맞 3개하고도 4등급임 답이없음 수능날...
-
오늘의 수익 4
오전 매매 좆같이해서 -30까지 찍힌거 오후에 +30만들어서 장 마감 ㅋㅋㅋ 결국은 또 tsmc
-
잘하면 더 좋아할 자신 있는데… 아무튼 화이팅
-
모순이 참이라면 26
(A and not A)=참 notnot(A and not A)=notnot참...
-
6평 69 (3) 9평 76 (4) 이후로 충격받고 2주동안 수분감 세 과목 다...
-
배터리 상태가 상당히 위긴데 지금
-
이글에 개추 누르기
-
제발 그 영상좀 찾아주세요 고려대 출신 남자 수능강사인데 돌아가신 걸로 기억해요...
-
작년에 서바 서바 하도 얘기하길래 구해서 풀었는데 개념은 너무 쉽고 도표를 너무...
-
내가 처음 메가패스 샀을땐 국어1타가 이원준t였는데 2
영어는 이충권 수학은 현우진(데뷔 1년차)
-
풀어봤는데 1회차 34번 틀리고 97점 일단 평소엔 듣기 포함해서 45~50분...
-
수능때 나온다면 1컷 80 정도 나올만한 걸로요!!
-
95점 10번,16번 틀림 10번 풀면서 뭔가 비타민k 생각남 독서론:짧길래 개이득...
-
ㅅㅂ? 좆됐다 이해가 되는 파트가 하나도 없네
-
현역땐 1,2타 말고 안유명한 강사들 듣는거 이해못했는데 2
지금은 유명하고자시고 그냥 자기귀에 잘들어오는 강사 듣는게 짱임
-
안녕하세요..ㅠ 제가 지금 적생모 7회를 학교에 가져와서 풀었는데 답을 놓고와서...
-
풀다가 진짜 N제화 시키고 싶었음 개인적으로 작수를 아득히 뛰어넘는듯 언매 제외...
-
10모처럼 나왔음 좋겠다 ㅋㅋㅋㅋㅋ 1등급 실력이 안되지만 1등급을 노려볼 수 있는……
-
지구 수완 2
수특은 했는데 N제를 할까요 수완을 할까요? 솔텍 파트1 다풀고 다음으로 풀 생각
-
3둥급뜨는데 뭐가문제지 2회때 딱한번 1떠보고 지금6화꺼지풀엇는데 다 한문제차이로...
-
남자인지 여자인지 물어보고 싶은 오르비언이 있는데 19
진짜 실례되겠지
-
음...
-
국정원 지하에서까지 그런짓을… 에휴
-
전 관독에서 악깡버하는데… 진짜 몸 안좋을때도 맨날 버티는데 안좋다는건 알지만.....
-
아 뭔 자신감이지.. 12
왜 원광치대는 될 것 같냐 너무 기대하면 실망하는데
-
????????????? ????????????? 진짜 뭐지
-
아까 스나 글 쓴사람인데 이 점수는 노양심인가요? 10
화작 2컷 간당 미적 100 영어 1 사탐 2개 3, 4 등급 앞의글 답변해주셔서...
-
예상해보는것도 메타인지에 속하는건가요
-
야 솔직히 스벅 자바칩 프라프치노 미만잡 아니냐? 31
반박시 초알못(초코를 잘 모르는 이) ㅋㅋ
-
언매 vs 화작 2
둘의 차이점이 시간인가요? 고2 국어 모고 3등급 나오는데 뭘 하는게 좋을까요?...
-
인생 ㅈ같다 0
내신 좆같다 진짜
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자