Algorithm

# 답 math 라이브러리를 사용하지 않은 풀이 a, b = map(int, input().split()) def gcd(a, b): while b > 0: a, b = b, a % b return a def lcm(a, b): return a * b // gcd(a, b) print(gcd(a, b)) print(lcm(a, b)) math 라이브러리를 사용한 풀이 import math a, b = map(int, input().split()) print(math.gcd(a, b)) print(math.lcm(a, b)) # 유클리드 호제법 2개의 자연수 a, b에 대하여, a를 b로 나눈 나머지를 r이라 하면(단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같습니다. 이 성질에 따라..

# 답 Counter 라이브러리를 사용하지 않은 풀이 import sys input = sys.stdin.readline N = int(input()) arr = [int(input()) for _ in range(N)] arr.sort() d = dict() for item in arr: if item in d: d[item] += 1 else: d[item] = 1 m = 0 tmp = list() for k, v in list(d.items()): if v > m: tmp = [k] m = v elif v == m: tmp.append(k) tmp.sort() # 산술평균 print(round(sum(arr) / N)) # 중앙값 print(arr[N // 2]) # 최빈값 if len(tmp) =..

# 답 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) ~~ # 풀이 파라메트릭 서치로 푸는 대표적인 문제입니다. 파라메트릭 서치는 이분 탐색과 거의 유사한 알고리즘인데요. 차이점은, 이분 탐색은 탐색범위를 좁혀나가다가 정답을 발견하면 바로 함수를 빠져나오는 반면, 파라메트릭 서치는 더 이상 살펴볼 것이 없을 때까지 함수를 종료..

N이 소수인지 판별하기 - 2부터 루트 N ​까지의 수로 모두 나누어 보고, 한 번이라도 나누어 떨어지면 소수가 아닙니다. - 반복문을 빨리 돌기 위해서는 2부터 루트 N 까지의 수들 중 (2를 포함한)홀수 또는 소수로만 나누는 방법을 생각할 수 있습니다. def is_prime(N): if N < 2: return False for i in range(2, int(N ** 0.5) + 1): if not(n % i): return False return True N보다 작은 소수 구하기 에라토스테네스의 체 알고리즘을 사용합니다. 1단계) N + 1 크기의 chk 배열을 만들고 True로 초기화합니다. True는 이 수가 소수가 맞다는 의미입니다. 2단계) 2부터 루트 N까지의 수들 중 소수(chk[i]..

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

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