ehdbs0903 ehdbs0903

동적 계획법(Dynamic Programming) 알고리즘이란?복잡한 문제를 더 작고 관리 가능한 부분 문제로 나누어 해결하는 알고리즘 설계 기법이다.알고리즘의 기본 아이디어는 각 부분 문제의 해답을 저장하고, 이를 재사용함으로써 중복 계산을 피해 계산 효율을 극대화하는 것이다.  시간복잡도동적 계획법 알고리즘의 시간복잡도는 문제에 따라 다양하지만, 일반적으로 부분 문제의 수와 각 부분 문제를 해결하는 데 걸리는 시간의 곱으로 표현된다. 피보나치 수열 계산:각 수를 계산하기 위해 이전 두 수만 알면 되므로, 한 번 계산된 값은 다시 계산할 필요가 없다.시간복잡도는 O(n)이다.최장 공통 부분 수열(Longest Common Subsequence, LCS):시간복잡도는 O(m * n)이다.m, n은 두 시..

문제https://www.acmicpc.net/problem/11866    코드1. Pythonfrom collections import dequedef josephus(N, K): q = deque(range(1, N + 1)) result = [] while q: q.rotate(-(K-1)) # K-1만큼 왼쪽으로 회전 (맨 앞의 요소가 K번째 요소가 되도록) result.append(q.popleft()) # 회전 후 맨 앞의 요소를 제거하고 결과 리스트에 추가 return resultN, K = map(int, input().split())ans = josephus(N, K)print("") 2. C++#include #include #in..

문제https://www.acmicpc.net/problem/11651    코드1. Pythonimport sysinput = sys.stdin.readlinen = int(input())points = [list(map(int, input().split())) for _ in range(n)]points.sort(key=lambda x: (x[1], x[0]))for p in points: print(*p) 2. C++#include #include #include using namespace std;bool compare(const pair& a, const pair& b) { if (a.second == b.second) { return a.first > n; vector> points; ..

문제https://www.acmicpc.net/problem/11650    코드1. Pythonn = int(input())points = [list(map(int, input().split())) for _ in range(n)]points.sort()for p in points: print(*p) 2. C++#include #include #include using namespace std;int main() { int n; cin >> n; vector> arr; int x, y; while (n--) { cin >> x >> y; arr.emplace_back(x, y); } sort(arr.begin(), arr.end()); for (const auto& a: arr) cout

문제https://www.acmicpc.net/problem/10845    코드1. Pythonimport sysinput = sys.stdin.readlinen = int(input())queue = []for i in range(n): cmd = input().split() if cmd[0] == "push": queue.insert(0, cmd[1]) elif cmd[0] == "pop": if len(queue): print(queue.pop()) else: print(-1) elif cmd[0] == "size": print(len(queue)) elif cmd[0] == "empty": i..

문제https://www.acmicpc.net/problem/10828    코드1. Pythonimport sysinput = sys.stdin.readlinen = int(input())arr = []for _ in range(n): cmd = input().rstrip() if cmd[:4] == "push": cmd, i = cmd.split() arr.append(i) elif cmd == "pop": if len(arr): print(arr.pop()) else: print(-1) elif cmd == "size": print(len(arr)) elif cmd == ..

문제https://www.acmicpc.net/problem/10816    코드1. Pythonfrom collections import defaultdictn = int(input())cards = list(map(int, input().split()))m = int(input())query = [*map(int, input().split())]card_count = defaultdict(int)for card in cards: card_count[card] += 1for q in query: print(card_count[q], end=' ') 2. C++#include #include using namespace std;int main() { ios::sync_with_stdio(fal..

문제https://www.acmicpc.net/problem/10814  코드1. Pythonn = int(input())people = []for _ in range(n): people.append(tuple(input().split()))people.sort(key = lambda x: int(x[0]))for i in people: print(i[0], i[1]) 2. C++#include #include #include using namespace std;bool compare(const pair& a, const pair& b) { return a.first > n; vector> arr; int age; string name; while (n--) { cin >> age >> na..