[ 알고리즘 ]

[백준] 2110. 공유기 설치

📌문제 https://www.acmicpc.net/problem/2110 🎖️난이도 ✔️풀이 # sol1) sys.stdin.realine(), 이분탐색 => 664ms import sys n, c = map(int, input().split()) x_list = sorted([int(sys.stdin.readline()) for _ in range(n)]) start = 1 # 최소 거리 end = x_list[-1] - x_list[0] # 최대 거리 result = 0 # 인접(최소) 공유기 사이의 최대 거리 # start~end 사이에서 "인접 공유기 사이 거리(mid)" 바꿔가며 이진탐색 # 즉, 변수 : "거리" ! while(start = tmp_x + mid: tmp_x = x_list[i..

[백준] 1300. K번째 수

📌문제 https://www.acmicpc.net/problem/1300 🎖️난이도 ✔️풀이 # sol1) 이분탐색 => 1028ms n = int(input()) k = int(input()) start = 1 end = k result = 0 while start = k: result = mid end = mid - 1 else: start = mid + 1 print(result) # sol2) 이분탐색 (check함수로 T/F return) => 396ms! n = int(input()) k = int(input()) def check(mid, kk): cnt = 0 for i in range(1, n+1): tmp = mid // i cnt = cnt + tmp if tmp < n else cn..

[백준] 10816. 숫자 카드 2

📌문제 https://www.acmicpc.net/problem/10816 🎖️난이도 ✔️풀이 # sol1) dict(해시), 리스트내포, 삼항연산자 => 652ms n = int(input()) cards = list(input().split()) m = int(input()) nums = list(input().split()) result = [0] * m nCards_dict = {} for card in cards: nCards_dict[card] = nCards_dict[card] + 1 if card in nCards_dict else 1 result = [nCards_dict[nums[i]] if nums[i] in nCards_dict else 0 for i in range(m)] prin..

[백준] 9663. N-Queen

📌문제 https://www.acmicpc.net/problem/9663 🎖️난이도 ✔️풀이 # sol1) 재귀 # python3 오답 (시간 초과) & pypy3 정답 (30044ms) n = int(input()) queen = [0 for _ in range(n)] # 각 행마다의 퀸의 위치(열) cnt = 0 # 해당 행에 퀸을 놓을 수 있는 곳이 있는지(유망한지) 현재 queen 배열 상태 체크 def isPromising(row): # 체크하려는 행의 이전 행까지만 체크 for i in range(row): # 퀸을 놓을 수 없는 경우 2가지 (유망 x) # 1. 같은 열에 위치한 퀸이 있거나 or 2. 왼쪽 위 or 오른쪽 위 대각선에 퀸이 있거나 if queen[row] == queen[i..

[백준] 15651. N과 M (3)

📌문제 https://www.acmicpc.net/problem/15651 🎖️난이도 ✔️풀이 from itertools import product # 중복 순열 n, m = map(int, input().split()) for i in product(range(1, n+1), repeat = m): # product는 꼭 repeat!! print(' '.join(map(str, i)))