반응형 백준31 코딩테스트 20일차(2025.02.09) - 백준2839번(설탕 배달) 문제유형그리디 알고리즘풀이 방법 도출 과정1. 3킬로, 5킬로만 담을 수 있는 봉지가 있다. 주어진 킬로로 최소의 봉지수 구하기2.5로 계속해서 나누면서 카운트하는 방식으로 이를 풀어보도록 하겠다. 시간 복잡도시간복잡도는 입력 후 for문이 최대 1번 사용되고 있기 떄문에 O(n)이다. 코드 및 간단설명그리다 알고리즘과 완전 탐색 알고리즘을 사용하여 def min_bags(n): # 5kg 봉지를 최대한 많이 사용 for i in range(n // 5, -1, -1): # 5kg 봉지 개수를 줄여가면서 탐색 remainder = n - (i * 5) # 5kg 봉지를 사용하고 남은 무게 if remainder % 3 == 0: # 나머지가 3으로 나누어 떨어지는.. 2025. 2. 9. 코딩테스트 19일차(2025.02.06) - 백준4949번(균형잡힌 세상) 문제유형스택풀이 방법 도출 과정1. "("는 ")"와 짝꿍 "["는 "]"과 짝궁 이를 맞추지 않고 있다면, no출력 그 반대는 yes출력을 한다. "."는 줄이 끝났다는 신호이다.2. 스택을 활용하면 괄호의 올바른 짝을 쉽게 확인할 수 있음3. 왼쪽 괄호를 만나면 스택에 추가4. 오른쪽 괄호를 만나면 스택에서 짝이 맞는 괄호가 있는지 확인 후 제거. - 짝이 맞지 않으면 no 출력- 짝이 맞지 않거나 스택이 비어있는데 닫는 괄호가 나오면 no 출력5. 모든 문자열을 처리한 후에도 스택에 괄호가 남아 있으면 no 출력- 스택이 비어 있으면 yes 출 시간 복잡도시간복잡도는 for문이 입력되는 순서대로 적용되고 있기에 대략 O(n)로 보여진다. 그리고 for 문의 스택의 연산은 O(1)이다. 그렇기 때문에.. 2025. 2. 7. 코딩테스트 18일차(2025.02.06) - 백준1260번(DFS와 BFS) 문제유형그래프 탐색 (DFS, BFS)풀이 방법 도출 과정1. 그래프탐색 기법에서 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)를 사용하는 문제이다.2. DFS는 왼쪽부터 시작해서 점차 오른쪽으로 계산하는 방식이며 BFS는 가장 가까운 것을 순서대로 계산하는 방법이다.3. DFS, BFS 구현시간 복잡도그래프 입력 처리는 간선의 개수만큼 반복하기에 O(M)정렬을 하기 위해서는 정점 개수만큼 반복하기(n*n)에 최악의 경우에는 O(V log V)DFS는 각 정점도 확인하고 노드도 확인하고 있기에 O(V + E) 이는 BFS도 마찬가지이기 때문에 O(V + E) 이를 모두 합하면 O(V logV + V + E)가 된다. 그러므로 회소 그래프에서는 O(V log V)가 될 수 있다. 더 빡빡한 그래프를.. 2025. 2. 6. 코딩테스트 18일차(2025.02.06) - 백준1929번(소수 구하기) 문제유형에라토스테네스의 체풀이 방법 도출 과정1. 에라토스테네스 체를 사용하는 문제이다.2. 1은 소수가 아니므로 제외해준다. 3. 소수 판별을 위한 반복문을 실행한다. 반복범위는 2부터 int(i ** 0.5) + 1까지이다.특정 수의 제곱근까지만 약수를 검사하면, 해당 수의 모든 약수를 판별할 수 있다.4. 약수가 존재하면 소수가 아니다.만약 i가 j로 나누어떨어진다면, i는 약수를 가지므로 소수가 아니다.그렇지 않다면 i는 소수이다. 5. 이 방식대로 코드를 작성해보았다. 시간 복잡도외부 for문은 m에서 n까지 i번 반복하기 때문에 대략 O(n)이며 내부 반복문은 2에서 int(i**0.5)+1개 반복하기 때문에 대략 O(i**0.5)인데 전체 복잡도는 i**0.5를 n번 반복하기 때문에 적분을 .. 2025. 2. 6. 코딩테스트 17일차(2025.02.05) - 백준10809번(알파벳 찾기) 내 풀이첫째 줄 단어 S 각각의 알파벳에 대해서 a가 처음 등장하는 위치, b가 처음 등장하는 위치 z가 처음 등장하는 위치를 공백으로 구분하여 출력어떤 알파벡이 단어에 포함되어 있지 않다면 -1를 출력한다. S = input()alpha = 'abcdefghijklmnopqrstuvwxyz'results = [-1] * 26for i in range(len(S)): results[alpha.index(S[i])] = S.index(S[i])print(*results)내가 하고자 한 것은 S를 순회해서 인덱스의 순서를 result에 알파벳순서대로 넣는 것이다.결과: 정답, 하지만 다시 공부할 필요있음.또 다른 풀이S = list(input())c = 'abcdefghijklmnopqrstuvwxy.. 2025. 2. 5. 코딩테스트 16일차(2025.02.02) - 백준11720번(숫자의 합) 내 풀이첫재줄에 숫자의 갯수두번째줄에 주어진 값 주어진 값들을 다같이 더하는 코드를 작성. 단, 주어진 값들은 공백이 없기에 주의count = int(input())numbers = list(input())for i in range(count): numbers[i] = int(numbers[i])print(sum(numbers))이번에 내가 한 풀이는 일단은 문자열을 받는 대신 문자열 리스트로 값들을 받고 리스트에 있는 값들을 int로 바꾸어 답을 구하였다.결과: 정답또 다른 풀이num = input()numbers = list(map(int,input()))print(sum(numbers)) [BAEKJOON]백준 11720번: 숫자의 합 파이썬문제 N개의 숫자가 공백 없이 쓰여있다. 이 숫자를.. 2025. 2. 2. 이전 1 2 3 4 ··· 6 다음 반응형
