데굴데굴

11047번: 동전 0 (acmicpc.net) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘을 이용하여 거스름돈/동전 문제를 풀 때는 탐색애 이용되는 값들 중 큰 값이 작은 값의 배수인지를 꼭 확인해야 한다. 배수가 아니라면 작은 단위의 동전들만 조합해도 최적해가 나올 수 있기 때문이다. 이 문제는 아래처럼 큰 값이 작은 값의 배수라는 것을 명시하고 있기에 그리디 알고리즘으로 풀 수 있다. (이것이 취업을 위한 코딩테스트다 p...

1874번: 스택 수열 (acmicpc.net) 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net n과 수열이 주어지면 1부터 n까지의 수에 대해 스택 연산만으로 해당 수열을 만들 수 있는지 판단하는 문제이다. 수열이 만들어진다면 연산의 순서를 차례로 출력하고, 수열이 만들어지지 않는다면 NO를 출력한다. 수열 생성 가능 여부를 ok라는 불리언 변수에 저장한 후 (초기값 True), 어긋날 시에는 False로 바뀌도록 구성했다. ..

1158번: 요세푸스 문제 (acmicpc.net) 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 리스트로 푸니 시간초과가 발생하여 deque 라이브러리를 이용했다. [구조] n과 k 입력받기 덱에 1부터 n까지 넣기 k-1번째 원소까지는 팝하자마자 다시 덱에 넣기 k번째 원소는 팝하여 josephus 순열 리스트에 저장 출력 형식에 맞도록 코드 작성 나의 풀이 from collections import deque import sys n , k = map(int, sys.stdin.readline().split()) D = deque() josephus = [] # n까지 큐에 넣기 for i in..

11557번: Yangjojang of The Year (acmicpc.net) 11557번: Yangjojang of The Year 입학 OT때 누구보다도 남다르게 놀았던 당신은 자연스럽게 1학년 과대를 역임하게 되었다. 타교와의 조인트 엠티를 기획하려는 당신은 근처에 있는 학교 중 어느 학교가 술을 가장 많이 먹는지 www.acmicpc.net 가장 술을 많이 먹은 학교의 이름을 출력한다. [입력] 2

9093번: 단어 뒤집기 (acmicpc.net) 9093번: 단어 뒤집기 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문장이 하나 주어진다. 단어의 길이는 최대 20, 문장의 길이는 최대 1000이다. 단어와 단어 사이에는 www.acmicpc.net [입력] I am happy today [출력] I ma yppah yadot 나의 풀이 리스트 내장 함수를 사용하면 간단하게 풀 수 있는 문제이다. 백준 알고리즘 기초 강좌에 이 문제가 수록되어 있어 스택을 활용해 풀어보았다. 파이썬에는 스택이 따로 없고 그 기능을 리스트가 전부 제공하기에 리스트를 이용했다. 문자열을 공백을 기준으로 나눈 리스트로 입력받는다. ex) ['I', 'am', 'happy',..

7568번: 덩치 (acmicpc.net) 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net [구조] 입력받은 정보를 쌍으로 묶어 리스트에 저장한다. 초기 등수는 1로 설정한다. 자신보다 덩치가 큰 사람의 수를 하나씩 센 후 크다면 등수에 1씩 더한다. 그렇게 만들어진 등수를 ranks라는 리스트에 넣는다. 리스트를 출력 형식에 맞게 공백으로 구분지어 출력한다. 풀이 data = [] ranks = [] for _ in range(int(input())): a, b = map(int, input()..

2231번: 분해합 (acmicpc.net) 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 첫 풀이 n = int(input()) sums = [] for num in range(1, n + 1): sum = num s = str(num) for j in s: sum += int(j) if sum == n: sums.append(num) if len(sums) == 0: print(0) else: print(min(sums)) 처음엔 이렇게 했는데 계속 틀렸다고 나와서 질문게시판..

17478번: 재귀함수가 뭔가요? (acmicpc.net) 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 문자열 문제는 무조건 복붙해야 한다는 교훈을 얻게 해준 문제다. (마침표 하나 때문에 계속 실패했었다) 딱 한 번 출력되는 문장은 함수에 넣지 않고 따로 출력한다. 재귀함수를 정지해줄 제어장치로 cnt 변수를 받는다. cnt 변수는 재귀의 진행 횟수를 카운트한다. 처음에는 텍스트가 그냥 출력되지만, 재귀할 때마다 문장 앞에 언더바 네 개(____)가 추가된다. 따라서 언더바 네 개에 cnt를 곱해준다. ..