Passwd

문제 문제 : 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. 숫자를 나눈 몫과 나머..

LZW LZW (Lempel-Ziv-Welch)는 Abraham Lempel, Jacob Ziv와 Terry Welch 만든 공통 무손실 데이터 압축 알고리즘이다. 1978년에 Lempel과 Ziv가 공개한 LZ78 알고리즘을 1984년에 Welch가 개선하여 공개했다. 구현이 간단하고 높은 처리량을 제공할 수 있다. 유닉스 파일 압축 유틸리티인 compress의 알고리즘이며 GIP 이미지 포맷에도 사용된다. 핵심 아이디어는 데이터 공간을 절약하기 위해 패턴을 만들어서 재사용하는 것이다. 일반적으로 ASCII Code는 문자를 8bit로 나타내므로 최대로 표현할 수 있는 문자의 개수는 256개이다. 여기서 LZW는 문자를 9~12bit까지 확장하여, 총 4096개 공간 중 기본 문자 256개 공간을 제외..

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/17684 어피치는 메신저에서 전송되는 메시지를 압축해 전송 효율을 높이는 업무를 맡았다. 메시지를 압축해도 전달하는 정보가 변경되서는 안 되기 때문에 압축 전 정보를 복원할 수 있는 여러 가지 무손실 압축 알고리즘 중, 성능이 좋고 구현하기 좋은 LZW(Lempel–Ziv–Welch) 압축을 구현하기로 했다. LZW 압축은 1983년에 발표된 알고리즘으로, 이미지 파일 포맷 GIF 등에서 사용된다. 압축 과정은 다음과 같다. 길이가 1인 모든 단어를 포함하도록 사전을 초기화한다. 사전에서 현재 입력과 일치하는 가장 긴 문자열 w를 찾는다. w에 해당하는 사전 색인 번호를 출력하고, 입력..