Passwd

문제 문제 : 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에 해당하는 사전 색인 번호를 출력하고, 입력..

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

문제 문제 : https://school.programmers.co.kr/learn/courses/30/lessons/76502 다음 규칙을 지키는 문자열을 올바른 괄호라고 정의한다. (), [], {}는 올바른 괄호다. A가 올바른 괄호면 (A), [A], {A}도 올바른 괄호다. []가 올바른 괄호 문자열이므로, ([])도 올바른 괄호다. A, B가 올바른 괄호면 AB도 올바른 괄호다. {}와 ([])가 올바른 괄호이므로, {}([]) 도 올바른 괄호다. 대괄호, 중괄호, 소괄호로 이루어진 문자열 s가 매개변수로 주어질 때, s를 왼쪽으로 x (0 ≤ x < (s의 길이)) 칸만큼 회전시켰을 때 s가 올바른 괄호 문자열이 되게 하는 x의 개수를 반환하라. 풀이 매개변수 s의 길이가 1000 이하로 제..