수학과의 개발자 도전기

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

-정답 풀이: 

• 자료구조 설정

• 숫자들의 0번째 컬럼 값들이 불규칙적으로 입력돼서 어떻게 해야할지 잘 몰랐는데, sort()로 정렬하면됨(기억해두자)

• 결국 가장 긴 증가하는 부분수열 구하는 알고리즘이다. 이 수열에는 서로 교차하는 숫자가 존재 하지 않는다. 그 수가 최대이므로
• n에서 값을 빼면 최소로 교차하는 전깃줄 개수가 된다 

-전체풀이:

n=int(input())
dp=[0 for _ in range(n)]
w=[]
w_b=[]
for _ in range(n):
    w.append(list(map(int,input().split())))
    
#0번 컬럼에 숫자들 순서 맞춰서 정렬하기     
w.sort(key=lambda x:x[0])

#가장 긴 증가하는 부분수열 구하는 알고리즘     
for i in range(n):
    for j in range(i):
        if dp[i]<dp[j] and w[i][1]>w[j][1]:
            dp[i]=dp[j]
    dp[i]+=1
            
print(n-max(dp))
  
#가장 긴 증가하는 부분수열이면 교차할 수가 없음. 교차하는 거 최소니까 n에서 가장 긴수열 빼기

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

-정답풀이:

n,k=map(int,input().split())
dp=[[0]*201 for _ in range(201)]

for i in range(201):
    dp[1][i]=1
    dp[2][i]=i+1
    
for i in range(2,201):
    dp[i][1]=i
    for j in range(2,201):
        dp[i][j]=(dp[i][j-1]+dp[i-1][j])%10**9
print(dp[k][n])

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

-정답풀이: 

n,k=map(int,input().split())
c=[]
dp=[0 for i in range(k+1)]
for i in range(n):
    c.append(int(input()))
    
for i in range(1,k+1):
    a=[]
    for j in c:
        if j <=i and dp[i-j]!=-1:
            a.append(dp[i-j])
    if not a:
        dp[i]=-1
    else:
        dp[i]=min(a)+1
print(dp[k])

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

어떻게 푸는지 몰랐는데 찾아보니까 dfs(깊이 우선탐색)+dp를 이용해서 풀어야하는 문제. 

-원리(출처: https://chldkato.tistory.com/114)

• dfs + dp로 목적지까지 도착할 수 있는지 검사한다
• 루프를 방지하기 위해 방문 확인 배열 c를 -1로 초기화하고 이동할 때마다 0으로 다시 설정해준다

• 1. 과정을 진행하면서 c에 이미 저장된 값이 0이면 목적지까지 갈 수 없으므로 0을 반환한다
• 2. 1 이상의 값이면 이전에 그만큼 방문 경로가 있으므로 해당 값을 반환해서 더해준다
• 3. -1이면 방문하지 않은 경로이므로 dfs + dp 수행 

-정답풀이: 

m,n = map(int,input().split())
a=[]
for i in range(m):
    a.append(list(map(int,input().split())))

c=[[-1]*(n) for i in range(m)]   

dx=[1,-1,0,0]
dy=[0,0,1,-1]

def dfs(x,y):
    if x==m-1 and y ==n-1:
        return 1
    if c[x][y]!=-1:
        return c[x][y]
    c[x][y]=0
    for i in range(4):
        nx=x+dx[i]
        ny=y+dy[i]
        if 0<= nx < m and 0<=ny<n:
            if a[nx][ny]<a[x][y]:
                c[x][y]+=dfs(nx,ny)
    return c[x][y]

print(dfs(0,0))

-전체풀이: 

• 파이썬으로 실행하면 Recurssion Error 때문에 Pypy3로 실행해야한다
• 세로 리스트가 입력된다는 것을 알고 문제를 풀어야한다 

• 초기값 설정. m이 컬럼 개수, n이 행 개수. 컬럼위주로 진행해야한다(4,5번라인)
• 이해 안가는 부분: 7번(밑에처럼 하면 mxn 행렬이 만들어지는 것 아닌가?)

• dx=[동,서,북,남] ,  dy=[동,서,북,남] 을 표현 한 것 같음 

• 인덱스가 행렬 가장 오른쪽 아래면 멈추고 1 반환한다 

• 값이 -1이 아니면 이 전에 방문된 기록이 있으므로 그 기록을 반환한다

• 이제 c[x][y]==-1이면 방문하지 않은 경로이고, 루프를 막아야하므로 0으로 초기화하고 시작한다 
• nx의 값으로는 x-1,x,x+1이 가능하다. ny도 마찬가지 
• 해당 인덱스의 동서남북 값을 비교하는 과정 

• (x,y)의 상하좌우 값 중에 작은 값들이 있을 경우에만 dfs값 넣는다 

• 왼쪽 가장 위 값부터 시작해서 (0,0)으로 대입하는 건가?