Algorithm 뽀개기

알고리즘 기초를 풀면서 수학 문제만 풀다가 나도 남들이 말하는 dp 문제라는 걸 풀게 됐다! 뿌듯해요 Dynamic Programming 은 동적 프로그래밍이다. 복잡한 문제를 작은 문제로 분해하여 해결하는 알고리즘 기법 중 하나이다. 분할 정복과 유사하며 중복되는 부분 문제가 발생할 때 한 번만 계산하고 그 결과를 메모이제이션하여 다른 비슷한 부분 문제들이 다시 발생할 때 메모이제이션한 결과를 가져와 재활용한다.  동적 프로그래밍을 적용하기 위해서는 두 가지 조건을 만족해야한다. 전체 문제의 최적해가 부분 문제의 최적해로부터 구해질 수 있어야 하는 최적 부분 구조 (Optimal Substructure) 와 부분 문제가 중복되어 여러 번 반복 계산되어야 하는 중복되는 부분 문제 (Overlapping ..

해당 문제에서는 제시된 수 보다 작은 소수들을 모두 알아야 한다. 그래서 얼마 전 소수 구하기를 풀면서 읽었던 책의 에라토스테네스의 체 알고리즘이 생각났다. 에라토스테네스의 체는 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 N 보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 에라토스테네스의 체 알고리즘은 다음과 같다. 1. 2 부터 N 까지의 모든 자연수를 나열한다.2. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i 를 찾는다.3. 남은 수 중에서 i 의 배수를 모두 제거한다. (i 는 제거하지 않는다)4. 더 이상 반복할 수 없을 때까지 2 번과 3 번 과정을 반복한다. 나는 에라토스테네스의 체를... 어떻게 구현해야 할지 정말 모르..

이런! 최소공배수가 뭔지 기억이 안 날 뻔 했다. 심각한 수학 실력... 수학 포기하지 말걸~~~,,, 컴퓨터 공학과를 꿈꾸는 청소년 여러분 수학 포기하지 마세요 제발... 최대 공약수는 유클리드 호제법으로 구할 수 있다. 유클리드 호제법은 나누고 나눈 수를 나머지로 나누는 알고리즘이다.유클리드 호제법먼저 큰 수를 작은 수로 나눈 나머지를 구한다. 그 다음 나눴던 수를 나머지로 또 나누어 나머지를 구한다. 나머지가 0 이 되었을 때 마지막 계산에서 나누는 수로 사용된 숫자가 두 수의 최대공약수가 된다. 이를 반복문과 재귀함수로 구현할 수 있다. # 반복문def gcd(a,b) : while b != 0 : a, b = b, a % b return a# 재귀 함수 def gcd (a..

출력 형식이 잘못되었습니다 가 계속 나오던 문제이당 결국 해결한 방법은 버릇 처럼 사용하는 strip 을 없애는 것이었다. 문제를 잘 읽어보면 알파벳이 아닌 글자는 그대로 있어야 한다. 고 적혀 있다. 필요할 때만 쓰도록 하자.  그 외에 리스트를 출력할 때 문제가 요구하는 문자열 형식으로 출력하기 위해서 print(''.join(s) 를 사용했다. 대문자, 소문자일 때를 나누고 숫자, 공백 (즉 알파벳이 아닐 때) 도 조건을 나누었다. 아스키 코드를 사용해서 이들을 if 문으로 나누어 주고 아스키 코드를 다시 문자로 만드는 chr 을 사용했다. 이때 만약 13 을 더했을 때 대문자 범위, 또는 소문자 범위 등을 넘어갈 경우엔 13 을 빼준다.s = list(input())# 알파벳이 아닌 것은 그대로 ..