Algorithm

# 문제상황 1 유클리드 기하학에서의 원은 우리가 일반적으로 알고 있는 원의 개념 그대로입니다. 하지만 택시 기하학에서의 원은 문제에서 주어진 거리 개념을 이용해, 어떤 모양일지 스스로 유추해야하는데요. 가로 길이의 차와 세로 길이의 차의 합이 동일한 점들을 일일이 찍어보면 위와 같이 45도 기울어진 정사각형이 나온다는 것을 알 수 있습니다. 정사각형의 넓이를 구하려면 정사각형의 한 변의 길이에 제곱을 해야되지만, 현재 우리가 알고 있는 건 정사각형의 대각선 길이(2R)입니다. 따라서 귀찮게 정사각형 변의 길이를 구하지 말고, 대각선 길이 제곱에 나누기 2를 해서 바로 넓이를 구해줍시다. # 문제상황 2 유클리드 기하학에서의 원의 넓이를 구할 때, PI 값을 가져와야 합니다. PI 값을 어떻게 계산해야할..

# 답 N, M = map(int, input().split()) lessons = list(map(int, input().split())) l = max(lessons) r = sum(lessons) m = (l + r) // 2 ans = r def is_possible(sz): cnt = 1 bluray = 0 for lesson in lessons: if bluray + lesson

# 답 for _ in range(int(input())): n = int(input()) sticker = [list(map(int, input().split())) for _ in range(2)] dp = [[0] * n for _ in range(2)] for i in range(2): dp[i][0] = sticker[i][0] if n > 1: dp[i][1] = sticker[i ^ 1][0] + sticker[i][1] for j in range(2, n): for i in range(2): dp[i][j] = max(dp[i ^ 1][j - 2], dp[i ^ 1][j - 1]) + sticker[i][j] print(max(dp[0][n - 1], dp[1][n - 1])) # 분석 1..

# 답 INF = 987654321 # 무한 N = int(input()) dp = [INF] * (N + 1) dp[1] = 0 for i in range(2, N + 1): if not i % 6: dp[i] = min(dp[i // 3], dp[i // 2]) + 1 elif not i % 3: dp[i] = min(dp[i // 3], dp[i - 1]) + 1 elif not i % 2: dp[i] = min(dp[i // 2], dp[i - 1]) + 1 else: dp[i] = dp[i - 1] + 1 print(dp[N]) # 분석 1 dp로 푸는 문제입니다. dp는 Top-down(재귀) 또는 Bottom-up(반복문)으로 풀 수 있는데, 저는 Bottom-up으로 풀었습니다. dp라는 ..

1. 노드간 연결 정보만 주어지는 유형 → 그래프 정보를 인접행렬 또는 인접리스트에 담아주세요. (아래 코드는 인접행렬) - 노드 개수 대비 간선 수가 많으면 인접행렬, 노드 개수 대비 간선 수가 적으면 인접리스트 adj = [[False for _ in range(v)] for _ in range(v)] for _ in range(e): n1, n2 = map(int, input().split()) adj[n1][n2] = adj[n2][n1] = True 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정..

동적 계획법 Dynamic Programming - 줄여서 DP라고도 부릅니다. - 문제를 쪼개고, 부분 문제들의 답을 구하는 과정을 반복하며 푸는 방식입니다. - 동적 계획법을 구현하는 방법에는 재귀와 타뷸레이션(반복문)이 있습니다. 피보나치 수열이 동적 계획법 대표 문제입니다. F(0) = 0 F(1) = 1 F(n) = F(n-1) + F(n-2) F(5)를 구하고 싶다면 F(4)와 F(3)이 필요합니다. F(5)라는 문제를 F(4)와 F(3)이라는 부분 문제로 쪼개어 풀어야하므로 동적계획법이 쓰인 것입니다. 메모이제이션 Memoization - 한 번 구한 부분 문제의 답을 따로 저장해두고 필요할 때 꺼내쓰는 기법입니다. - 캐싱(caching)이라고도 합니다. - 메모이제이션은 DP와는 별개의 ..

# 답 N, M = map(int, input().split()) tree = list(map(int, input().split())) lo = 0 hi = max(tree) mid = (lo + hi) // 2 def get_total_tree(h): ret = 0 for t in tree: if t > h: ret += t - h return ret ans = 0 while lo = M: ans = mid lo = mid + 1 else: hi = mid - 1 mid = (lo + hi) // 2 print(ans) # 분석 절단기 높이의 '최댓값'을 구하는 최적화 문제인데 결정 문제로 바꿔서 풀 수 있으므로 파라메트릭 서치로 풀면 됩니다. 절단기 높이가 h라면, 나무들을 자른 길이를 구할 수 있고..

선형탐색 Linear Search 앞에서부터 차례대로 찾는 것 # L에서 3찾기 L = [2, 5, 3, 4] for i in L: if i == 3: break 이분탐색 Binary Search 탐색 범위를 절반으로 줄여가면서 찾는 것 # L에서 3찾기 L = [2, 3, 4, 5] left = 0 right = len(L) - 1 mid = (left + right) // 2 while left 3: right = mid - 1 else: # L[mid] < 3 left = mid + 1 mid = (left + right) // 2 - 선형탐색보다 구현이 복잡하지만 시간이 짧게 걸립니다. - 배열 안의 값들이 반드시 정렬되어 있어야 합니다. 이분탐색 라이브러리 from bisect import bi..

# 답 N = int(input()) ans = 0 chk_col = [False] * N chk_d1 = [False] * 2 * N # 대각선 \, 우상단부터 0 chk_d2 = [False] * 2 * N # 대각선 /, 좌상단부터 0 def bt(row): global ans if row == N: ans += 1 return # row가 0이면 왼쪽 절반만 탐색, row가 1 이상이면 전체 탐색 for col in range(N if row else N // 2): if not chk_col[col] and not chk_d1[row - col] and not chk_d2[row + col]: chk_col[col] = True chk_d1[row - col] = True chk_d2[row +..

# 답 from collections import deque import sys input = sys.stdin.readline N, M = map(int, input().split()) board = [input() for _ in range(N)] chk = [[set() for _ in range(M)] for _ in range(N)] ans = 1 dy = (1, -1, 0, 0) dx = (0, 0, 1, -1) def is_valid_coord(y, x): return 0