Passwd

문제 문제 : https://www.acmicpc.net/problem/11057 오르막 수란 수의 자릿수가 오름차순을 이루는 수를 말한다. 이때 인접한 두 수의 값이 같아도 오름차순을 준수하는 것으로 판단한다. 예로 들어 2234, 3678, 1119은 오르막 수이다. 하지만 2232, 3676, 91111은 오르막 수가 아니다. 수의 길이 N이 주어졌을 때 오르막 수의 개수를 구하여라. 수는 0으로 시작할 수 있다. 단, 결괏값은 10007로 나눈 수로 출력한다. + 다른 사람의 풀이를 참고했다. 접근 동적 계획법으로 접근하면 좋은 문제다. 수의 길이가 1인 경우, 오르막 수는 0, 1, 2, 3 …… 9가 해당된다. 수의 길이가 2인 경우, 첫번째 자리의 수에 따라 다음으로 올 수 있는 수의 개수는..

문제 문제 : https://www.acmicpc.net/problem/10448 삼각수 Tn(n ≥ 1)는 그림에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. 또한 자연수 n에 대해 다음과 같은 공식을 만족한다. $$T_n=1+2+3+...+n=n(n+1)/2$$ 1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. $$4=T_1+T_2$$ $$5=T_1+T_1+T_2$$ $$6=T_2+T_2=T_3$$ $$10=T_1+T_2+T_3=T_4$$ 이 증명은 가우스가 다이어리에 “Eureka! num = Δ + Δ + Δ” 라고 적음으로써 유레카 ..

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/250121 AI 엔지니어인 현석이는 코드 번호(code), 제조일(date), 최대 수량(maximum), 현재 수량(remain)으로 구성된 데이터를 분석하고 있는데, 조건을 만족하는 데이터만 뽑아서 정렬하려고 한다. 데이터가 저장된 이차원 정수 리스트 datam, 데이터를 필터링할 기준을 의미하는 문자열 ext, 필터링할 기준값을 의미하는 정수 val_ext, 정보를 정렬하는 기준을 의미하는 문자열 sort_by가 주어질 때, data에서 ext 값이 val_ext보다 작은 데이터만 뽑은 후, sort_by 값을 기준으로 오름차순으로 정렬하여 반환한다. 접근 Pandas를 사용하라고..

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/250137 어떤 게임에 붕대감기라는 기술이 있다. 붕대감기 기술은 t초 동안 실행되는데 1초마다 x만큼의 체력을 회복한다. 또한 t초 연속으로 붕대를 감으면 y만큼의 체력을 추가로 회복한다. 캐릭터가 붕대감기 기술을 쓰는 도중 몬스터에게 공격당하면 기술이 취소되며 체력을 회복할 수 없다. 기술이 취소되거나 기술이 끝나면 캐릭터는 즉시 붕대감기 기술을 재사용하며 연속 성공 시간이 초기화된다. 게임 캐릭터는 최대 health만큼의 체력을 가질 수 있다. 몬스터의 공격을 받으면 피해량만큼 캐릭터의 체력이 줄어들며, 현재 체력이 0 이하가 되면 죽는다. 붕대감기 기술의 시전 시간, 초당 회복량..

문제 문제 : https://www.acmicpc.net/problem/11727 양의 정수 n을 입력받아 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 10,007로 나눈 나머지를 구하여라. + 이번 글도 다른 사람 풀이를 참고한다. 점화식 n = 1일 때부터 시작해 결과를 그려보면 아래 그림과 같다. 조금 더 그려보면 아래와 같은 패턴이 반복되는 것을 확인할 수 있다. 즉, 확인한 패턴을 점화식으로 표현하면 다음과 같다. $$counts(n)=counts(n-1)+2counts(n-2)$$ 이전 값 하나만 참조할 뿐 아니라, 여러 값을 참조하는 경우도 충분히 있을 수 있다……. 생각해보면 피보나치 함수도 그렇다. 구현 이전에 계산한 값을 반복적으로 확인해야 하..

개요 2024.01.31 - [Alogrithm] 동적 계획법 (Dynamic Programming) 이란에서 동적 계획법의 개념과 접근 방식에 대해 간단히 살펴보았는데, 아무래도 관련 문제를 직접 해결해보는 편이 더 익숙해질 것 같아 문제를 풀어보려고 한다. 다만 이번 글에서는 다른 사람의 풀이(https://beginnerdeveloper-lit.tistory.com/81)를 참고한다. 🤔 비슷한 문제로 https://school.programmers.co.kr/learn/courses/30/lessons/154538 가 있는데, 이 문제는 직접 풀어보려고 한다. 문제 문제 : https://www.acmicpc.net/problem/1463 정수 X에 사용할 수 있는 연산은 세 가지이다. X가 3으..

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

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/132265 철수는 여러 토핑이 일렬로 올려진 롤케이크를 두 조각으로 잘라서 동생과 한 조각씩 나눠 먹으려고 한다. 두 사람은 조각의 크기보다 토핑의 종류를 더 중요하게 생각해, 각 조각에 올라간 토핑의 가짓수가 동일하면 공평하게 나눈 거라 생각한다. 예로 들어, 롤케이크에 4가지 종류의 토핑이 올라가 있고 그 토핑을 1, 2, 3, 4와 같은 번호로 표시했을 때 롤케이크의 토핑은 [1, 2, 1, 3, 1, 4, 1, 2]라고 표현할 수 있다. 이 롤케이크를 공평하게 나눈 경우는 [1, 2, 1, 3], [1, 4, 1, 2] 또는 [1, 2, 1, 3, 1], [4, 1, 2]가 될 ..

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

개요 Python으로 진수 변환하는 방법에 대해서는 2022.06.08 - [BOJ] 2998 - 8진수에서 살펴보았었는데, 10진수를 2, 8, 16 진수 외의 다른 진수의 수로 변환할 때는 직접 변환 함수를 구현해야 한다. 이 글에서 구현해보려고 한다. 진수 변환 방법 수학적으로 진수를 변환하는 방법은 다음과 같다. 1. 어떤 수를 진수로 나눠 몫과 나머지를 구한다. 2. 몫이 나누어지지 않을 때까지 연산을 반복한다. 3. 나머지를 역순으로 읽는다. 이 과정을 Python 코드로 구현한다. 코드 구현 - 재귀함수 진수 변환은 재귀함수를 이용해 간단히 구현할 수 있다. 1. 자릿값을 초기화한다. tmp = string.digits + string.ascii_uppercase 2. 숫자를 나눈 몫과 나머..