컴공일기 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를 선물하세요.
-
정신과 환자를 조롱하는건 잘못됐다고 생각해요...
-
삐까뻔쩍한게 몇억은 들었을것 같은 비주얼인데 이용하는 사람이 아무도 없고 파리만...
-
엌ㅋㅋㅋ
-
다행이 100이긴 한데 이거 현장에서 풀었으면 ㄹㅇ 멘탈나가겠네ㅋㅋㅋ 특히 문학...
-
꿈돌이 진득하게 밀어주는거 너무 귀엽지 않나요ㅜㅠㅠ 대전 많이 좋아해주세요 엉엉....
-
정확한 맥락은 모르겠어서 내 마음대로 첨언. 자유주의 진영이라고 사기업에 전혀...
-
눈 더 나빠졌다고 할까봐 무서워서 못가겠음 근데 코팅 다 나가서
-
집중안하기 응안해 아몰라...
-
세뇌나 받아놓고 그 세뇌에 반하는걸 말하면 짐승처럼 공격하기나 하는주제에
-
너는 왜 나대니 4
중국 fdi추이 찾아보시구요 자유주의국가들이 왜 사례가없겠니 그짓을 하면 ㅈ되는걸...
-
경제 이새끼 왜 사문 따라감?
-
평가원이나 교육청 문제를 풀때는 문학에선 틀릴지언정 독서 전체에서 보통 1개...
-
ㄷ선지가 맞는선지인데 이해가안가요 (나)의 B에 도달하는게 아니라 급팽창이전에 도달한거 아닌가요??
-
사문 실모 다 풀ㄹ고 어테하세여? 오답도 하나요..?
-
고려랑 순서 나열,개항기에서 벽 느껴진다 이제 개념 디테일을 챙겨야할듯…
-
최소한의 반례는 제시못하시면서 아무튼 통계드립치면 지가맞는줄아네 야 ㅇㅅㄲ야...
-
그럼 노예를 만들려는 시도가 무효화될까?
-
글 쓸 때 애초에 분류하는 기능이 없어서 불가능하려나 아 근데 막 오르비 내...
-
by chatgpt
-
수입품에 대한 을국 가계의 소비지출이 gdp에 반영이 안된다면 if 생산측면의...
-
난 스카갈때 화장 1도 안함
-
9모 같이 너무 쉬운경우를 제외하고 보통 1컷 80초중반 나오는 시험지 기준임...
-
뭔가 도표 안내문 이런 쉬운 문제에서도 단어로 낚시거는 경우 많아서 좀 애매하긴...
-
1)밤에 5시간만 자고 공부해야지!! 함 2)눈비비고 일어나서 국어품 ->그정도자고...
-
고민
-
지금부터는 집중안될겁니다 ㅎㅎ 그리고 눈뜨면 수능이에요 컨디션관리 잘해봅시다. 막...
-
사케베~
-
이매진 핫백 문학 난이도는 어느정도인 편인가요? 수능정도?
-
9평이랑 비교했을때 난이도 어떤거같은지요 9평보다 점수 많이 올라서 기분이 좋은데 흐흐
-
난 살아있는 지성의 화신인것을..
-
반대로 못봐도 스트레스 안받을거임
-
언매 태도교정 필요
-
수면 1
제가 2시부터 7시까지 5시간정도 자는데도 졸려서 중간중간 쉬는 시간에 20분씩 한...
-
뇌안에 논리가 없어서그럼 논리를 만드는 논리도 없어서 그럼 논리를 만드는 논리를...
-
살모벅벅해도 안되고 시험장만 가면 계산꼬이고 발상 잘 안됨... 항상 10점씩은...
-
이상치다 하고 유기할까
-
일어나니까 20분 지나있네
-
왜 나는 출근을 하는가
-
6평 지칭어호칭어 1틀 9평 2틀 실모 평균 2틀 음...... 기본적인 개념은 다...
-
주위에 어떰
-
문제를 다 맞췄어도 뭔가 지문자체가 겉핥기식으로 이해한 느낌들면 되게 찝찝하지...
-
화학 중화 공부 안 해서 젤 안 나온 번호로 찍었는데 이게 맞누 생명은 공부 안 한...
-
그런 사설 회차 아시는거 있을까요? 작수에 ㅈㄴ 충격먹었어서
-
결국 최후의 승자가될 가설은 정해져있고 그 가설이 검증받으면 이론이 되어 모든...
-
오지훈은 지문 안읽고 풀겠네ㅋㅋ
-
올해 9평보다 쉬웠어요?? 풀세트로 풀어본 적이 없어서 감이 안 오네
-
시험 난이도에 상관없이 원점수 80점 전후에서 고정이었는데 고2 때 이후로 90점대...
-
학과 상관없이 학교 최대한 올리면 인문 계열로 지원할 때 ㅇㄷ까지 가능할까요ㅠㅠ...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자