컴공일기 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를 선물하세요.
-
굳이 왜 들고 기다리지 그것도 어느 정도 시간차 있게 나갔는데
-
전형적인 '애는 착해' st
-
빅뱅 후 3분 (헬륨원자핵 생성) 이후부터 지금까지 수소 헬륨 질량비는 거의 3:1로 일정하나요?
-
강k에서 계속 대가리 깨지고 70점대 못벗어나니깐 쉬운거 풀고싶어짐
-
두각에서 오프로 진행하는 이감 모고 시즌 6파이널 언제 예약창 올라오는지 아시는분
-
시간만 있으면 해설 안보고 풀리는데 4점 푸는 시간 줄이려면 어떻게 하죠오ㅠㅠ 모고...
-
쉽게ㅔ 뜨나요???? 듣기할때 안풀다가 오늘 실모 듣기 들으면서 18-20,...
-
2017년에 산 갤럭시 탭 쓰고 있는데 슬슬 성능의 한계가 보이는 것 같아요,,...
-
수험생때 운동하면 대학갈때쯤 몸 탄탄해짐
-
급우울해지네.. 원래도 그랬지만 정시로 튼 후 몸/정신 모두 학교를 거부함...
-
방금전까지 한국이엇는데 친구가 비행기표만 내준대서 또 왔음.. 술집 왔슴다
-
제가 고12때는 계속 1등급이엇다가 고3 올라와서 3으로 떨어졋는데 9모 전까지...
-
메카니카 - 클러스터 파급 물리 - 모킹버드(파급) 이분들은 제 구세주세요
-
3모 100 5모 97 6모 96 7모 99인디 + 작년 6모 95(화작) 9모...
-
화작N제 2
이감 vs 상상 vs 본바탕 뭐살까요?
-
사문 기출 분석 0
얼마나 중요한가요?? 형수쌤 기출분석 듣고 있는데 거의 아는 내용 같고 ㅠ...
-
렉카들 처보는데 1
이거 때문에 괜히 밀양 사건 파는 애먼 렉카들까지 피해봄;; 분명 인터넷 방송 중...
-
퇴근 2
-
저는 이번 1학기 시험기간에 공부하기 싫어서 안하고 사회 모의고사 만들어서 배포함요..
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자