컴공일기 247
게시글 주소: https://iu.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를 선물하세요.
-
으아아아아아아아아아아아아아아아아아아아아아아아아아아아 4
아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아아...
-
19만 지르면 10
19만 지르면 패스가 생겨 배송도 해줘 19만 지르면~ 너도 내년이 있을 거 아냐...
-
천만덕 가쥬아
-
이제 정들었던 화1을 떠나보내려고합니다.. 메가 대성 상관 없습니다 인강 지1이면...
-
전쟁좀 평화롭게 합의 봐라
-
히히 0
뿌지직
-
이원준+정석민 조합은 신이네
-
지금까지 수특, 수완, 모고 8개년 기출 모음집 같은 거로만 공부를 했는데 탐구...
-
대통령실 "사실 4000명 의대증원 필요…틀렸다면 근거 갖춘 안 갖고 오길" 32
의대 증원을 두고 8개월째 의료계와 대치 중인 대통령실은 17일 의대 증원의...
-
수학수학수학 0
김범준쌤 이번에 인강 런칭하신다길래 궁금하기도 하고 이창무쌤이랑 비교해서 어떤가요????
-
국어-김승리 유대종 정석민 김젬마 수학-이미지부터 한석원~김범준까지 영어-이명학 션티 이영수
-
어느날 보면 살 튼 자국이 늘어난 것 같을때
-
삶에 중요헌개 없다고 느끼는것과같나
-
대성 신규강사 2
실루엣 추측가는분 있나요?
-
생명과학 0
생명 2 목표이고 최저러라 주말엔 하루종일 할 수 있고 평일엔 3시간 정도? 공부할...
-
뭐가 더 강의력 고트인가요 그동안 도표는 감으로만 풀고 다 맞았는데 수능 들가기 전...
-
김동욱 선생님이 장클에서 국어 실모도 두번 연달아 치면 피지컬 올라간다는데 해보신분 계신가요?
-
내일부터는 진짜 달린다
-
유기야 나한테 왜그래
-
김범준쌤 평가 9
그냥 고트임 ㅋㅋㅋ 보닌 2학년 11모 수학3이었는데, 겨울방학때 대깨치고, 수학...
-
언어이해 교수진에서 안보이는데
-
난 2일에 한번 싸
-
애매한 것 같아서 물어봅니다
-
설날 의미있게 보내기 연말 의미있게 보내기
-
이거 왜틀림...? 빡대가리 맞습니다... 근데 진짜 모르겠어요 ㅠㅠ
-
현재 내 목표: 서강대 화학...
-
연세대 건축공학과 논술시험 치른 수험생입니다 사실 저도 문제를 미리 받아봤고...
-
비유전 좀 많이 틀려서 복습 좀 하려는데
-
대성마이맥 사이트 홈에 GAME CHANGER 이라 적혀있고 안경쓰고 통통한...
-
오늘 2개 풀었고 처음껀 환경이 병신이라 제대로 안풀렸고 두번째는 회차 자체가...
-
ㅈㄱㄴ
-
실력 80 운 20 아님? 실력도 실력인데 그날의 운이나 컨디션 이런것도 성적을...
-
집으로 오라는 거 보니까 저번처럼 사이비는 아닌듯
-
아수라 총정리 어제 못해서 두개 하고 아침에 강k 치고 오후에 10모침........
-
독서가 약점인데 기출을 더 볼지 수특수완으로 연계 체감을 높일지 고민중인데 수능에서...
-
5분 만점각했는데 하나틀림
-
나만 그런거 아니었구나 걍 회차 자체가 빙신이엇다네
-
밥이라도 먹을걸 ㅎㅎ
-
두 학과 동급이란건 알아요 선호하는 학교학과 골라주시고 학교학과 이름 or 취향 둘...
-
기출에 나온 빈출어법 분석하고 정리본만들건데 이것만해도 ㄱㅊ? 지금 2초라 어법...
-
칭찬점 칭찬점 도파민분출중
-
fx에 x=0이 들어가는건 알았고 이게 한개냐 두개냐 고민하는 과정에서 의문이...
-
지구과학 이거머임? 10
1. 지금 근일점에서 북반구는 겨울임(12월) 2. 만약 6500년이 흐른다면...
-
으으으으으으으으으으으으으으으으 싫어
-
뭐풀지
-
국어 수학 사설 80점인데 신기하게 수능은 깔끔하게 나와서 작수 국수합...
-
5시간중에 3시간을 멍때린듯
-
6평 75 9평 90 10모 75 이감 파이널1 평균 78이런데 독서는 1개에서...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자