컴공일기 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를 선물하세요.
-
크아아아아아앜 미쳣다 두달도 안남았다고 진짜 와
-
오늘 공부 7
내일 쉼
-
님들 과제 안밀리고 잘 하고 있음?? 생각보다 많네
-
딴건 이제 거의 다 맞추는데 천체 파트랑 반감기 이게.. 어렵게 나오면 안풀리거든요...
-
수학 실모 추천 0
메가 대성 외에서 시중 구매 가능한 실모 추천좀
-
근데 어쩔수 없는듯 오답정리 확실하게 하자
-
나의 구원자들
-
입문:가장 평범하지만 가장 강력한 입문 개념:폭발하듯 강렬한 개념완성 기출:기출을...
-
20학번이라 울었어ㅠㅠ
-
'벤처 천국' 떠나는 기업들…무슨 일이 있었길래 [송영찬의 실밸포커스] 1
미국 실리콘밸리는 전 세계의 가장 대표적인 ‘스타트업 천국’이자 테크 업계의 심장부...
-
아육대 봤는데 0
설윤 진짜 이쁘데
-
6평보고 국어하느라 거의 안해서그런지 정상화당했는데 어떡하죠 굵직한건 기억나는데...
-
사아 밍밍타하 12
츄우야카쿠텐
-
다시 태어나면 4
이재명 vs 윤석열 와이프는 그대로 혜경궁 김씨 vs 김건희
-
그냥 제 인생에서 가장 후회됐던 선택이라 순간 울컥해서 넋두리좀 해본건데 언짢게...
-
확통 사탐할거임?
-
24/09/16 월요일 [국어] : 박광일T [주연마의 서 9강, 10강] -목가적...
-
수리논술 1
6장 썻는데 계집이라 수학 못해서 ㅈ댐 건대 확통 통계부분 잘 안나오죠?? 확률만 공부할 계획인데
-
21번진짜뭐임????? 21에서 말려서 21 22 28 30 싹나감 28은...
-
택 1 ㄱㄱ 난 무조건 문학
-
이것은 수능 이후에 벼락치기로는 절대 붙을 수 없을 거라는 확신이 듬 늦었지만...
-
물리 무서운점 7
1페이지 별거 아닌문제에서 시간끌림 하나로 끝날 리 없음. 여기저기서 계속 턱턱막힘...
-
엔제
-
정신나갈거같아
-
공부해서 컨텐츠 만들어보는 것이 소원
-
올해 목표대학 가면 11
내년엔 진짜 정벽모 만들어볼까 ㄷㄷ
-
ㄹㅇ
-
검색해도안나와요
-
양도 0
완전양도 가장 큰곳 ㅁㄱ 구해요! 급합니다 .. 편하게 쪽지 주세요
-
풀고 틀린거 고민 몇분 정도까지 함?
-
어느 분야에 있어서 최고가 되기위해서는 많은 노력이 필요하다고하네요 10000시간...
-
수능 끝나고 칼럼 쓸거임
-
요즘에도 균대가면 많이 헤어지나오?
-
관심좀 13
관심
-
현 메가스터디 쌤인데 자주 하는 말 모음이에요 ㅋㅋ " (흐억!)(칠판소리...
-
그럴바엔 올해대학감ㅋㅋ
-
나 억울해 4
동생이 훅 지나가면서 디시 좀 그만하래 평생 디시 한 적도 없고 오르비 학습글 보는...
-
노력하고 발품 팔면 어느정도는 갈 수 있지 않나 눈이 높아서 취업을 못하는 것도...
-
옯창인가요?
-
스킬위주로 독해력없이 푸는강사 ㅊㅊ좀 독해력기르긴 시간도 능력도 없음
-
하 ㅋㅋ
-
사회문화 질문 7
문화 상대주의가 문화의 차이가 생기는 이유는 발전수준의 차이 때문이다 라고 할 수...
-
이감은 안 사고 싶고 상상,한수,바탕 중 2곳 파이널 실모를 구매하려고 하는데...
-
그럼 걍 중도퇴실 해야하남
-
하원해버리기
-
씨발 2023년 생각하면 정유정 이 개년 때문에 과외 앱도 삭제하고 다 지우고...
-
降 1
落
-
오공완 2
오늘도 즐거운 영어유기
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자