백준 플레를 향해서 - 12월 넷,다섯째주(12.19~12.31)

뭔가 정체기가 온 듯한 2주였다.

계란으로 바위치기라는 블로그 이름처럼

최대한 힌트 없이 솔브드 CLASS 문제들만 순서대로 풀었더니

한 문제 한 문제 푸는 시간이 너무 오래 걸리고 못 푸는 문제들도 많았다.

 

1) 백준 1486 : 등산

다익스트라 알고리즘을 조금 까다로운 조건으로 응용하는 문제였다.

 

2) 백준 1167 : 트리의 지름

import sys
n = int(sys.stdin.readline().strip())
tree = [[] for _ in range(n+1)]

for i in range(1,n+1):      
    string = list(map(int,sys.stdin.readline().strip().split()))
    index = string[0]
    for j in range(1,len(string)-1,2):
        tree[index].append((string[j],string[j+1]))

visited = [False]*(n+1)

def dfs(now):
    visited[now] = True
    max1 = 0
    max2 = 0
    distance = [0,0]
    
    for endPoint,dist in tree[now]:
        if visited[endPoint] == False:
            temp = dfs(endPoint)
            
            if temp[1] + dist > max1:
                max2 = max1
                max1 = temp[1] + dist
            elif temp[1] + dist > max2:
                max2 = temp[1] + dist
                
            if temp[0] > distance[0]:
                distance[0] = temp[0]
            
    if max1 + max2 > distance[0]:
        distance[0] = max1 + max2
    distance[1] = max1
    return distance

answer = dfs(1)
print(max(answer))

힌트 안보고 푸는데 3일이 걸렸다.

dfs를 응용해서 풀 수 있었는데

트리 자료구조의 재귀적인 특성을 사용하면 된다는 아이디어를 떠올리는데 시간이 오래 걸렸다.

 

3) 백준 1005 : ACM Craft

위상 정렬 알고리즘을 이용해 푸는 문제였다.

위상 정렬과 최소 신장트리, 유니온 파인드 알고리즘을 조금 더 공부해봐야할 것 같다

import sys
from collections import deque

t = int(sys.stdin.readline().strip())
for i in range(t):
    n,k = map(int,sys.stdin.readline().strip().split())
    d = list(map(int,sys.stdin.readline().strip().split()))
    graph = [[] for _ in range(n)]
    indegree = [0]*n
    minlst = [0]*n

    for i in range(k):
        a,b = map(int,sys.stdin.readline().strip().split())
        graph[a-1].append(b-1)
        indegree[b-1] += 1

    w = int(sys.stdin.readline().strip())
    dq = deque()
    for i in range(n):
        if indegree[i] == 0:
            dq.append(i)
            minlst[i] = d[i]

    while dq:
        now = dq.popleft()
        for nextPoint in graph[now]:
            indegree[nextPoint] -= 1
            if indegree[nextPoint] == 0:
                dq.append(nextPoint)
            if minlst[nextPoint] < minlst[now] + d[nextPoint]:
                minlst[nextPoint] = minlst[now] + d[nextPoint]

    print(minlst[w-1])

 

4) 백준 1799 : 비숍

n = int(input())
boardW = [[] for _ in range(n)]
boardB = [[] for _ in range(n)]
for i in range(n):
    temp = list(map(int,input().split()))
    for j in range(n):
        if temp[j] == 1:
            if (i+j)%2 == 0:
                boardW[(i+j)//2].append((i,j))
            if (i+j)%2 == 1:
                boardB[(i+j)//2].append((i,j))
ans1 = 0
ans2 = 0
def backW(now,stack):
    global ans1,n
    if now == n:
        ans1 = max(ans1,len(stack))
        return
    for y,x in boardW[now]:
        check = 0
        for yy,xx in stack:
            if yy-xx == y - x:
                check = 1
                break
        if check == 0:
            stack.append((y,x))
            backW(now+1,stack)
            stack.pop()
    backW(now+1,stack)
    
def backB(now,stack):
    global ans2,n
    if now == n:
        ans2 = max(ans2,len(stack))
        return
    for y,x in boardB[now]:
        check = 0
        for yy,xx in stack:
            if yy-xx == y - x:
                check = 1
                break
        if check == 0:
            stack.append((y,x))
            backB(now+1,stack)
            stack.pop()
    backB(now+1,stack)

for i in range(n):
    backW(i,[])
    backB(i,[])    

print(ans1+ans2)

이건 사실 질문 게시판을 조금 보고 풀었다.

아무리해도 시간초과가 계속 나오다가

체스판의 흑,백을 분리해서 푼다는 아이디어 1개를 질문게시판에서 봤더니

바로 통과해서 너무 허무했다.

백트래킹은 가지치기를 최대한 효율적으로 해보자

 

5) 백준 14003 : 가장 긴 증가하는 부분 수열 5

n = int(input())
lst = list(map(int,input().split()))
dp = [0]*n
indexList = [-1]*n

maxlen = 0
maxindex = 0
dp[0] = 0
indexList[0] = 0

for i in range(1,n):
    start = 0
    last = maxlen
    c = 0
    
    while start <= last:
        c = int((start+last)/2)
        if lst[dp[c]] == lst[i]:
            break
        elif lst[dp[c]] < lst[i]:
            start = c + 1
        else:
            last = c-1
                
    if lst[dp[c]] < lst[i]:
        dp[c+1] = i
        indexList[i] = dp[c]
        if c == maxlen:
            maxlen += 1
            maxindex = i
    else:
        if c == 0:
            dp[0] = i
            indexList[i] = i
        elif lst[dp[c-1]] < lst[i]:
            dp[c] = i
            indexList[i] = dp[c-1]
            

print(maxlen+1)
start = maxindex
last = indexList[start]
stack = []
while start != last:
    stack.append(start)
    start = last
    last = indexList[last]

stack.append(last)
while stack:
    print(lst[stack.pop()],end = " ")

무려 4일동안 이 문제에만 매달려서 겨우 풀었다.

근데 알고보니 이미 알고리즘이 개발되어 있는 유명한 문제였다.

LIS 알고리즘인데 시간 복잡도가 O(N**2) or O(NlogN)인 두 가지 방법이 있다.

처음 이틀 동안 O(N**2) 알고리즘을 만들고 시간 초과에 정신이 나가다가

이틀 뒤에 O(NlogN)짜리 알고리즘을 직접 개발해냈다.

인터넷에 나와있는 알고리즘 설명과 내 풀이가 정확하게 일치하는걸 보고 좀 뿌듯했다.

근데 걍 보고 할 걸

그래도 LIS 알고리즘을 완벽하게 이해할 수 있었다.

참고로 첫 번째로 해결해낸 플레티넘 문제다

 

6) 백준 11054 : 가장 긴 바이토닉 부분 수열

import sys

n = int(sys.stdin.readline().strip())
lst = list(map(int,sys.stdin.readline().strip().split()))
upScale = [1]*n
downScale = [1]*n

for i in range(1,n):
    for j in range(i-1,-1,-1):
        if lst[i] > lst[j]:
            upScale[i] = max(upScale[i],upScale[j]+1)
    
for i in range(n-2,-1,-1):
    for j in range(i+1,n):
        if lst[i] > lst[j]:
            downScale[i] = max(downScale[i],downScale[j]+1)
maxN = 0        
for i in range(n):
    if upScale[i] + downScale[i] > maxN:
        maxN = upScale[i] + downScale[i]
        
print(maxN-1)

LIS 알고리즘의 변형 문제였다.

앞에서 4일 동안 사투한 결과

30분도 안되서 금방 풀 수 있었다.

 

 

이젠 차라리 힌트 좀 보고 푸는게 나을지도 모르겠다.

힌트 하나도 없이 푸는건 너무 비효율적이지 않나 싶기도 하고

특정한 유형 문제를 연습해보고 싶어도 할 수가 없다.

차라리 빨리 플레 찍고 프로그래머스로 넘어가서 힌트 없이 푸는 연습을 해보는 것도 나쁘지 않은 것 같다.