수학과의 개발자 도전기

-문제: 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)

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

이전에 풀었던 연구실 문제와 풀이가 같다고 생각해서 그대로 풀다가 삽질했던 문제. 

마지막에는 메모리 초과까지 발생했다. 

문제 풀이 아이디어

1.  장애물을 설치하고

2. 선생님 주변에 학생이 있는지 확인

주변,확인 함수 구현 / process, watch 

3. 없으면 True 반환, 있으면 False 반환하고 

4. 그 값을 기준으로 답 출력 

연구실문제와 이 문제가  다른 점은 연구실 문제는 해당 위치 위,아래,좌,우만 보면 됐지만. 

여기는 한 방향에서 O나 S가 나올때까지 탐색을 할 수 있다는 점이다. 

이는 while i>=0 또는 while i<n 형태로 구현하면 된다 

선생님 시야에 학생이 들어온다면 process는 False를 반환한다. 

만약 아니라면 True를 반환하고, 이 경우에 YES를 출력, 아니면 NO를 출력한다. 

무작위로 하는 경우에는 항상 연산 끝나고 되돌려 놓기 

for data in combinations(spaces,3):
    for x,y in data:
        board[x][y]='O'

    if not process():
        find=True
        break
    for x,y in data:
        board[x][y]='X'

-정답풀이

from itertools import combinations
n=int(input())
board=[]
teachers=[]
spaces=[]

for i in range(n):
    board.append(list(input().split()))
    for j in range(n):
        if board[i][j]=='T':
            teachers.append((i,j))
        if board[i][j]=='X':
            spaces.append((i,j))
            
def watch(x,y,direction):
    if direction ==0:
        while y>=0:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            y-=1
    if direction ==1:
        while y<n:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            y+=1
            
    if direction ==2:
        while x>=0:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            x-=1
    if direction ==3:
        while x<n:
            if board[x][y]=='S':
                return True
            if board[x][y]=='O':
                return False
            x+=1
    return False

def process():
    for x,y in teachers:
        for i in range(4):
            if watch(x,y,i):
                return True
    return False 
    
find=False
for data in combinations(spaces,3):
    for x,y in data:
        board[x][y]='O'

    if not process():
        find=True
        break
    for x,y in data:
        board[x][y]='X'
if find:
    print('YES')
else:
    print('NO')

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

간단한 문제인데 괜히 어렵게 생각해서 틀린 문제. 

각각의 연산자를 문자로 바꾸고, 문자에 해당하는 연산을 하고,, 

문제해결 키는 숫자의 순서는 바뀌지 않으므로 연산들을 무작위로 나열한 다음 

숫자,연산자,숫자,연산자 순으로 값을 계산하면 되는데 이거를 dfs가 해준다. 

dfs의 파라미터로 숫자 위치 알려주는 i와 이전까지의 계산 결과인 now를 설정한다. (이 부분이 생각하기 어려웠다)

무작위로 나열하는 것은 if문들로 알 수 있다. 각각의 연산을 한번씩 한다음 dfs를 돌린 후 다시 연산 값 복귀. 

연산의 갯수가 0개인지 그 초과인지 어떻게 구별할 줄 몰랐는데 operation>0을 이용하면된다. 

n= int(input())
data=list(map(int,input().split()))
add, sub, mul, div = map(int,input().split())

min_value= 1e9
max_value = -1e9

def dfs(i,now):
    global max_value, min_value, add, sub, mul, div 
    
    if i==n:
        min_value=min(min_value,now)
        max_value = max(max_value,now)
        
    else:
        if add>0:
            add-=1
            dfs(i+1, now+data[i])
            add+=1
        if sub>0:
            sub-=1
            dfs(i+1, now- data[i])
            sub+=1
        if mul >0 :
            mul-=1
            dfs(i+1, now*data[i])
            mul+=1
        if div >0:
            div-=1
            dfs(i+1, int(now/data[i]))
            div+=1
            
dfs(1,data[0])
print(max_value)
print(min_value)