후회가 없도록

문제 출처: https://www.acmicpc.net/problem/10942 1. 결과 메모리 60000KB, 시간 1816ms 2. 풀이 동적 계획법을 다루는 문제에서 팰린드롬(Palindrome)은 대표적인 예제 중 하나이다. ABA, ABCBA와 같이 앞에서 한 글자씩 읽어도, 뒤에서 한 글자씩 읽어도 같은 문자열이 되는 경우를 팰린드롬이라고 한다. 주어진 문자열에서 가능한, 가장 긴, 연속된 팰린드롬 문자열의 길이를 구하는 문제가 팰린드롬 관련 문제 중 가장 기초가 되는 문제이고, 그 외에 가장 긴 팰린드롬 자체를 구하는 문제나 이 문제처럼 팰린드롬의 여부를 묻는 문제도 있다. 여기서 말한 다른 팰린드롬 문제는 블로그에 알고리즘 풀이를 기록하기 이전에 풀어봤기 때문에 아직 없지만, 추후에 특정..

문제 출처: https://www.acmicpc.net/problem/11444 1. 결과 메모리 29200KB, 시간 88ms 2. 풀이 이 문제는 평범한 재귀 호출이나 동적 계획법과 같은 연산을 통해 구하기가 쉽지 않다. 문제 조건에서 볼 수 있듯이 Fn을 구하는데, 해당 n이 최대 10^17(10의 17제곱)까지 가능하기 때문이다. 또한 피보나치 수열은 궁극적으로 앞의 연속된 두 숫자를 알아야만 그 다음 숫자를 구할 수 있고, 앞의 연속된 두 숫자는 또 해당 숫자의 앞의 연속된 두 숫자를 알아야만 연산이 가능하다. 즉, 기존의 피보나치 수열 개념( Fn = Fn-1 + Fn-2 (n ≥ 2) )은 연쇄적으로 연산이 되기 때문에, 각각의 독립된 소문제 해결을 통해 큰 문제를 해결하는 일반적인 분할 정..

문제 출처: https://www.acmicpc.net/problem/11401 1. 결과 메모리 188804KB, 시간 1144ms 2. 풀이 이 문제를 처음에 풀이할 때는 혼란스러웠다. 분할 정복과 재귀 호출 등을 사용해서 팩토리얼 연산 횟수를 최대한 줄이는 것이 문제의 요점이라고 생각했다. 하지만 그렇게 풀이한 코드는 채점 결과 런타임 에러를 발생했고, 생각해보면 최대 400만 번의 재귀 호출이 발생할 수 있기 때문에 납득할 수 있는 결과였다. 하지만 그렇다면?? 어떤 풀이로 접근을 해야 할지 고민을 하며 다른 블로그와 풀이 아이디어만을 참고하려고 검색하던 중 '페르마의 소정리'를 이용하는 문제라는 것을 알았다. 페르마의 소정리란 코드의 주석 부분에 작성한 것처럼 소수인 p와 그 p의 배수가 아닌 ..

문제 출처: https://www.acmicpc.net/problem/1780 1. 결과 메모리 67648KB, 시간 3592ms 2. 풀이 분할 정복을 최근에 제대로 배워보면서 분할 정복과 재귀 호출을 연습하게 되는 계기가 되었다. 또한, 나로서는 이 문제에서 하나의 함수만으로 재귀 호출 후 답을 반환하는 아이디어가 쉽게 떠오르지 않았기 때문에 전역 변수를 사용했다. 각 함수 내에서 global을 통해 counts가 전역 변수임을 알렸는데, 이런 전역 변수 선언은 가장 함수의 맨 위에서 이루어져야 한다. 파이썬은 위에서부터 순서대로 읽어나가는 경향이 있기 때문에, 함수의 중후반에서 전역 변수 선언을 했을 때는 그 이전 줄에서 이 counts라는 변수를 읽지 못하고 오류가 발생했다. 오히려 전역 변수를 ..

문제 출처: https://www.acmicpc.net/problem/10773 1. 결과 메모리 29980KB, 시간 4908ms 2. 풀이 이 문제는 솔직히 전혀 어려웠거나 어떤 이슈가 있는 것이 아니고, 직접 스택이라는 추상적 자료형을 클래스로써 구현한 코드를 담고 있기 때문에 남긴다. 파이썬의 리스트를 이용해서 구현해서 충분히 쉽게 풀이가 가능한 문제이다. import sys class Stack: def __init__(self): self.stack = [] def push(self, x): self.stack.append(x) def rmpop(self): if self.stack: self.stack = self.stack[:-1] def pop(self): if self.stack: re..