컴공일기 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를 선물하세요.
-
영어 개씹노답 3
지금 아마 모고풀면 4~5나오는데 하루에 3시간씩 투자하면 3등급 가능한가요 듣기랑...
-
맞팔할분 구해요 19
고
-
극값의차 질문 5
뭐 삼차함수 극값의차는 ㅣaㅣ/6-- 사차함수 극값의차 ㅣaㅣ/12 이거 말고도...
-
요즘 공부 안하고 5시간씩 오르비 눈팅해서 깔았는데 생각보다 불편함
-
겨울 쯤 돼서 시발점으로 개념 나가려고 하는데 전에 수2 시발점+워크북+쎈 할때는...
-
말벅지 소유자 근데 손목둘레가 15센치도 안되는
-
나먼저안락사시켜주
-
생명 찍기 1
가계도 소거법으로 항상 하나씩은 맞을 때가 참 좋았는데….요즘은 다 저격해서 안돼네요.
-
사만다 시즌1~3 다 살 필요 있을까요? 실모 ㅊㅊ 부탁드립니다
-
10모 지구 4
7번에서 시간 구분 해가 동에서 뜨는 걸로 구분하는거죠?? 그리고 이거 기본...
-
뭘로 해먹을가요
-
이감 파1 언매 36번 1번도 솔직히 잘 ㅁ?ㄹ겠는데 5번이 진짜 이해가 안됨 둘...
-
자야징
-
외모기만은 못 참음 성적은 노력하면 되지만 외모는 인생 리셋밖에 답이없음
-
경찰과 도둑 0
-
아무의미없는거 아는데 의대가 되나 싶어서
-
내 도파민이 2
ㅜㅜ
-
말이 안되네... 확통이 이렇게 힘든 건가요
-
부럽다
-
업 업 업 홀업
-
하루에 실모 하나 풀고 학교 한교시에 서킷 문풀+오답까지 하면 시간 딱 맞아서...
-
진짜 이등급 블랭크가 아님에 감사하다.. 말이 안되는 시험진데 이거
-
20대 초반 날렸다고 인생 망하는 건 아니겠죠…?? 19
두달뒤면 23살이라 20대 중반인데… 제 주변 친구들은 전부 대학 생활,연애,군대...
-
치킨 먹을까요 닭발 먹을까요 다른것도 ㄱㅊ
-
아마 여러분들도 한번 쯤은 인터넷 썰로 들었을 법한 이야기인데요, 프랑스에서는...
-
솔직히 슬슬 현타옴 10
전에는 수능을 잘보면 막연히 행복해지겠지라 생각했는데 요즘은 수능을 잘봐도 달라지지 않을거 같음
-
다음닉 투표 11
ㅈㄱㄴ
-
고쳐주는 댓글보면 짜릿해요
-
오늘의공부 1
국어:비문학비연계3지뮨/문학옛기출3지문/언매한세트 영어:10지문벅벅+단어...
-
ㄹㅇ인듯
-
삶은계란먹어야지 0
오늘 야식은 간단하게
-
백분위 6모 98 9모 91 10모 86 공부 계속 하는데 왜 떨어지는 지를...
-
이루어 질지는 몰?루
-
진짜미친놈마냥잘하는데
-
내신을 4 5까지 박은 이상 나에게 다른 선택지는 없다 남은 1년 수능에 미친듯이...
-
퀴즈 1
전자기파에서 전기장과 자기장의 세기의 최댓값을 각각 E, B라고 할 때,...
-
6평 1, 9평 2초인데 1일1실모 어떻게생각하시나요? 실모 많이보면 평가원식...
-
집공은 확실이 어렵다 14
-
원래 어느정도 머리가 좋은데 공부안함:5등급—>2등급 이런경우는 꽤 있겠죠? 근데...
-
42 43 나오는데 1컷이 44… 멘탈 나가는데요
-
저 궁금한게 생겼는데 잠깐 얘기 가능하신분 있나요? 1
정시수학 관련해서요. . . 삐약이라서 정보얻을곳이 없어요 ㅠ
-
다들 어디간거야
-
동생 중간이라 얘네 학교 시험문제 어떻게 나오는지 3개년(6학기정도) 기출 봤는데...
-
왜냐하면 이제부터 기다림이 24시간을 기다릴 때마다 대라기를 존나 쎄게 내리쳐서 제...
-
11월부터는 휴강이고 2주정도 수업 남았는데 그냥 수능 전까지 가지 말까요 수능...
-
시즌1,2 있는데 현강 다닐 때 무료배포 해주셔서 받아놓고 유기함 1,2나 3,4나 차이없나요?
-
ㄹㅇㅋㅋ
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자