본문 바로가기
728x90

파이썬

 (171)
[백준] 11726번 2×n 타일링 [Python] 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수 더보기 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. $($1 ≤ n ≤ 1,000$)$ 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. n개의 2x1 블럭과 r개의 1x2 블럭이 있을 때, 1x2 블럭이 들어갈 수 있는 2x1 블럭 사이 공간은 n+1개이고, 중복 가능 하므로 \begin{align} _{n+1}H_{r} = _{n+1+r-1}C_{r} = _{n+r}C_{r}\end{align} import sys from mat..
[백준] 1475번 방 번호 [Python] 방 번호 숫자를 만들기 위해 필요한 0~9 숫자 세트 개수 구하기 더보기 문제 다솜이는 은진이의 옆집에 새로 이사왔다. 다솜이는 자기 방 번호를 예쁜 플라스틱 숫자로 문에 붙이려고 한다. 다솜이의 옆집에서는 플라스틱 숫자를 한 세트로 판다. 한 세트에는 0번부터 9번까지 숫자가 하나씩 들어있다. 다솜이의 방 번호가 주어졌을 때, 필요한 세트의 개수의 최솟값을 출력하시오. $($6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다.$)$ 입력 첫째 줄에 다솜이의 방 번호 N이 주어진다. N은 1,000,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 필요한 세트의 개수를 출력한다. 입력 받은 문자를 리스트로 바꾸면서 digit별로 구분해서 각 문자$($숫자$)$의 개수를 list.c..
[백준] 10845번 큐 [Python] 큐$($Queue$)$는 데이터를 저장하는 자료구조로, 먼저 들어온 데이터가 먼저 나가는 선입선출$($FIFO, First-In-First-Out$)$ 원칙을 따릅니다. 파이썬의 collections 모듈에서는 deque 클래스를 사용하여 큐를 구현할 수 있습니다. 더보기 from collections import deque # 큐 생성 queue = deque() # 데이터 enqueue queue.append(1) queue.append(2) queue.append(3) # 큐에서 데이터 dequeue data = queue.popleft() print(data) # 출력: 1 # 큐가 비어있는지 확인 if not queue: print("큐가 비어있습니다.") 위의 예시에서는 파이썬 deque를 사..
[백준] 10866번 덱 [Python] 덱$($deque, double-ended queue$)$은 파이썬의 collections 모듈에 포함된 자료구조로, 양쪽 끝에서 원소를 추가하거나 제거할 수 있는 큐$($Queue$)$의 확장된 형태입니다. 덱은 리스트$($list$)$와 유사하지만, 리스트보다 효율적인 양방향 연산을 지원합니다. 이러한 특징 때문에 덱는 다양한 상황에서 유용하게 사용될 수 있습니다. 더보기 from collections import deque # 데크 생성 deque_list = deque() # 데크의 오른쪽에 원소 추가 deque_list.append(1) deque_list.append(2) deque_list.append(3) # 데크의 왼쪽에 원소 추가 deque_list.appendleft(0) # 데크 출..
[백준] 10828번 스택 [Python] 스택$($Stack$)$은 데이터를 저장하고 관리하는 자료구조 중 하나로, 후입선출$($Last In, First Out, LIFO$)$ 방식으로 동작합니다. 파이썬에서 스택은 리스트$($list$)$를 활용하여 구현할 수 있으며, 다양한 상황에서 유용하게 사용됩니다. 함수 호출 스택 재귀 함수를 사용할 때 스택은 함수 호출의 형태로 사용됩니다. 재귀 함수는 자기 자신을 호출하는 방식으로 동작하기 때문에 스택을 이용하여 함수 호출 순서를 관리합니다. 재귀적으로 호출되는 함수는 스택에 쌓이고, 함수가 반환되면 스택에서 제거됩니다. 브라우저 뒤로/앞으로 기능 웹 브라우저에서 뒤로 가기, 앞으로 가기 기능은 스택을 사용하여 구현될 수 있습니다. 방문한 페이지의 URL을 스택에 추가하고, 뒤로 가기 버튼을 클릭..
[백준] 2839번 설탕 배달 [Python] 상근이의 설탕 배달 더보기 문제 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다. 상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다. 상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. $($3 ≤ N ≤ 5000$)$ 출력 상근이가 배달하는 봉지의..
[백준] 1018번 체스판 다시 칠하기 [Python] 흑백이 번갈아가며 나타나는 체스판을 만들기 더보기 문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의..
[백준] 17219번 비밀번호 찾기 [Python] - 딕셔너리 주어진 주소와 비밀번호 쌍에 대해서, 주소를 입력 받으면 비밀 번호를 출력하는 문제 더보기 문제 2019 HEPC - MAVEN League의 "비밀번호 만들기"와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못 한다는 것이었다! 그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민이는 메모장에서 찾기 기능을 활용하지 못하고 직접 눈으로 사이트의 주소와 비밀번호를 찾았다. 메모장에 저장된 사이트의 수가 늘어나면서 경민이는 비밀번호를 찾는 일에 시간을 너무 많이 쓰게 되었다. 이를 딱하게 여긴 문석이는 경민이를 위해 메모장에서 비밀번호를 찾는 프로그램을 만들기로 결심하였다! 문석이를 도와 경민이의 메모장에서..
[백준] 11050번 이항 계수 1 [Python] - 조합 조합 $_{n}C_{r}$을 구하는 문제 더보기 문제 자연수 N과 정수 K가 주어졌을 때 이항 계수 \left(\begin{array}{c}N\\ K\end{array}\right)를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. $($1 ≤ N ≤ 10, 0 ≤ K ≤ N$)$ 출력 \left(\begin{array}{c}N\\ K\end{array}\right)를 출력한다. 조합 \begin{align}\left(\begin{array}{c}N\\ K\end{array}\right) = \frac{N!}{K!(N - K)!} \end{align} 팩토리얼 \begin{align}N! =1*2*3* \cdots * N\end{align} 다 같은 내용이지만 3가지 방식으로 코드를 ..
[백준] 15652번 N과 M[4] [Python] - 중복조합 $_{n}H_{r}$ = $_{n+r-1}C_{r}$중복조합을 구하는 문제 더보기 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. $($1 ≤ M ≤ N ≤ 8$)$ 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 중복조합$(..
[백준] 15651번 N과 M[3] [Python] - 중복순열 $_{n}\Pi_{r}$ 중복순열을 구하는 문제 더보기 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. $($1 ≤ M ≤ N ≤ 7$)$ 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 중복순열$($permutation with repeation$)$ : 서로 다른 n개의 원소에서 r개를 중복하여 순서에 상관있게 선택하는 혹은 나열하는 것 입력 받기 import ..
[백준] 15650번 N과 M[2] [Python] - 조합 $_{n}C_{r}$ 조합을 구하는 문제 더보기 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. $($1 ≤ M ≤ N ≤ 8$)$ 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 조합이란 n개의 원소를 갖는 집합에서 r개의 원소를 선택하는 것 itertools.combinations : 조합을 구하는 함수 $_{n}C_{r}$ : itertools.co..

티스토리툴바