알고리즘/투 포인터2 [Baekjoon - 22862] 가장 긴 짝수 연속한 부분 수열 (large) with Python 주저리 주저리 투 포인터 문제 중 대표적인 문제 중 하나라고 생각한다. 이런 유형의 문제는 꼭 풀어봐야 생각하는게, 만약 코테에 이런 문제가 나올 시 이것이 투포인터 인지 아닌지 애매해서 못 풀수도 있을 거 같다라는 생각을 든다. 다들 알다시피 투 포인터는 대충 두 점을 같은 위치에서 시작하느냐 or 양 끝으로 시작하느냐의 문제가 대부분인 듯 하다. 난 개인적으로 같은 위치에서 시작을 하는 경우는 이제 특정 조건에 만족하는 길이를 구할때의 문제에 적용하고, 양 끝은 이제 양 끝에서 부터 접근해서 풀면 쉬울것 같다(?) 라고 판단시에 푸는 듯 한다. 문제 해결 이 문제는 k개의 원소를 지워 가장 긴 짝수 의 수열을 만드는 것이다. 그럼 당연하게도... 지우는 원소는 뭐가 되겠는가 => 홀수다 그래서 이 문.. 2023. 4. 25. 17609 - 회문 with Python 주저리 주저리 이 문제를 보자마자 그대로 문자를 뒤집어서 계산하는 것은 안 될까 싶었다. 하지만 유사 회문 덕에 모든 문자열을 탐색해야 함으로 O(n**2)이 걸릴 거라 생각하고 한번 짜봤는데, 역시 시간 초과... 당연히 다른 접근으로 접근해보자 문제 해결 회문을 탐색하는 방법으로는 그냥 맨 앞과 맨 뒤에 포인터를 두고 만약 두개의 포인터가 가리키는 문자가 서로 같으면 한 칸씩 움직이는 아주 간단한 방법이 존재한다. 다만 여기서는 유사 회문이 존재한다. 따라서 그냥 만약 다르다! 그러면 왼쪽과 오른쪽 둘 중 한 곳만 움직이게 해서 그 다음을 체크하면 될 것이다. 한번 코드로 직접 보면 더 이해가 쉽게 간다. 코드 import sys input = sys.stdin.readline t = int(inpu.. 2023. 3. 30. 이전 1 다음 728x90