컴공일기 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를 선물하세요.
-
젭알
-
인버스 롱 0
곧 시계경제 도미노 충격여파 온다 꽉 잡고 인버스 롱 올인
-
외롭다 0
그치만 수능은 보고 죽어야겠다 다 망했지만 수능만큼은 아직
-
25시행 중1,고1 국어 시험지 현금 2만원 제공(선착순), 고1 국어, 고2 문학, 고3 특강 분석 문제 배포 0
안녕하세요 나무아카데미입니다. 고1 공통국어, 고2 언매, 고3 특강 분석 기출...
-
씨발 2
형이고뭐고 다필요없어 결국 우린 적이야
-
타이완 32% 베트남 46% 중국 34% 일본 24% 한국 25% 이렇게 관세...
-
현생이 바쁘다
-
기아 맛 갔네 0
이것뭐예요
-
조회수가 이렇게 잘나오는데 안다룰수가 없지~
-
엄기은 이훈식 0
솔텍 할까요 아님 엄기은쌤 피크 들을까요?
-
웃다가울다가하니
-
수특에 관세지문 있음 한번 읽어보시길
-
샹기부 자체가 단순 사실 나열이라 걍 사람이 써도 ai같음
-
학교생활이나 공부법 같은 거 멘토해주는 거고 강사비? 조금 주는 거 같던데...
-
강릉 정박 선박서 '코카인 1.7t'...역대 최대 1
[앵커] 한·미 공조 수사로 강원 강릉 옥계항에 정박한 외국 화물선에서 코카인으로...
-
[단독]현역 군인 매수, 한미훈련 정보 빼낸 중국인 체포 1
현역 군인을 포섭해 군사기밀과 비공개 자료를 수집해 온 중국인 일당 중 행동책이...
-
-
디른 친구들이 AI 대필 의심스럽다고 검사했을때도 높게 나왔는데, 제가 했을때도...
-
기코 2회독하고 한완수로 한바퀴 더 돌렸는데 입문 n제는 몇권 정도 푸는게 좋을까요?
-
좋은 아침 0
오늘은 다시 열심히 해볼게요
-
아직도 뻐기면 제적시키는 게 맞는듯
-
좋을텐데 0
너의 손 꼭 잡고 그냥이 길을 걸었으면내겐 너뿐인걸 니가 알았으면 좋을텐데
-
관세가 .. 1
이거 뭐노 ㅋㄴㅋㅋㅋㅋㅋㅋ 미국도 드디어 미쳤구만
-
정상화되길 바랐다면 너무 큰걸 바랐던걸까
-
아~ 수시 적폐 0
학교에 차 끌고 오던 양아치새끼 외국인전형으로 뭐 고려대 글로벌자율? 들어갔는데 배 존나 아프네
-
일단 학원에서 신청했는데 학원을 그때까지 다닐지 모르겠어서 교육청가서 중복신청...
-
얼버기 0
-
ㅇㅂㄱ 3
좋은아침이에요
-
D-224 0
영어단어 영단어장 day 12(480단어) 모르는 단어만 복습 +day 4 추가...
-
자러감 3
학교 좀만 늦게 가야지
-
출근 1
이따 봅시다
-
틀딱입니다. 수능수학을 준비한다느 가정하에, 개념원리 등을 한번 돌리고 이후 볼 수...
-
왜냐면 이제부터 기다림이 24시간이 넘을 때마다대가리를 존나 쎄게 쳐서 제 머릿속을...
-
상호관세 25퍼센트 ㅋㅋㅋㅋㅋㅋ 미국 국민이 멍청하니까 온 세상이 고통받는구나
-
-
얼버기 1
ㅎ
-
빅포텐 문항수 0
왤케 적냐 병호야 뒤질래
-
얜 ㄹㅇ 눈풀로 풀리네 30번인데 이건 좀
-
레알과 바르셀로나를 낳았는가
-
죽여줘... 3
느어엉
-
졸려..
-
난 아직 안잤단말야
-
아가 기상 0
기요미 나 일어났어
-
얼버기 0
좋은아침되세요
-
[속보] 트럼프, 상호관세 발표…韓 25% 日 24% 中 34% 부과 6
미국 정부가 한국에서 생산돼 미국으로 수입되는 제품에 25%의 상호관세를 부과한다고...
-
내가 만든 내 세상이다
-
69수 원점수 92 100 96
-
얼버기 4
안농
-
오르비 안녕히주무세요 10
해뜨고 봐요
-
똥먹기 2
미소녀 똥 우걱우걱
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자