ehdbs0903 ehdbs0903

문제https://www.acmicpc.net/problem/1074    코드1. Pythondef recursion(n, x, y): global ans # 재귀의 종료 조건, n이 0이 될 경우 위치 (x, y)에 도달했음을 의미 if n == 0: ans += x * 2 + y print(ans) return # 첫 번째 사분면: 좌상단 (x, y가 모두 2^n보다 작은 경우) if x = 2 ** n: ans += 2 ** (2 * n) # 해당 사분면 전에 탐색해야 하는 전체 항목 수 추가 recursion(n - 1, x, y - 2 ** n) # y 좌표 조정하여 재귀 호출 # 세 번째 사분면..

분할 정복(Divide and Conquer) 알고리즘이란?하위 문제들이 중복되지 않을 경우에 사용하는 알고리즘이다.알고리즘의 기본 아이디어는 복잡한 문제를 더 작고 다루기 쉬운 하위 문제로 나누고, 각각을 독립적으로 해결한 다음, 그 해결 결과를 합쳐 전체 문제의 최적 해를 도출하는 것입니다.  시간복잡도분할 정복(Divide and Conquer) 알고리즘의 시간복잡도는 문제를 어떻게 분할하고 정복하는지에 따라 달라진다. 일반적인 계산을 위해 사용되는 방법은 재귀식을 통해 시간복잡도를 표현하는 것이다. 이는 문제의 크기를 줄여가면서 하위 문제의 수와 각 하위 문제를 해결하는 데 걸리는 시간을 고려한다. 이진 탐색(Binary Search):분할: 배열을 반으로 나눔.정복: 한 쪽 반을 선택하여 탐색을..

문제https://www.acmicpc.net/problem/1012    코드1. Pythonimport sysinput = sys.stdin.readline # 입력을 빠르게 받기 위해 sys.stdin.readline 사용sys.setrecursionlimit(10**6) # 재귀 깊이 한계 설정, 대규모 그리드 처리를 위함dx = [-1, 1, 0, 0] # x축 이동 방향 (상, 하)dy = [0, 0, -1, 1] # y축 이동 방향 (좌, 우)def dfs(x, y): # 그리드 범위를 벗어나는 경우 즉시 종료 if x = n or y = m: return False # 현재 위치에 1이 있으면, 해당 위치를 0으로 바꾸고 주변을 탐색 if graph..

문제https://www.acmicpc.net/problem/1003    코드1. Pythont = int(input())dp = [[0, 0] for _ in range(41)]dp[0] = [1, 0]dp[1] = [0, 1]for i in range(2, 41): dp[i][0] = dp[i-1][0] + dp[i-2][0] dp[i][1] = dp[i-1][1] + dp[i-2][1] for _ in range(t): n = int(input()) print(*dp[n]) 2. C++#include #include using namespace std;int main() { ios_base::sync_with_stdio(false); cin.tie(nu..

동적 계획법(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