최근접 점의 쌍(closest pair) 문제는 2차원 평면상의 n개의 점이 입력으로 주어질 때 거리가 가장 가까운 한 쌍의 점(거리)을 찾는 문제이다. 최근접 점의 쌍을 찾는 방법으로는 모든 점에 대하여 각각의 두 점 사이의 거리를 계산하여 가장 가까운 점의 쌍을 찾는 방법 (BruteForce) - O(n^2) n개의 점을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고 부분해 중 짧은 쌍을 찾는 방법 (분할정복) 이 있다. 부분해를 취합(정복)하는 과정에서 중간 영역 사이의 점에서 더 근접한 점의 쌍이 존재할 수 있다. 중간 영역의 점들은 [왼쪽 그룹의 가장 오른쪽 점의 x 좌표에서 부분해를 뺀 값과 오른쪽 그룹의 가장 왼쪽 점의 x좌표에서 부분해를 더한 값 사이의 x 좌표 값을 가진..

분할정복 -주어진 문제를 둘 이상의 부분 문제로 나누어서 푸는 방법 -비슷한 크기로 문제를 나눔 -재귀호출 사용 분할정복 과정 Divide :부분 문제로 나눌 수 있는 경우 2개 이상의 문제로 나눈다. Conquer : 더 이상 나눌 수 없는 경우 현재 문제를 정복한다. Combine : 해결된 문제들을 병합하여 기존 문제를 해결한다. 분할 횟수 입력의 크기가 n이고 총 분할한 횟수가 k라면. -1번 분할 후 입력 크기 : n/2 -2번 분할 후 입력 크기 : n/2^2 ... -k번 분할 후 입력 크기 : n/2^k --> n/2^k 가 1 이라면 더 이상 분할 불가 분할 횟수 분할정복의 사용 1. 합병정렬(Merge Sort) 입력이 2개의 부분문제로 크기가 반씩 줄어드는 분할 정복 알고리즘 -n개의..

문제 https://programmers.co.kr/learn/courses/30/lessons/1829 코딩테스트 연습 - 카카오프렌즈 컬러링북 6 4 [[1, 1, 1, 0], [1, 2, 2, 0], [1, 0, 0, 1], [0, 0, 0, 1], [0, 0, 0, 3], [0, 0, 0, 3]] [4, 5] programmers.co.kr 영역의 수와 가장 큰 영역의 넓이를 구하는 문제이다. 문제풀이 흔히 볼 수 있는 bfs 문제와 유사하다. que에 좌표를 넣고 que가 빌 때까지 move를 이용해 주위 좌표(상,하,좌,우)를 탐색하고, 동일한 값을 지닌 좌표는 que에 추가해주는 방식으로 탐색을 진행한다. 해당 좌표를 방문했다면 check 값을 바꿔주어 방문 체크를 해준다. bfs를 새로 실..

문제 https://www.acmicpc.net/problem/9024 문제풀이 num 배열을 정렬하고 k값 보다 큰지 아닌지 비교해가면서 이분탐색을 진행한다. 그 값이 k보다 크면 mid-1 값을 r로 설정해주고 작으면 min+1 값을 l로 설정해준다. k와 두 수의 합의 차이가 mini 값보다 작으면 mini 값을 없데이트 해주고 cnt=1로 초기화한다. mini 값과 같으면 cnt+=1을 해준다. 코드 import sys input=sys.stdin.readline t=int(input()) for i in range(t): n,k=map(int,input().split()) num=list(map(int,input().split())) num.sort() mini=200000000 for j in..