[코드트리 챌린지] 여섯번째 학습진단

이번엔 최고점을 찍었는데 또 Parametric Search 문제를 만나서 틀려버렸다.

이번까지 세 번째 장렬한 패배를 했는데 처음엔 정말 접근조차 못했는데

이제는 '아 Parametric Search 접근인 것 같은데?'라는 생각이 들긴 하는 것 같다.

그래도 아직 해를 찾는 방법을 찾는데 취약하고, 매번 문제가 색달라서 헷갈리는 것 같다.

 

아래 문제는 코드트리에서 제공해주는 문제은행에서 가져왔다.

유사 문제 풀이

코드트리 문제

https://www.codetree.ai/training-field/search/problems/painting-the-grid?&utm_source=clipboard&utm_medium=text

 

문제

0부터 1,000,000 의 숫자로 이루어진 n*n 격자가 주어지고, 임의의 현재칸 숫자와 d 이하의 차이를 갖는 인접한 칸을 색칠할 수 있다는 조건이 주어졌을 때, 절반 이상을 색칠할 수 있는 최소 d를 구하는 문제이다.

코드

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]
dxs= [0,0,-1,1]
dys= [-1,1,0,0]

def in_range(x,y):
    return 0<=x<n and 0<=y<n

def counts(d):
    visited = [[0]*n for _ in range(n)]
    max_cnt = 0
    for i in range(n):
        for j in range(n):
            if not visited[i][j]:
                cnt = 1
                s = [(i,j)]
                visited[i][j] = 1

                while s:
                    x,y = s.pop()
                    for idx in range(4):
                        nx,ny = x+dxs[idx], y+dys[idx]
                        if not in_range(nx,ny) or visited[nx][ny]: # 갈 수 없거나 방문했으면 skip
                            continue
                        if abs(arr[x][y]-arr[nx][ny]) > d: # 차이가 d보다 크면 skip
                            continue
                        visited[nx][ny] = 1
                        s.append((nx,ny))
                        cnt += 1
                        
                if cnt >= (n*n+1)//2:
                    return True
    return False

s,e = 0,1000001
while s<=e:
    mid = (s+e)//2

    if counts(mid):
        e = mid-1
    else:
        s = mid+1

print(s)

 

추가로 또 다른 진단 테스트를 하다가 만난 문제인데

쉬운 문제였지만 임의의 점이 아니라 주어진 점들 중에 최소 거리로  문제를 잘못 이해해서 엄청 헤맸던 문제를 소개한다.

사실 알았어도 수학적 개념을 떠올리지 못해서 다시 헤맸을 수도 있다...

 

https://www.codetree.ai/training-field/search/problems/minimum-of-distance-sum?&utm_source=clipboard&utm_medium=text

문제

n개의 점이 주어졌을 때, 하나의 (임의의) 점 좌표에서 각 점까지의 거리의 합이 최소가 되게 하는 문제이다.

이 문제는 x좌표를 정렬했을 때 중앙값과

y좌표를 정렬했을 때 중앙 값에 해당되는 좌표를 찾고mid_x, mid_y 와 각 점들 사이의 거리를 합한 값을 찾으면 된다.

코드

from collections import defaultdict

# 거리 구하기
def dist(p1,p2):
    x1,y1 = p1
    x2,y2 = p2
    return abs(x1-x2)+abs(y1-y2)

n = int(input())
xs = []
ys = []
points = []
for i in range(n):
    x,y = map(int,input().split())
    xs.append(x)
    ys.append(y)
    points.append((x,y))
xs.sort()
ys.sort()
mid_x = xs[n//2]
mid_y = ys[n//2]
print(sum([dist((mid_x,mid_y),points[i]) for i in range(n)]))

 

---

#코드트리 #코딩테스트 #코딩테스트실력진단