컴공일기 247
회문(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를 선물하세요.
-
친구가 호머식 2등급이라 그러는데 맞으면 맞은거고 틀리면 틀린거 아닌가 해서요.....
-
양곰탕은 16000원 꼬리곰탕은 2만원이네
-
수능 시뮬레이션 0
유튜브에 쳐서 들으면서 하는데 한숨빌런이 진짜 만나면 최악이겠다...한지문에 한번꼴로 한숨쉬네;;
-
실모풀면 맨날 독서만 6틀 7틀해서 2등급떠요.. 한 두 문제만 더 맞추고 싶은데...
-
오리 꽥꽥 7
-
국어 순서 0
공통 + 선택 포함 고전소설 제일 힘들어해서 고전소설 맨 마지막에 풀면 거의...
-
오르비 교재 0
오르비 클래스에서 교재구매할 때 결제 확인창이 원래 안뜨나요?
-
올해 독서 0
어느정도 난이도일 거 같나요 아무도 모르는 거긴 하지만 독서 약하고 문학 잘해서...
-
어느정도 푸셨어요 다들?
-
죽을까 그냥
-
상상 5-9 0
마킹 다 하니 79분 91 독서 인문 3점틀 문학 마지막 고전시가 2점틀,...
-
차엿어 .. 여자랑 단 둘이 만나는거 부담스럽대 .. 말도 안된다 ..
-
케이비에스ㅅㅅㅅ 한국바앙소옹 (띤딘띤딘딘딘 디리링~) 뚜 뚜 삐--- 빰바밤 빠밤밤밤
-
화작 0
제가 항상 실모를 보면 화작에서 시간을 줄이려고 노력을 해봐도 빠르면17분 늦으면...
-
수능시험이라는게 3
출제자가 개념들을 엮어서 구조를 만들어내면 수험생들은 그 구조를 추론해서 맞추는건데...
-
공콘 시즌2때 가서 오르비언들 많이 보곤 했는데 이젠 추억이네
-
논술날 봐요~~~~~ 제가 안전하게 통제하겠습니다!!!
-
응애 2
아아안.아.줘.
-
사회규범의 통제력 강화를 일탈행동의 대책으로 제시하는건 머튼이랑 뒤르켐 모두...
-
동생 인강패스는 내가 끊어줘야징
-
혹시 문학/비문학 고난이도 지문 하나씩 툭 던져주고 가주실 분..! 6
그냥 여러분 기준 어려웠던 지문(문학+비문학) 아무거나 1-2개씩 툭 던져 주시고...
-
15권정도 인데 개당 만원인데 그냥 일괄로 2만원에 사가실분
-
기출 얼추돌렿느데 이감하나볼까,,,,
-
국영수한과탐임 가격15000해드림
-
다 안다고 바로 문제 들어가기보다는 배경지식을 활용한 지문과 보기 읽기 해야 틀리지 않을 거 같음
-
여기서 잡히다가 왜 사동임?? 피동아닌가…
-
슈시붙어서 필요가 없다 ㅎ
-
뚜왕뚜왕 0
뚜왕뚜왕
-
11덮 확통 0
난이도 어땟나요 33분썻고 30번 틀렷는데 평가원 기출보다 좀 어려운거같던데 맞나요…
-
미적분하면 공통 3
도움되나요?? 확통이나 기하랑 다르게 논리가 비슷해서 도움될 거 같긴 한데 어떨지...
-
기분좋은 점수로 시작하는 하루 문학이 평소보다 쉬워서 너무 좋았음 그리고 한줄평...
-
삼각함수 그래프 1
제가 풀면서 쓴 풀이인데 맞나요? 이상한점 있나요?
-
문학때문에 시간 계속 개박살나서 다 꼬이네
-
나온 거 있으면 아는사람? 요즘 사설 독서론 가끔씩 틀려서 슬프네 생각해보니...
-
춘매전 뭔가 0
느낌이온다 문실정 출제자분 말도 일리가 있다 드문 능동적 주체적 여성인물..
-
내 정신머리
-
관리를 평가할 때는 개인의 능력이 아닌 도덕성만을 고려해야 한다 왜 틀린 거예요?...
-
예열지문이랑 요약본 들고갈건데 각 교시 쉬는시간마다 볼 수 있나요? 한국사랑...
-
오르비 망했네 6
딥피드 딱 5개 뜨는 거 중에 4개가 애니프사에다 나머지 하나는 제목 상태가...
-
ㅗ 화작 2점 틀리는 사람을 뭐라고 불러요?
-
허락받는건가요?? 감독관한테
-
아 인생 8
-
1. 잠깐이라도 충분히 자며 에너지 충전하기 공부 슬럼프에 빠진 학생들은 지금까지...
-
바로 75점 떠버리네;;;
-
오느레 급씩 2
히히.. 마시게따
-
나만 어려웟나 ..
-
오바임뇨?? 걍 기출 더 보는게 낫나..
-
심찬우 나와서 노래부르고 춤 춤?
-
근처에서 혼밥 하실거임? 아님 콘섵만 보고가나
-
생글 첫강듣고 독재에서 숨죽여 울었던게 어끄제같은대 벌써 수능이 열손가락으로...
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자