Passwd

동적 계획법 동적 계획법 (Dynamic Programming)이란 복잡한 문제를 간단한 여러 문제로 나누어 푸는 방법을 말한다. 부분 문제가 반복(Overlapping Subproblem)되거나 최적 부분 구조 (Optimal Substructure)를 가진 알고리즘을 효율적으로 해결할 때 사용한다. 최적 부분 구조 (Optimal Substructure) 답을 구하기 위해 수행한 계산을 반복해야 하는 문제의 구조 동적 계획법은 알고리즘이라기보다는 어떤 문제를 풀 때 그 문제를 더 작은 문제의 연장선으로 생각하고 기존에 구한 해를 활용하는 방법을 총칭한다고 이해하는 편이 좋다. 접근 방식 1. 큰 문제를 작은 문제로 표현할 수 있다. 예로 들어 피보나치는 아래와 같이 표현할 수 있다. $$ \begin..

개요 2022.06.18 - [Algorithm] 에라토스테네스의 체에서 정리한 에라토스테네스의 체 알고리즘은 소수를 찾는 방법으로 유명하다. 다만 범위 내의 모든 소수를 찾는 방법이기 때문에, 어떤 수가 소수인지 아닌지를 확인할 때는 효율적이지 않을 수 있다. 이 글에서는 어떤 수를 입력으로 받아, 그 수가 소수인지 아닌지를 판별하는 방법을 적어둔다. 접근 소수는 1과 자기 자신을 제외한 어떤 수로도 나누어 떨어지지 않는 수를 말한다. 어떤 수가 소수인지 아닌지 판별하기 위해서는 약수의 성질을 먼저 생각해봐야 한다. 약수는 제곱근을 기준으로 대칭을 이룬다. 따라서 어떤 수의 약수를 찾을 때 제곱근까지만 확인하면 나머지 약수는 자연스럽게 구할 수 있다. 즉, 어떤 수가 소수인지 아닌지를 판별하고 싶을 때..

개요 중복을 허용하고 반복 가능한 데이터에서 특정 데이터 기준으로 등장한 순서를 확인하고 싶다. 예로 들어 실행할 로직명과 설정값이 정의되어 있는 데이터가 있다고 할 때, 각 실행을 구분할 수 있도록 구분자를 추가해야 하는 상황이다. 추가할 구분자는 '실행 로직명_로직 등장 순서' 정도의 형식이면 충분할 것 같다. 반복 가능한 데이터에서 특정 데이터의 수를 세는 것이 아니라서 count 등의 함수는 사용할 수 없을 것 같아, 구현한 내용을 간단히 정리해 둔다. 사용한 프로그래밍 언어는 Python이다. 값 예시 처리할 데이터 예시는 아래와 같다. 실행할 로직명과 처리 데이터의 시작 시점, 처리 데이터의 종료 시점으로 구성되어 있다. washer_filter, 2023-11-17 03:00:00, 2023..

개요 수학에서 약수(divisior)란 어떤 수를 나누어 떨어지게 하는 수를 말한다. 알고리즘 문제를 풀다 보면 약수를 다룰 일이 많다. 보통 어떤 수의 모든 약수를 찾는다던가, 약수의 개수를 찾게 되는데 이 글에서는 어떤 수의 모든 약수를 찾는 방법을 적어둔다. 일반적인 방법 약수를 찾을 때 가장 단순하게 접근하는 방법은 반복문을 활용하는 것이다. 예로 들어 100의 모든 약수를 찾는다고 가정할 때 1부터 100까지의 모든 수에 대해 100을 나누어 떨어지게 하는 수를 찾는 것이다. def get_divisior(num): result = [] for i in range(1, num + 1): if num % i == 0: result.append(i) return result if __name__ =..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/132267 다음과 같은 콜라 문제가 있다. 콜라 빈 병 2개를 가져다주면 콜라 1병을 주는 마트가 있다. 빈 병 20개를 가져다주면 몇 병을 받을 수 있는가? 단, 보유 중인 빈 병이 2개 미만이면, 콜라를 받을 수 없다. 상빈이는 그림과 같은 방법으로 콜라 문제를 풀어냈다. 빈 콜라병 20병을 가져가서 10병을 받는다. 받은 10병을 비우고 5병을 받는다. 5병 중 4병을 비우고 2병을 받고, 또 2병을 비우고 1병을 받는다. 받은 1병과 5병을 받았을 때 남은 1병을 비워서 1병을 또 받는다. 따라서 총 10 + 5 + 2 + 1 + 1 = 19병의 콜라를 받는다. 만약 빈 병 a개를 가져다..

에라토스테네스의 체 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법 알고리즘 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 즉, 2부터 n까지의 모든 수를 나열한다. 지우지 않은 수 중 가장 작은 수를 찾는다. 이 수는 소수이다. 자기 자신을 제외한 소수의 배수를 모두 지운다. 더 지울 수가 없을 때까지 2 ~ 3 과정을 반복한다. 또는 \( \sqrt{n} \)의 정수부보다 작은 소수의 배수를 지우고 남는 수는 모두 소수이다. 그림의 경우, \( 11^2 > 120 \)이므로, 120보다 작거나 같은 수 가운데 2, 3, 5, 7의 배수를 지우고 남는 수는 모두 소수이다. 구현 Python으로는 아래와 같이 구현할 수 있다. def prime_list(n): # 에라토스테네스의 ..