Passwd

문제 문제 : https://www.acmicpc.net/problem/1890 각 칸에 수가 적힌 N * N 크기의 게임판이 있다. 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프하여 이동하는 것이다. 각 칸에 적힌 수는 현재 칸에서 갈 수 있는 거리를 뜻한다. 단, 0은 종착점을 의미한다. 오른쪽이나 아래쪽으로만 이동할 수 있고, 한 번 점프하는 중간에 방향을 바꿀 수 없다. 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 이동할 수 있는 경로의 수를 구하여라. 접근 2024.04.08 - [백준] 11048 - 이동하기와 비슷한 문제인데, '이동하기'는 한 번에 한 칸씩 움직이는 반면 '점프'는 이동할 수 있는 칸의 수가 정해져 있지 않다. 때문에 현재 위치..

문제 문제 : https://www.acmicpc.net/problem/11048 1 * 1 크기의 방에 사탕이 놓여져 있는 N * M 크기의 미로가 있다고 하자. 미로의 가장 왼쪽 윗 방의 좌표는 (1,1)이고, 가장 오른쪽 아랫방 좌표는 (N, M)이다. 또한 사람이 (r, c) 좌표의 방에 위치하고 있으면 (r+1, c), (r, c+1), (r+1, c+1) 방향으로만 이동할 수 있고, 방을 방문할 때마다 방에 놓여진 사탕을 모두 가져갈 수 있다. 사람이 (1,1) 좌표 방에서 (N, M) 좌표 방으로 미로를 빠져나온다고 할 때, 가져올 수 있는 사탕 개수의 최대값을 구하여라. 접근 이 문제도 동적 계획법과 관련된 문제다. 현재 위치한 방을 어떻게 왔는지 고려해보면 아래 그림을 떠올릴 수 있다. ..

문제 문제 : https://www.acmicpc.net/problem/10844 45656과 같이 인접한 자리수의 차이가 1인 수를 계단 수라고 한다. 수의 길이 n이 주어질 때, 길이가 n인 계단 수의 계수를 구하여라. 단, 0부터 시작하는 수는 계단 수가 아닌 것으로 취급한다. 접근 이 문제는 2024.04.04 - [백준] 11057 - 오르막 수와 비슷하게 동적 계획법으로 접근할 만한 문제다. 수의 길이가 1일 때, 계단 수의 1부터 9까지 수가 해당된다. 그리고 수의 길이가 2인 경우, 각 자리 수 마다 계단 수는 다음과 같이 생성할 수 있다. 개수를 표시하면 아래 그림과 같다. 참고로 0으로 시작하는 수의 개수는 다음 길이의 계단 수의 개수를 구할 때 구하기 위해서 구해야 한다. 즉, 숫자 ..

문제 문제 : 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://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..