본문 바로가기

Algorithm

[백준] 12865 평범한 배낭(Python 파이썬) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 설명 이 문제는 아주 평범한 배낭에 관한 문제이다. 흔히, 냅색(Knapsack) 알고리즘이라고 불리는 문제이다. 배낭의 용량이 정해져 있을 때, 최대한의 가치를 가지도록 배낭을 싸야 한다. 주어진 물건들의 용량과 가치를 고려하여 주워담을지 말지 정하는 문제이다. 풀이 과정 먼저, 내 배낭이 버틸 수 있는 용량이 7이라고 하자.. 더보기
[백준] 2252 합분해 (Python 파이썬) www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 설명 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 풀이 과정 이 문제는 코드는 간단해보일지 몰라도, 아이디어를 떠올리는 과정이 굉장히 까다로웠다. 나는 DP와 순열과조합의 개념을 조합하여 아이디어를 떠올렸다. 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 d[N][K]에 저장한다고 하자. N = 2, K = 1 일 경우 0부터 2까지.. 더보기
[백준] 2156 포도주 시식 (Python 파이썬) www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 문제 설명 포도주가 ( a, b, c, d, e, f ) 식으로 일렬로 나열되어 있다. a, b, c, d...는 포도주의 용량을 뜻한다. 연속으로 3잔 이상을 마실 수 없을 때, 최대로 마실 수 있는 포도주의 용량을 구하면 된다. 풀이 과정 6잔의 포도주 ( 6, 10, 13, 9, 8, 1 ) 가 있다고 생각해보자. 마지막 포도주를 마실지 말지를 결정하는 상황이라고 할 때, 내가 9와 8을 이미 마셨다면 1은.. 더보기
[백준] 1003번 피보나치 함수 (Python 파이썬) www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 설명 자세한 문제 설명은 위의 링크에 나와있습니다! 피보나치 함수란, N번째 수의 값이 N-1 + N-2 의 값이 되는 함수입니다. fibonacci(N) 을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 문제입니다. 풀이 과정 이 문제를 문제에서 주어진 C++코드를 그대로 이용해 0과 1의 횟수를 구하려고 하면 시간초과가 난다. 왜냐하면 f(10)을 호출했다고 가정할 때, f(10) = f(9) + f(8)이 되기 때문에 f(9)와 f(8)을 한번씩 호출하게 되는데, f(9) = f(8)+f.. 더보기
[백준] 1463번 1로 만들기 (Python 파이썬) www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오. 풀이 과정 이 문제는, 전의 결과를 다음 결과에 이용하게 되는. 점화식을 활용한 DP 문제이다. X = 10인 경우, 10 -> 9 -> 3 -> 1 과정을 거쳐 1이 되게 되는데 9의 경우에는 또, 9 -> 3 -> 1의.. 더보기
[백준] 5430번 AC (Python 파이썬) www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제 설명 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 숫자를 버리는 함수이다. 배열의 .. 더보기
[백준] 1021번 회전하는 큐 (Python 파이썬) 문제 설명 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, ..., ak, a1이 된다. 오른쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 ak, a1, ..., ak-1이 된다. 큐에 처음에 포함되어 있던 수 N이 주어진다. 그리고 지민이가 뽑아내려고 하는 원소의 위치가 주어진다. (이 위치는 가장 처음 큐에서의 위치이다.) 이때.. 더보기
[백준] 1966번 프린터 큐 (Python 파이썬) www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 설명 프린터는 FIFO(First In First Out) 즉 선입 선출의 구조로 문서를 출력하게 된다. 하지만 문제의 프린터에는 조건이 있다. 문서마다 중요도가 기록되어 있는데, 자신보다 중요도가 높은 문서가 하나라도 자신의 뒤에 있으면 자신은 맨 뒤로 밀려나게 된다. 예를 들어, A B C D 라는 4개의 문서의 중요도가 2 1 4 3이라면 2가 밀려나고 1이 밀려나고 4가 제일 먼저 출력되어 3 2 1 .. 더보기

티스토리툴바