반응형 분류 전체보기116 [브론즈2]백준 5585번(거스름돈) - 코테공부 27일차(2025.02.18) 문제유형그리디 알고리즘풀이 방법 도출 과정1. 가장 최적의 해 = 가장 빠른 순서대로 이기에 적합한 문제이다.2. 이러한 것은 그리디 알고리즘을 사용하면 적합하다. 3. 우선 순위는 가장 많은 동전이여야한다는 점을 기억하며 코드를 작성해보도록 하겠다. 시간 복잡도시간 복잡도는 O(1)이다. 그리디 알고리즘을 사용했기 때문이다. 코드 및 간단설명그리디 알고리즘을 사용하여 간단하게 풀었다. N = int(input())N = 1000 - Ncount = 0for coin in [500, 100, 50, 10, 5, 1]: count += N // coin N %= coinprint(count)다른 풀이1) math함수 사용divmod를 사용하여 몫과 나머지를 같이 계산하는 방법으로 더 효율적으로 .. 2025. 2. 18. [실버2]백준 18111번(마인크래프트) - 코테공부 27일차(2025.02.18) 문제유형빈도수 배열 활용풀이 방법 도출 과정1. 마크에서 땅 고르기 작업을 해야한다. 2. 좌표 (i, j)에서 블록을 제거하거나 추가해야 한다.- 블록을 제거하는 데는 2초가 걸리며- 블록을 추가하는 데는 1초가 걸린다. 3. 밤에는 무서운 몬스터가 나오기 때문에, 가능한 한 빨리 작업을 끝내야 한다.4. 땅 고르기 작업에 걸리는 최소 시간과 그 경우의 땅 높이를 출력해야 한다. 5. 이 문제는 빈도수 배열을 이용한 브루트 포스를 사용해서 풀어야 한다.6. 가장 먼저 빈도수 배열을 생성한다.7. 모든 가능한 목표 높이에 대한 시뮬레이션을 한다.8. 인벤토리 조건 확인 및 최적 해를 선택한다. 시간 복잡도시간 복잡도는 모두 O(n x m)이다. 하지만 n과 m을 500에서 257로 줄여 시간복잡도를 절반.. 2025. 2. 18. [브론즈2]백준 30802번(웰컴 키트) - 코테공부 27일차(2025.02.18) 문제유형수학풀이 방법 도출 과정1.수학적으로 생각해보자 1의 주변에는 6개가 있다. 이것은 2~7까지의 수인데 1에서 건너 뛰려면 1칸이 소요되는 얘이다.2. 다음 1~7주변의 것을 보자 8~19까지 있다. 이것은 12개이다. 그 다음 주변을 보자. 20 ~ 37까지 있다. 이것은 18개이다.3. 규칙이 나왔다. 칸을 나갈 수록 카운트가 6 12 18 이 된다. 4. 이것을 통해 값을 구하도록 하겠다. 시간 복잡도시간 복잡도는 모두 O(n)이다. 코드 및 간단설명사칙연산을 활용한 문제이다.n = int(input())layer = 1current_max = 1while n > current_max: current_max += 6 * layer layer += 1print(layer)다른 풀이1.. 2025. 2. 18. 준랩 1071번(배열 원소 개수 구하기) - 코테공부 27일차(2025.02.18) 문제유형브루드 포스풀이 방법 도출 과정1. 탐색을 하는데 완전탐색을 하는 방법으로 문제를 풀어보도록 하겠다. 2. 값 중 제시한 값이 들어있는지 확인하는 것이 목표.3. 이대로 코드를 작성해보도록 하겠다. 시간 복잡도시간 복잡도는 브루드 포스 방법을 사용했기에 O(n)이다. 최악의 경우 n은 1000이기에 시간제한에 충족하여 시간복잡도는 괜찮다.코드 및 간단설명사칙연산을 활용한 문제이다.n, k = map(int, input().split())lst = list(map(int, input().split()))ans = 0for i in range(n): if lst[i] == k: ans += 1print(ans)다른 풀이1) count함수 사용더욱 간단한 방법은 count함수를 사용.. 2025. 2. 18. [실버1]백준 1342번(행운의 문자열) - 코테공부 26일차(2025.02.17) 문제유형백트래킹, 제귀함수풀이 방법 도출 과정1. 예로 들어 aaabbbaaa는 같은 문자열이 오는 경우가 있어 행운의 문자열이 아니다.2. 그런데 이 문자열들을 순열로 하여 섞어 행운의 문자열을 찾는 것이 문제이다. 3. 문자열의 모든 가능한 순열을 생성하고 그 문자가 행운의 문자열인지 알아내는 코드를 작성해보도록 하겠다.시간 복잡도시간 복잡도는 모든 순열의 수 N! X 각 순열을 생성하는 데 걸리는 시간 N을 곱한 정도가 된다. 최악의 경우 10! X 10정도는 3600만이므로 1초 이내에는 계산이 가능하다. 코드 및 간단설명백트래킹과 재귀함수를 활용하여 문제를 해결하였다. def func(lev): global S, chars, cnt, choose, ans # base case .. 2025. 2. 17. [실버2]백준 1182번(부분수열의 합) - 코테공부 26일차(2025.02.17) 문제유형조합 알고리즘풀이 방법 도출 과정1. 부분수열은 주어진 원소 중 일부를 선택하는 조합과 동일한 개념 이기에 조합을 사용해보도록 하겠다. 2. 조합을 사용하여 모든 수를 만들고 그 다음에 값들을 더한다음 첫째 줄에 합이 S가 되는 수를 찾는다.시간 복잡도최악의 경우 N이 20이기 떄문에 20 X 2^20= 2천만 정도 된다. O(N 2^N)코드 및 간단설명조합을 사용하여 풀었더니 시간초과가 나지 않았다. from itertools import combinationsN, S = map(int, input().split())lst = list(map(int, input().split()))ans = 0for i in range(1, N + 1): for num in combinations(lst, i.. 2025. 2. 17. 이전 1 2 3 4 5 6 7 ··· 20 다음 반응형
