이진 탐색 알고리즘 파라메트릭 서치 Q www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net A 이진 탐색 문제이다. 다만, 문제를 그냥 풀기보다는 파라메트릭 서치를 적용하여 결정 문제로 바꾼 뒤에 푸는 것이 훨씬 간단해진다. 가장 인접한 두 공유기 사이의 최대 거리를 구하는 문제이므로, 최대 거리를 범위로 잡고, 공유기를 다 설치할 수 있는지 결정하는 문제로 바꿔서 풀었다. 코드 import sys n, c =..
Q www.acmicpc.net/problem/1789 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net A 원래는 이진 탐색 알고리즘으로 푸는 문제인 것 같으나, 이진 탐색을 고민하다가 그냥 식이 떠올라서 편하게 풀었다. 코드 import sys s = int(sys.stdin.readline().rstrip()) import math n = (- 1 + math.isqrt(1 + 8 * s)) // 2 #f(x) = (x(x+1))/2 = Σx라는 걸 이용했다. print(n)
JOIN(조인) 1. 개념 두 개 이상의 테이블을 연결하여 데이터를 검색하는 방법이다. 2. 유형 - 논리적 조인 : 사용자 SQL 문에 표현되는 테이블 결합 방식 - 물리적 조인 : 데이터베이스 옵티마이저에 의해 내부적으로 발생하는 테이블 결합 방식 3. 논리적 조인 (1) INNER JOIN(내부 조인) - 공통 존재 컬럼의 값이 같은 경우를 추출 - 조인 대상이 되는 컬럼을 명시적으로 선언하기 위하여 ON 조건절 사용된다. - SELECT A.컬럼1, A.컬럼2, ..., B.컬럼1, ... FROM 테이블1 A JOIN 테이블2 B ON 조인조건 WHERE 검색조건; 같은 이름의 컬럼이 여러 테이블에 있는 경우, 별칭.컬럼명 형태로 명시 WHERE 절은 생략가능 (2) OUTER JOIN(외부 조..
이진 탐색 알고리즘 Q www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net A 이진 탐색 알고리즘을 사용하였다. 코드 import sys from math import floor x, y = map(int, sys.stdin.readline().rstrip().split()) z = floor((y*100)/x) #내림 start = 0 end = 1000000000 if x == y or z == 99: #승률 100프로와 99프로는 변하지 않으므로 -..
