Algorithm/BaekJoon

# 답 bisect_left 라이브러리 없이 풀기 import sys input = sys.stdin.readline N = int(input()) A = list(map(int, input().split())) LIS = [A[0]] def find_index(x): lo = 0 hi = len(LIS) - 1 while lo

# 답 N = int(input()) k = int(input()) lo = 1 hi = N * N mi = (lo + hi) // 2 while lo

# 답 import sys input = sys.stdin.readline N, C = map(int, input().split()) home = [int(input()) for _ in range(N)] home.sort() lo = 1 hi = home[-1] - home[0] mi = (lo + hi) // 2 while lo = pre + mi: pre = i cnt += 1 if cnt >= C: lo = mi + 1 else: hi = mi - 1 mi = (lo + hi) // 2 print(mi) # 풀이 과정 이분 탐색을 이용해 풉니다. 1) 이 문제에서 요구하는 답은 '공유기 사이의 최단거리의 최댓값'입니다. 즉 '공유기 사이의 거리'를 구해야합니다. '공유기 사이의 거리'는 최소 1 ..

# 답 import sys board = [list(map(int, sys.stdin.readline().split())) for _ in range(9)] zero = [] for y in range(9): for x in range(9): if not board[y][x]: zero.append((y, x)) def is_sudoku(ty, tx, n): y = (ty // 3) * 3 x = (tx // 3) * 3 for i in range(9): # 가로줄 확인 if board[ty][i] == n: return False # 세로줄 확인 if board[i][tx] == n: return False # 3 * 3 확인 if board[y + i // 3][x + i % 3] == n: retu..

# 답 K, N = map(int, input().split()) lan = [int(input()) for _ in range(K)] lo = 1 hi = max(lan) mi = (lo + hi) // 2 while lo = N: if lo == mi: lo += 1 else: lo = mi elif tot < N: if hi == mi: hi -= 1 else: hi = mi mi = (lo + hi) // 2 print(mi) ~~ # 풀이 파라메트릭 서치로 푸는 대표적인 문제입니다. 파라메트릭 서치는 이분 탐색과 거의 유사한 알고리즘인데요. 차이점은, 이분 탐색은 탐색범위를 좁혀나가다가 정답을 발견하면 바로 함수를 빠져나오는 반면, 파라메트릭 서치는 더 이상 살펴볼 것이 없을 때까지 함수를 종료..

# 문제상황 처음에는 두 선분에 대한 직선의 방정식을 2개 세워서 직접 교점을 찾으려고 했으나.. 이렇게 풀면 코드가 복잡해집니다. 이 문제는 아래 2166번 문제를 풀 때 쓰였던 '다각형의 넓이 공식'을 이용해서 풀 수 있습니다. 세 좌표를 이용해 구한 다각형의 넓이가 양수이면 반시계, 음수이면 시계 방향이라고 했었죠? 시계 방향이냐, 반시계 방향이냐를 이용하면 네 점이 교차하는 위치에 있는지 아닌지 알 수 있습니다. (파이썬) 백준 2166번 "다각형의 면적" # 문제상황 다각형의 좌표들을 모두 알고 있을 때, 다각형 넓이를 쉽게 구할 수 있는 공식이 있습니다. 고등학교 때 교육과정에는 없는 내용이지만 수업시간에 '이런 공식도 있습니다~' 하고 흘 beluga9.tistory.com # 답 x0, y..

# 문제상황 다각형의 좌표들을 모두 알고 있을 때, 다각형 넓이를 쉽게 구할 수 있는 공식이 있습니다. 고등학교 때 교육과정에는 없는 내용이지만 수업시간에 '이런 공식도 있습니다~' 하고 흘러가듯이 들었던 적이 있었는데 이렇게 알고리즘 문제를 풀 때 만나게 됐네요. 다음 점 A(-4, 9), B(-3, -2), C(-1, 4), D(6, 1), E(3, 10)로 구성된 다각형의 넓이를 구해봅시다. 넓이를 구하는 과정을 그림 하나에 모두 담아보았습니다. 단계별로 설명하자면 다음과 같습니다. 1단계) 각 좌표들을 반시계 방향으로 나열하고, 맨 끝에는 제일 첫 좌표를 한 번 더 써줍니다. - 제일 첫 좌표를 한 번 더 써주는 거 잊지 마세요! - 만일 좌표들을 시계 방향으로 나열하고 문제를 풀면 넓이가 음수로..

# 문제상황 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..