ehdbs0903 ehdbs0903

문제https://www.acmicpc.net/problem/10773  코드1. Pythonimport sysinput = sys.stdin.readlinek = int(input())arr = []for _ in range(k): n = int(input()) if n: arr.append(n) else: arr.pop()print(sum(arr))  2. C++#include #include using namespace std;int main() { int k; cin >> k; stack s; int temp; for (int i = 0; i > temp; if (temp == 0) s.pop();..

문제https://www.acmicpc.net/problem/9012  코드for _ in range(int(input())): s = input() stk = [] is_valid = True for char in s: if char == '(': stk.append(char) elif char == ')': if not stk or stk[-1] != '(': is_valid = False break stk.pop() if is_valid and not stk: print('YES') else: print('..

브루트포스(Bruteforce) 알고리즘이란?가장 단순하지만, 최적의 해를 보장하는 접근법이다.알고리즘의 기본 아이디어는 모든 가능한 경우의 수를 탐색하여 문제의 해를 찾는 것이다.  시간복잡도브루트포스 알고리즘의 시간복잡도는 문제의 크기와 경우의 수에 따라 달라진다.일반적으로 매우 높은 시간복잡도를 가지며, 이는 문제가 커질수록 기하급수적으로 증가한다. 순열 생성:n개의 원소에 대한 모든 순열을 생성하는 경우시간복잡도는 O(n!)이다.부분집합 생성:n개의 원소에 대한 모든 부분집합을 생성하는 경우시간복잡도는 O(2^n)이다. 문자열 패턴 매칭:텍스트 길이가 n이고, 패턴 길이가 m인 경우, 모든 위치에서 패턴을 비교하는 방식시간복잡도는 O(n * m)이다.  브루트포스의 기본 원리가능한 모든 경우 생성..

문제https://www.acmicpc.net/problem/7568  코드import sysinput = sys.stdin.readline# 입력받을 쌍의 개수n = int(input())# 쌍의 정수를 저장할 리스트 초기화data = []# 순위를 저장할 리스트 초기화ans = []# n개의 쌍을 입력받아 data 리스트에 저장for i in range(n): a, b = map(int, input().split()) data.append((a, b))# 각 쌍에 대해 다른 모든 쌍과 비교하여 순위를 매김for i in range(n): count = 0 for j in range(n): # (a, b)가 (c, d)보다 두 값 모두 작을 경우 카운트 증가 ..

문제https://www.acmicpc.net/problem/4949  코드import sysinput = sys.stdin.readlinewhile True: s = input().rstrip() if s == '.': break stack = [] # 괄호를 저장할 스택 balanced = True # 문자열의 괄호가 균형 잡혀 있는지 여부 # 문자열의 각 문자를 순회 for char in s: if char in '([': # 여는 괄호는 스택에 추가 stack.append(char) elif char == ')': # 닫는 소괄호를 만난 경우 if not stack or stack[..

그리디(Greedy) 알고리즘이란?최적의 해를 구하는 데에 사용되는 근사적인 방법이다.알고리즘의 기본 아이디어는 문제를 해결하는 과정에서 각 단계에서 가장 최적이라고 생각되는 선택을 하는 것이다.  시간복잡도그리디 알고리즘의 시간복잡도는 문제의 특성과 구체적인 알고리즘 구현에 따라 다르다. 거스름돈 문제:동전 단위가 미리 정렬되어 있고, 각 동전을 한 번씩 선택시간복잡도는 O(n)이다.여기서 n은 동전의 종류 수활동 선택 문제:활동을 종료 시간 기준으로 정렬한 후, 한 번의 순회로 선택시간복잡도는 O(n log n) (정렬) + O(n) (활동 선택) = O(n log n)최소 신장 트리 문제 (Kruskal 알고리즘):간선을 가중치 기준으로 정렬한 후, Union-Find 자료구조를 사용하여 사이클을 ..

문제https://www.acmicpc.net/problem/2839  코드n = int(input())# 배달 가능한 봉지의 개수를 저장할 변수 초기화bg = 0while n >= 0: if n % 5 == 0: # 5kg 봉지로 나눌 수 있는 수를 bg에 더함 bg += n // 5 # 최종 봉지 개수를 출력하고 반복문을 종료 print(bg) break # n이 5로 나누어 떨어지지 않는다면 3kg 봉지 하나를 사용하고 n에서 3을 뺌 n -= 3 # 봉지 개수를 하나 증가 bg += 1# n이 음수가 되면 원하는 봉지 조합을 만들 수 없으므로 -1else: print(-1)  풀이기본적인 아이디어는 그리..

문제https://www.acmicpc.net/problem/2751  코드import sysinput = sys.stdin.readlinen = int(input())arr = [int(input()) for _ in range(n)] arr.sort()for i in arr: print(i)  풀이파이썬 내장 함수 sort()나 sorted()를 사용하면 쉽게 풀 수 있다.직접 정렬을 구현하고 싶다면 병합 정렬로 풀면 된다.  파이썬 내장 함수 참고https://ehdbs0903.tistory.com/entry/파이썬의-정렬-알고리즘은-어떤-알고리즘을-사용할까 파이썬의 정렬 알고리즘은 어떤 알고리즘을 사용할까?백준 문제를 풀다가 문득 궁금한 점이 생겼다.많은 정렬 알고리즘이 있는데, lis..