본문 바로가기
728x90

파이썬

[백준알고리즘] 9095번: 1, 2, 3 더하기 -Python [백준알고리즘] 9095번: 1, 2, 3 더하기 -Python https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 문제 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다. 출력 각 www.acmicpc.net 동적 계획법으로 문제를 해결했다. 한 번 DP문제를 풀기 시작.. 더보기
[백준알고리즘] 2751번: 수 정렬하기 2 -Python [백준알고리즘] 2751번: 수 정렬하기 2 -Python https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 간단한 정렬문제이다. 실패로 떠있어서 이전 코드들을 보니까 이 문제가 뭐라고 그렇게 창의적으로 코딩을 했었는지 모르겠다. ㅋㅋㅋㅋ 주어진 수만큼 서로 다른 정수들을 입력받아 내림차순으로 출력하면 되는 문제이다. 다른 건 확인할 필요가 없는 것 같고 arr.sort()와 sorted(arr)의 차이만 살펴보면 될 것 같다. 가장.. 더보기
[백준알고리즘] 2740번: 행렬 곱셈 -Python [백준알고리즘] 2740번: 행렬 곱셈 -Python https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개가 차례대로 주어진다. N과 M, 그리고 K는 100보다 작거나 같고, 행렬의 원소는 절댓값이 100보다 작거나 같은 정수이다. www.acmicpc.net 분할 정복까지는 아닌 것 같지만 소개에도 "행렬의 거듭제곱을 계산하기 전에 먼저 풀어야 할 문제"라고 나와있다. 행렬의 곱셈을 할 줄만 안다면 코드를 짜는 건 쉽기 때문에 코드만 올린다. 이 문제 역시.. 더보기
[백준알고리즘] 11401번: 이항 계수 3 -Python [백준알고리즘] 11401번: 이항 계수 3 -Python https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 어렵다.. 처음에 풀다가 방법을 찾아봤다 그러다가 "페르마의 소정리"와 "확장 유클리드 호제법"으로 해결이 가능하다는 것을 확인하고 공부했던 내용을 다시 확인했다. 우선 "확장 유클리드 호제법"을 확인하고 해당 방법으로 문제를 해결했다. 이전에 공부했던 내용이라 다른 분의 블로그를 참조하니 이해가 쉬웠다. 해당 블로그의 링크는 아래이며 이해가 안되면 더 찾아보면.. 더보기
[백준알고리즘] 15650번: N과 M (2) -Python [백준알고리즘] 15650번: N과 M (2) -Python https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 저번에 풀었던 N과 M (1)의 다음 문제이다. 조건을 보면 "고른 수열은 오름차순이다."가 추가되었다. 별로 추가된 것도 없고 그냥 풀었다. itertools를 쓰면서 이 추가된 조건을 처리하려 하는 것보다 그냥 짜는 게 훨씬 쉬워 보여서 그냥 짰다. 얼른 백 트랙킹 마무리 지어야겠다. import sys def testCa.. 더보기
[백준알고리즘] 1021번: 회전하는 큐 -Python [백준알고리즘] 1021번: 회전하는 큐 -Python https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net 저번에는 덱을 c언어로 직접 구현해봤기 때문에 이번에는 그냥 Python으로 풀어봤다. Python에서 제공하는 collections 모듈의 deque을 이용하면 2, 3번 기능인 rotate기능까지 제공하기 때문에 쉽게 문제를 풀 수 있다. 왼쪽 값을 오른쪽.. 더보기
[백준알고리즘] 1966번: 프린터 큐 -Python [백준알고리즘] 1966번: 프린터 큐 -Python https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 www.acmicpc.net 이전에 푼 2164번 문제처럼 큐의 문제를 덱을 사용해서 풀 것이다. 여기서는 P.. 더보기
[백준알고리즘] 2164번: 카드2 -Python [백준알고리즘] 2164번: 카드2 -Python https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net 큐를 이용한 문제를 푸는 것이다. 파이썬으로 큐 모듈이 있던 것 같아서 찾던 와중에 쓰기.. 더보기
728x90

티스토리툴바