수학과의 개발자 도전기

-문제 : https://www.acmicpc.net/problem/2667

스스로 푼 문제다! 전에 풀었을 때는 아쉽게 답지를 봤던 것 같은데, 이번에는 5트만에 정답이었다

dfs문제이고, gloabl count로 각 단지의 수를 구하는 것이 요점인 것 같다. 

그리고 탐색 시작하는 지점 방문처리하고 시작하는 것도!

-정답 풀이 :

n=int(input())
data=[]
for _ in range(n):
    data.append(list(map(int,input())))
dx=[-1,1,0,0]
dy=[0,0,-1,1]
result=[]

def dfs(x,y):
    global count
    for i in range(4):
        nx, ny = x + dx[i], y + dy[i]
        if 0 <= nx < n and 0<= ny < n :
            if data[nx][ny] and not visit[nx][ny]:
                visit[nx][ny]=1
                count+=1
                dfs(nx,ny)  
    
visit=[[0]*n for _ in range(n)]                
for i in range(n):
    for j in range(n):
        if not visit[i][j] and data[i][j]==1:  
            visit[i][j]=1
            count=1
            dfs(i,j)
            result.append(count)

            
print(len(result))            
result.sort()
for i in range(len(result)):
    print(result[i])

-문제 : https://www.acmicpc.net/problem/11501

스스로 푼 문제다! Silver Level 2 문제. 

처음에는 증가하는 부분수열 문제인가? 싶었는데, 1 1 3 1 2 같은 경우 부분 수열이 [1,1,3], [1,2] 두개가 있어서 이거를 어떻게 해야할지 몰랐다. 그래서 생각한게 완전탐색. 이걸로 돌리면 예제는 다 맞는데, 시간 복잡도가 n^2이라서 시간 초과가 떴다. 

이전에 그리디에서 완전탐색으로 쓴맛을 많이 봤기에 어떻게 해야하나 생각을 했다. 

순간 떠오른 방법이 리스트 거꾸로 진행하는 것. 그러면서 작은 인덱스의 값이 더 크다면 result라는 리스트의 해당 인덱스 값을 변경하고, 아니면 누적하는 방법을 생각했다. 

그런데 위 방법으로는 8%에서 틀리길래 반례를 생각해 봤더니, 1,1,3,1,2,5 였다. 가장 큰 값이 오른쪽 끝에 있을 때 위 방법으로는 

result=[3,3,3,5,5,5]인데 이것보다 [5,5,5,5,5,5]이 더 큰 값을 가진다. 

따라서 data인덱스 값 뿐 아니라 result 인덱스의 값도 같이 비교해준 뒤 result 값을 갱신하는 방식으로 진행했더니 정답이 떴다

-정답 풀이:

import sys
input=sys.stdin.readline
for _ in range(int(input())):
    n=int(input())
    data=list(map(int,input().split()))
    result=[0]*n
    result[-1]=data[-1]
    for i in range(n-2,-1,-1):
        if data[i]>data[i+1] and data[i]>result[i+1]:
            result[i]=data[i]
        else:
            result[i]=result[i+1]
    answer=0
    for i in range(n):
        answer+=result[i]-data[i]
    print(answer)

-문제: https://www.acmicpc.net/problem/2110

처음보는 유형의 문제라 어떻게 풀어야할지 몰랐던 문제다. 파라메트릭 서치 유형. 이것도 찾아봐야겠다 

아직 설명이 다 이해가지 않지만 이해한 부분만 정리해 보자면 

기본 값이 크기때문에 시간초과를 피하기 위해 이진탐색을 한다 

여기서 start,end,mid 값은 집 위치들의 차이(gap)을 의미한다.

start=min gap

end= max gap

이후 gap보다 큰 위치이 있는 집에 공유기를 설치하고, 공유기 수를 증가 시킨다. 

이때의 값이 원래 가지고 있는 공유기의 갯수(c)와 비교했을 때

c보다 작으면 설치한 공유기 수가 적은 것이고, 이는 gap이 너무 넓기때문에 발생하므로 gap을 줄여야 한다(end=mid-1)

c가 같거나 작으면 설치한 공유기의 수가 같거나 많은 것이고, 이때 원래의 gap을 저장하고(result=mid) gap의 값을 증가했을 때도 성립하는지 확인한다(이부분이 제일 이해가 가지 않는다)

-정답풀이: 

n,c=map(int,input().split())
data=[]
for _ in range(n):
    data.append(int(input()))
data.sort()

start=1
end=data[-1]-data[0]
result=0

while(start<= end):
    mid=(start+end)//2
    value=data[0] #공유기 설치하는 집 위치
    count=1 #공유기 갯수
    
    for i in range(1,n):
        if data[i]>=value+mid:
            value=data[i]
            count+=1
    if count >= c: #거리가 짧음 늘려야한다 
        start=mid+1
        result=mid
    else: #거리가 길어서 줄여야한다
        end=mid-1
print(result)

오름차순으로 정렬된 리스트에서 주어진 숫자가 몇개 있는지 출력하는 코드를 작성해야하는 문제였다.

시간 복잡도가 O(logN)이어야 한다. 

그래서 완전 탐색보다는 이진탐색으로 풀어야 하는 문제다. 

일반적인 이진탐색보다는 주어진 숫자가 시작하는 인덱스와 끝나는 인덱스를 구한 후 그 두 인덱스의 차이를 구하면 되는데

다른 방법으로는 내부 함수를 이용하면된다. bisect_left와 bisect_right다

-정답풀이:

from bisect import bisect_left,bisect_right

def count_by_range(data,left_value,right_value):
	right_index=bisect_right(data,right_value)
    left_index = bisect_left(data,left_value)
    return right_index-left_index
    
n,x=map(int,input().split())
data=list(map(int,input().split()))

count=count_by_range(data,x,x)
if count==0:
	print(-1)
else:
	print(count)