반응형 Coding Test (코딩 테스트)77 [실버5]백준 1181번(단어 정렬) - 코테공부 40일차(2025.03.06) 문제유형정렬풀이 방법 도출 과정1. 알파벳 소문자로 이루어진 N개의 단어가 들어오면 "길이가 짧은 것부터", "길이가 같으면 사전 순으로" 우선순위 대로 정렬하는 것이 문제이다.2. 입력은 첫째줄에 얼마정도 나타나는 지(N) 나머지는 정렬할 대상이 온다. N은 20000만 이하, 문자열의 길이는 50을 넘지 않음3. sort 알고리즘을 쓰며, lambda함수를 사용하여 정렬을 해보도록 하겠다.시간 복잡도시간 복잡도는 O(N)이다. 시간복잡도가 최악이 될 경우 2만이기에 시간복잡도 부분에서 안정하다. 코드 및 간단설명정렬을 사용하여 고쳐보았다. N = int(input())result = set() # 중복 제거를 위해 set 사용for i in range(N): A = input() resu.. 2025. 3. 6. [브론즈1]백준 28702번(FizzBuzz) - 코테공부 39일차(2025.03.05) 문제유형문자열풀이 방법 도출 과정1. 주어진 문제는 특정 규칙을 기반으로 문자열을 예측하는 문제이다.2. 문자열이 연속적으로 주어지며, 그 깅리은 최대 8 이하이다. 특정 패턴이 전용되며 이를 기반으로 다음에 올 문자열을 예측해야한다.2. 이 문제는 게임 "369"와 유사하지만 다른 규칙을 따른다.3. 적용되는 규칮은 이와 같다. 숫자가 3의 배수이면서 5의 배수이면 "FizzBuzz"를 출력한다. 3의 배수이기만 하면 "Fizz" 5의 배수이기만 하면 "Buzz"를 출력한다. 둘다 해당하지 않는다면 숫자 그대로 출력한다. 4. 이를 해결하기 위해 문자열이 연속되다가 숫자가 등장하는 경우 해당 숫자를 활용하여 이후 문자열을 결정하는 방식을 적용한다.5. 특정 숫자가 주어지면, 이를 기반으로 문자열을 생성.. 2025. 3. 5. [브론즈1]백준 11050번(이항 계수 1) - 코테공부 38일차(2025.03.04) 문제유형조합풀이 방법 도출 과정1. 간단한 이항계수를 구하면 되는 문제.2. 이를 위해서 itertools를 쓰면 된다. 이를 사용하여 이항계수를 구하면 간단하게 할 수 있다. 시간 복잡도시간 복잡도는 range(1, N +1) C K다. 최악의 경우 N이 10일 경우를 생각하면 1~10C1이라고 가정해도 1억은 넘지 않는다.코드 및 간단설명조합 알고리즘을 사용하였다. from itertools import combinationsresult = []N, K = map(int, input().split())# range(N)로 1부터 N까지의 숫자를 iterable로 만든 후, 그로부터 K개의 조합을 구함result.extend(combinations(range(1, N + 1), K))print(len.. 2025. 3. 4. [브론즈1]백준 2869번(달팽이는 올라가고 싶다) - 코테공부 37일차(2025.02.27) 문제유형수학풀이 방법 도출 과정1. 땅 위의 달팽이가 V미터인 나무 막대를 올라간다. 달팽이는 낮에 A미터 올라가는데 밤에는 B미터 떨어진다. 달팽이가 나무 막대를 모두 올라가려면, 몇일 걸리는지 구하는 문제2. 입력: A, B, V 3. 예제 분석1일차: (A - B)2일차: (A - B) + (A - B) 3일차: (A - B) + (A - B) + (A - B) 일반화 하면 (A - B) x (n - 1) + A 4. 이식을 변형하면 (A - B) x (n - 1) + A >= V이것을 n에 관하여 정리하면 다음과 같아진다. n >= V-A/A-B + 1 그런데 이가 마지막 날에는 미끌어지지 않기 때문에 +1를 삭제한다.시간 복잡도시간 복잡도는 O(1)이다. 코드 및 간단설명수학을 사용하였다. .. 2025. 2. 27. [골드5]백준 12865번(평범한 배낭) - 코테공부 36일차(2025.02.26) 문제유형다이나믹 프로그래밍(동적 계획법)풀이 방법 도출 과정1. 물건 N개의 물건이 있다. 각 물건은 무개W와 가치 V를 가지는데 최대 K만큼의 무개만큼 넣는다고 가정했을 때, 가치V가 가장 높을 때의 값을 구하는 문제이다.2. 첫 줄에 입력은 N, K 나머지는 W, V이다. 3. 가장 먼저 일단 가장 W가 채워질 가능성을 찾고 그 뒤로 그 가능성 중에 가장 나은 것을 고르는 방법이 있다. 이 방법은 최악의 경우 100C50이 나오는데 이는 1억을 넘는 것이기에 사용하지 않겠다. 4. 두번째로 그리디 알고리즘을 사용하는 방법이 있는데 이를 위해 가치 대비 무개 비율이 높은 순서대로 정렬한 다음 가능한 한 많은 물건을 선택한다고 해서 정확한 최적해를 보장하기에는 적절하지 않다. 5. 그러므로 동적 계획법을.. 2025. 2. 26. [브론즈1]백준 2775번(부녀회장이 될테야) - 코테공부 36일차(2025.02.26) 문제유형다이나믹 프로그래밍(동적 계획법)풀이 방법 도출 과정1. 아파트의 거주 인원을 계산하는 문제이다. 특정 층(k)와 호(n)에 몇 명이 살고 있는지 구해야한다.2. 거주 규칙은 다음과 같다. 3. 0층의 i호에는 i명이 거주한다.4. k층의 n호에 살려면, 바로 아래층(k-1)의 1호부터 n호까지 거주하는 사람들의 합만큼 데려와야 한다. 5. 예를 등러 1틍과 2층의 3호까지를 살펴보자1층1호: 0호 1호(1명) -> 1명2호: 0층 1호(1명) + 0층 2호(2명) -> 3명3호: 0층 1호(1명) + 0층 2호(2명) + 0층 3호(3명) -> 6명따라서 1층 3호 (n호)거주 인원은 총 6명이다. 2층1호: 1호 1호(1명) -> 1명2호: 1층 1호(1명) + 1층 2호(3명) -> 4명3.. 2025. 2. 26. 이전 1 2 3 4 ··· 13 다음 반응형
