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으..

백준허브(BaekjoonHub) LeetCode의 개인 풀이를 Git 저장소에 자동으로 Push 하는 LeetHub를 포크 해서 개발된 크롬 확장 프로그램. 오픈 소스로, 기존에 풀었거나 풀어낼 문제 풀이를 저장소를 통해 관리하고 싶다면 사용할 수 있다. 설치 및 설정 1. 아래 설치 크롬 웹 스토어 링크로 접근한 뒤 Chrome에 추가 버튼을 클릭한다. 링크 : 백준 허브 크롬 확장 프로그램 2. 브라우저 오른쪽 상단 바에서 확장 프로그램 > BaekjoonHub를 클릭한 뒤, GitHub와 연동하기 위한 Authenticate 버튼을 클릭한다. 3. Github에 로그인하면, 아래와 같이 BaekjoonHub를 통해 관리할 Github 저장소를 설정할 수 있다. 새 저장소를 만들거나 기존 저장소로 연..

문제 https://www.acmicpc.net/problem/9546 n명의 승객을 태우고 있는 3000번 버스는 버스 정류장마다 문을 연다. 정류장마다 타고 있는 승개의 수의 절반과 반 명의 승객이 내린다. k개의 정류장에서 승객이 내렸고, 마지막 정류장에서 승객이 없었다면 맨 처음 타고 있던 승객이 몇 명인지 구하여라. 풀이 t번째 정류장에서의 승객의 수를 \( n_t \)라고 하자. 정류장마다 내리고 남은 승객의 수는 아래와 같이 계산할 수 있다. $$ \begin{matrix} n_t - (0.5n_t + 0.5) = n_{t+1} \\ 0.5n_t - 0.5 = n_{t+1} \end{matrix} $$ 마지막 정류장에서의 승객이 0명이므로, 정류장이 1개인 경우, 2개인 경우, 3개인 경우…..

문제 https://www.acmicpc.net/problem/9081 단어를 입력받아, 그 단어를 이루는 알파벳들로 만들 수 있는 단어들을 사전 순으로 정렬할 때에 주어진 단어 다음에 나오는 단어를 찾는 프로그램을 작성하라. 입력 첫 줄은 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 알파벳 대문자로만 이루어진 단어로 공백은 없다. 풀이 파이썬에서 문자(chr)는 대소 관계 비교가 가능하므로 직전에 풀었던 2022.05.10 - [BOJ] 10972 - 다음 순열(next permutation) 문제를 활용하면 쉽게 풀어낼 수 있다. 차이가 있다면 값의 중복 여부인데, 이는 값을 교환할 위치 i - 1과 j를 찾아내려 갈 때의 조건을 크거나 같을 때 반복하도록 수정하면 된다. import sys..

문제 https://www.acmicpc.net/problem/1476 준규가 사는 나라에서는 숫자 E, S, M 3개를 이용해서 연도를 나타낸다. 그리고 이 세 수는 아래와 같은 범위를 가진다. 1 ≤ E ≤ 15 1 ≤ S ≤ 28 1 ≤ M ≤ 19 우리가 알고있는 1년은 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다. 예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 되면 16 16 16이 아니라 1 16 16이 된다. E S M 년도를 입력받아, 우리가 알고 있는 연도를 계산하라. 풀이 내 풀이 나는 연도를 증가시킨 후, 그 연도를 E S M 연도와 비교하는 방식을 사..

문제 https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 1부터 N까지의 수로 이루어진 순열을 입력으로 받아, 사전 순으로 다음에 오는 순열을 구하여라. 사전 순으로 가장 첫 순열은 오름차순으로 이루어진 순열이고, 가장 마지막 순열은 내림차순으로 이루어진 순열이다. 예시 ) 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 입력 첫째 줄은 N을, 둘째 줄은 순열이 주어진다. 입력 받은 순열이 가장 마지막 순열인 경우에는 -1을 출력한다. 풀이 1. 순열의 오른쪽 끝에서부터..

문제 https://www.acmicpc.net/problem/2556 자연수 n을 입력받은 후, 지금까지 안 나온 별 찍기 방식으로 n개의 줄에 걸쳐 별을 적절히 찍으세요. 풀이 문제가 꽤 당황스러운데…… 별 찍기 관련 문제는 https://www.acmicpc.net/workbook/view/20 에 모여있다. 별 찍기 문제를 1번부터 13번까지 확인해보면 직각삼각형, 이등변삼각형, 마름모, 나비 모양, 모래시계 모양 등을 출력하도록 요구하고 있는데, 정작 정사각형 모양은 요구한 적이 없는 것을 알 수 있다. 즉, 정사각형 모양이 되도록 별을 찍으면 된다. import sys n = int(sys.stdin.readline()) for i in range(n): print("*" * n)

문제 https://www.acmicpc.net/problem/1269 1269번: 대칭 차집합 첫째 줄에 집합 A의 원소의 개수와 집합 B의 원소의 개수가 빈 칸을 사이에 두고 주어진다. 둘째 줄에는 집합 A의 모든 원소가, 셋째 줄에는 집합 B의 모든 원소가 빈 칸을 사이에 두고 각각 주어 www.acmicpc.net 자연수를 원소로 갖는 공집합이 아닌 두 집합 A와 B가 있다. 두 집합 A와 B에 대해 (A-B)와 (B-A)의 합집합을 A와 B의 대칭 차집합이라고 할 때, 그 원소의 개수를 구하여라. 예시 ) $$ A = \{1, 2, 4 \}, B = \{2, 3, 4, 5, 6 \}$$ $$ A-B = \{1 \}$$ $$ B-A = \{ 3, 5, 6\}$$ $$ A \triangle B=(A..

문제 https://www.acmicpc.net/problem/1748 첫째줄에 N을 입력받아, 1부터 N까지의 수를 이어서 쓴 하나의 수의 자릿수를 구하여라. 예시) n = 15 이어쓴 수 : 123456789101112131415 자릿수 : 21 풀이 틀린 풀이 N까지 이어서 쓴 수를 실제로 구한 뒤, 그 길이를 출력하는 방법을 썼다. import sys n = int(sys.stdin.readline()) print(len("".join([str(i) for i in range(1, n + 1)]))) 무식한 방법이었는지, 메모리 초과로 틀린 풀이였다. 맞은 풀이 i번째 자리수가 등장하는 개수와 N과의 관계를 생각해보자. 자릿수 범위 개수 1번째 (1의 자릿수) 1 ~ N N - 1 + 1 2번째 ..