컴공일기 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끼 나와서 따로 밥 사먹는 일은 거의 없을 것 같고 술, 담배x...
-
명절이구나 0
즐거운? 명절
-
. 1
맛점 하새우 허허
-
어떤 사설 문학을 만나도 전체 세트로 따지면 작수보다 어려운걸 본적이 없음......
-
제가 지금 2025강기분 독서 듣고 있는데요. 이거 완강하면 내년에 나오는...
-
1.헌급방으로 군수할생각인데 군수실패하는이유가 시간은꽤많은데 일과나 훈련?받고와서...
-
신텍스 알고리즘 수강했고 지금은 기출 깔짝(거의 안함) 하고 있는데 리로직 안하고...
-
1. 사탐1개+과탐1개 보려는데 과탐 2개할때만 가산점 주나요? 아니면 과탐 1개에...
-
왜 시험때는 그렇게 급하고 그랬을가
-
아오 ㅅㅂㅋㅋㅋ
-
고민중이라…
-
막히는 부분 답지보면서 풀어도 ㄱㅊ나요
-
상상 4-2 0
상상 4-2 독서 진짜 맵네요 문학은 맘에 들고 문학 이감보다 훨씬 나은듯
-
손가락으로 예를 들면 기껏해야 얇은 고기덩어리에 뼈 박혀있는 정도의 질김인데 이걸로...
-
정시100으로만 명문대에 가는것은 불가능해질까요? 정치적인 이야기하려는건 아닌데...
-
덕코 현금인출 4
어캐해요?
-
11번 푸는 데 70분남고 12번 푸는데 50분ㄴ 남아서 n제화 on
-
https://youtu.be/Ssd_JpuaOaE?feature=shared...
-
작수가 갑자기 22에서 급발진한 것처럼 만점방지용 문제가 분명히 박혀있을거라...
-
전열심히부쳤네요 0
절반은배로들어감
-
밥 뭐먹지..
-
지인이 17학년도 모의고사와 수능 국어를 풀 때 모든 문제를 지문을 먼저 안 읽고...
-
국영수사문생윤 다 풀어야할까요 ㅠㅠ? 작년엔 거의 안 했어서
-
이감 오프 0
일정? 잇으신 분 계신가요 뭐 사야될지 모르겟음 ㅠ
-
강윤구T 포3, 4공S 다 들었는데 윤구T처럼 금머리말고 일반적인 두뇌를 가진 분께...
-
풍성하진 않고 맨들한 한가위
-
안올라오나 아 물론 유빈이는 내가 아는 어떤 사람임
-
기출을 22~24까지밖에 안 했는데 2017기출까진 하는게 좋을까요?
-
문을 아무도 안 열엇서..
-
연역적 탐구면 가설이 꼭 있어야 하지 않나요? 이 실험에는 가설이 안보이는데 연역적...
-
59일 남았네 이제 오르비에 글쓰면 난 좆돼지개새끼다 0
꿀꿀꿀 멍멍멍 오잉크오잉크
-
내신때 배웠는데 ㅋㅋ 내신한정 개꿀임뇨
-
진짜 위험한 소신발언) 23
코로나 백신 <<< 이거 한 10년 뒤에 재조명될 거 같음
-
재밌었다
-
국어 적절하지 않은 건데 적절한 거 고르고 적절한 건데 적절하지 않은 거 골라서 많이 틀림ㅋㅋㅋㅋ
-
내년부터 개인레슨 받을건데 노력으로 극복 가능? 진격거 브금들 드럼으로 쳐보는게 꿈임
-
표가계도 0
기출에서 표가계도가 가계도 단독 문제로 나온적이 있나요? 항상 돌연변이에서만 나왔던 것 같아서요
-
우기분 3
6모 2컷… 허수입니다 피드백 과학기술, 이감 간쓸개 연계문제 기출 실모 이렇게...
-
너무 과하거나 지엽적이진 않나요?
-
일주일에 하나만 할 생각인데 이감이랑 상상중에 어느걸 추천하시나요??
-
얼버기 4
zz
-
논리다듬기
-
한양대 FM정리 10
섹시 파경 폭주 자동차 영양만점 식품영양 ㅋㅋ
-
용돈 받으러 왔어요 10
-
수능 시험장가면 어차피 그냥 날려읽게 되어있음ㅋㅋ 딴 풀이 생각할 정도의 여유가 없음
-
독서에서 시간 ㅈㄴ 쓰이는 게 가나 인문 지문이 ㅈㄴ ㅈㄴㅈㄴ 오래 걸리네. 잘...
-
올해 수능 잘보고 입대 취소할렸는데 나 군대가있는동안 집 월세내주시고 빚 갚으려...
-
? ㅋㅋ
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자