문제 백준 1로 만들기 풀이 과정 그리디 알고리즘과 구분하기. 그리디 알고리즘은 각 단계에서 최적의 해를 보장해야하지만, 이 문제는 무엇으로 나눌지에 따라서 최적의 해가 달라지기 때문에 DP로 풀어야한다. 또한 입력 갯수와 시간 제한이 빡빡하기 때문에 이를 보고 유추했을 때, DP를 떠올릴 수 있다. 각 단계별로 네가지의 연산이 가능하기때문에 이 중에서 최솟값을 구해주면 된다. 따라서 이 문제의 점화식은 다음과 같다. min(ai-1, ai/2, ai/3 ai/5). 나머지를 구하는 연산은 각 조건에 해당할 때만 수행할 수 있어야 한다. (a의 i-1번째, a의 i를 2로 나눔, a의 i를 3으로 나눔, a의 i를 5로 나눔의 의미) 이를 코드로 구현하면 다음과 같이 구현할 수 있다. +1을 해주는 것은..
백준 숫자카드2 풀이 일단 처음에 문제를 보고 입력이 500,000까지의 범위에 시간 제한이 1초인 것을 보고 문제를 최소한 O(n^2) 이하의 알고리즘으로 구현해야겠다고 생각했다. 입력을 보고 이런 생각을 하는 것을 연습중인데 꽤나 도움이 되는 것 같다. 시간 내에 몇개의 원소가 있는지 확인하려면 Hash를 사용하여 숫자를 Counting하여 비교하면 되겠다고 생각했다. 이를 구현하기 위해서 collections.Counter 라이브러리를 사용했다. Counter 라이브러리의 결과값을 타겟 리스트(m_list)와 비교하여 타겟 리스트의 요소가 Counter 결과값에 존재하면 counting 한 value 값을 프린트 해주면 된다. from collections import Counter import s..
11047 동전0 풀이 동전이 이미 오름차순으로 정렬되어 있기 때문에 이를 거꾸로 정렬해준다. 이는 동전이 가장 큰 것부터 소거해야 가장 최소가 되는 수를 찾을 수 있기 때문이다. 그 이후에는 몫과 나머지를 이용하여 연산을 수행해주면 된다. import sys sys.stdin = open("11047_동전0_input.txt", "r") n, k = list(map(int, sys.stdin.readline().split())) coins = [int(sys.stdin.readline().rstrip()) for _ in range(n)] cnt = 0 coins.reverse() for v in range(n): count += k//coins[v] k = k % coins[v] print(count)
- Total
- Today
- Yesterday
- 빅데이터를지탱하는기술
- DFS
- mahout
- Flutter
- sqoop
- kubernetes
- Hadoop
- 이코테
- 파이썬
- heapq
- cka
- kafka
- Espher
- oozie
- BOJ
- 빅데이터
- CS
- GROK
- OS
- DP
- HDFS
- Python
- 백준
- 프로그래머스
- 네트워크
- elasticsaerch
- CSAPP
- Elasticsearch
- Algorithm
- logstash
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |