컴공일기 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를 선물하세요.
-
아 뭔 자신감이지.. 12
왜 원광치대는 될 것 같냐 너무 기대하면 실망하는데
-
????????????? ????????????? 진짜 뭐지
-
아까 스나 글 쓴사람인데 이 점수는 노양심인가요? 10
화작 2컷 간당 미적 100 영어 1 사탐 2개 3, 4 등급 앞의글 답변해주셔서...
-
예상해보는것도 메타인지에 속하는건가요
-
야 솔직히 스벅 자바칩 프라프치노 미만잡 아니냐? 31
반박시 초알못(초코를 잘 모르는 이) ㅋㅋ
-
언매 vs 화작 2
둘의 차이점이 시간인가요? 고2 국어 모고 3등급 나오는데 뭘 하는게 좋을까요?...
-
인생 ㅈ같다 0
내신 좆같다 진짜
-
행복하다 수능때까지만 열심히하자
-
생1 교육청 0
교육청이랑 평가원 난이도 차이 심한가요?? 지금 3개년치 교육청+평가원 싹 다...
-
국어 1~2 왔다갔다 하시는분들 실모 지금 몇개 푸시나요 9
1주일에 2개씩 푸는데 적은걸까요
-
‘주 44시간, 월급 3000만원’ 한국 의사들, 베트남 병원 수십명 지원 8
[파이낸셜뉴스] 한국 의사들의 베트남 진출이 활발해 지고 있다. 16일 조선일보에...
-
님이 지금 응시한 시험지는 붙는 성적이고 재시험 시험지는 유형이 다르니 다른...
-
이제는 뭔가 안쓰러움.. 과연 무슨 사연이 있는걸까..?
-
연세대 수험생 "집단소송"…전형료 32억 받고도 부실관리 논란 1
연세대학교 수시 논술 문제 유출과 관련해 수험생들이 논술시험 무효를 청구하는...
-
무슨요일에 들으시나요?? 저는 원래 수욜마다 들었다가 사정때매 이틀 미뤄서 금욜에 듣는데
-
컨디션 영 별로이면 걍 조퇴때리나요?아니면 걍 끝까지 악깡버하나요
-
포괄적 권리(자유, 평등, 행복추구권)라고 보나요?
-
연세대 수험생 ‘양심 선언’…“논술문제 3개, 다른 수험생에 문자로 전달” 15
2025학년도 연세대 수시모집 자연계열 논술시험 문제 유출 논란과 관련해 ‘시험지를...
-
국어 별로 못하는데 검토까지 다해도 20분 남네...
-
38점 뭣.. 봇치는 지구과학을 몬해
-
공포영화 보러옴 2
으흐흐
-
6시간 잤다고 뻗는 게 말이 되나 운동 좀 해놓을걸..
-
인류는 개@%@$임
-
경희대 봉사시간 보나요? 봉사활돝 대학에서 안본다길래 1학년때 헌혈도 안하고 그래서...
-
“월 수입 5000만원?” 100만 유튜버된 ‘효린’…사진 속 ‘골드버튼’ 실체 1
[헤럴드경제= 박영훈 기자] “100만 유튜버 월 수입 5000만원?” 가수 효린이...
-
대충 화작2컷 미적100 사탐2개 서성한이상 낮공 자연대 가능하려나
-
이감 푸니까 진이 빠지는듯… 시간도 부족하고; 2-3일에 한번씩은 풀어야겠음
-
언매고 9모 100 9덮 92 였어요 지금 수탐 급해서 수탐만 죽어라하는중
-
Lv.20 3
!
-
이제 국어지문같은거는 손도 못대겠고 영어도 집중력이 씹창났어 탐구도 이제 텍스트자체를 잘 못읽겠고
-
폭발원리 1
이게 뭐야? 도서관 가서 찾아보면 나오려나..
-
나도 그렇고 ㅋㅋㅋ 운동이든 게임이든 공부든 열정적이긴 한듯 ㅋㄱ
-
수능끝나고 퇴소하면 걍 인스타 싹다 언팔치고싶은데,,
-
덕갈하고싶다 3
덕코 갈취 하고 싶다라는 뜻
-
한기호 "北은 1만명 파병, 우리도 우크라에 참관단 보내자" 13
(계룡=뉴스1) 허고운 기자 = 우리 군이 우크라이나 전쟁에 '참관단'을 파견해야...
-
오늘 아직 핫식스 0캔
-
수능 전날이나 전전날에 이감 풀면 머리만 아프고 현타 올 것 같은데 수능 직전에 풀...
-
쿠쿠리가 오르비에 무한동력장치 심어놓은듯 ㄹㅇㅋㅋ
-
아니 진짜 정시n수가 논술최저도못맞출거같은게말이되냐고 11
하진짜씨발어캄?
-
ㅋㅋㅋㅋ 8
ㅋㅋㅋㅋㅋㅋㅋㅋ
-
한국 의사들 "베트남으로 갈래요"…외국인 의사 영어시험 수십 명 응시 3
베트남에 진출하는 우리나라 의사가 크게 늘어날 것으로 전망된다. 최근 한국...
-
특히 영어는 현역이 더잘하는거같음 어떨때는
-
이거 뭔가 효과없는데? 싶다가도 딱 1~2주만 참고 계속 쓰면 걍 삶의 질이 달라짐...
-
진짜 폭발원리, 상대성이론, 열역학 다 싸그리 ㅄ임 7
인류는 그냥 ㅄ집단임
-
씨발입갤 ㅋㅋㅌㅌ
-
내가 저번에 작년인가 흉기난동 관해서 개소리 씨부렸던 거 보강함 3
저 당시 경제 불경기에 취업난 때문이라고 했던 거 같은데 추가로 요소를 더해 보자면...
-
글도 자주 안 올리고 입시도 이제 안 하는 뻘글러 미대생인데
잘 자
Was it Eliot's toilet I saw?
Bool isPalindrome(const char*);
const char Text[] = “wasiteliotstoiletisaw”;
std::cout << isPalindrome(Text) << std::endl;
문자열 문제는 파이썬으로 풀자