유니온 파인드 알고리즘이란?

그래프 알고리즘의 일종으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다.

 

def find(x,parent):
    if x != parent[x]:
        parent[x] = find(parent[x],parent)
    return parent[x]

def union(a,b,parent):
    a = find(a,parent)
    b = find(b.parent)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

 특정 노드의 루트 노드를 찾는 find함수와 두 노드를 합치는 union 함수로 이루어져있다.

find 함수는 재귀함수를 이용해 특정 노드의 루트 노드가 나올때까지(자기 자신이 부모일때까지) 반복해서 찾아내고

union함수는 find 함수를 이용해 주어진 두 노드의 루트 노드를 찾은 후 작은 수 큰 수의 부모 노드가 되도록 변경한다.

 

그래프의 간선이 생길 시 union함수를 이용해 두 노드를 합치는 과정을 반복한다면

특정한 두개의 노드가 주어졌을때 find 함수를 이용해 두 그래프의 루트 노드를 비교하고 같은 그래프에 속하는지 알 수 있다.

 

최소 신장 트리(MST, Minimum Spanning Tree)란?

 

그래프의 일부 간선을 선택해 그래프 내의 모든 정점을 최소 비용으로 연결해낸 트리이다.

크루스칼 알고리즘이 가장 대표적인 구현방법인데 실제로는 유니온 파인드 알고리즘을 사용해서 쉽게 구현할 수 있다.

 

크루스칼 알고리즘은 그리디 알고리즘의 일종으로 사이클이 발생하지 않는 최소 가중치의 간선만을 골라나가 연결하는 방법이다.

간선을 연결할때 union 함수를 사용한다면 특정한 간선을 연결하면 사이클이 발생하는지를 find 함수를 통해 알아낼 수 있다.

 

https://www.acmicpc.net/problem/1197

 

1197번: 최소 스패닝 트리

첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이

www.acmicpc.net

 

import sys,heapq
  
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a,b):
    a = find(a)
    b = find(b)
    if a < b:
        parent[b] = a
    elif b < a:
        parent[a] = b
        
v,e = map(int,sys.stdin.readline().strip().split())
parent = list(range(0,v+1))
route = []
ans = 0

for i in range(e):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    heapq.heappush(route,(c,a,b))
    
while route:
    c,a,b = heapq.heappop(route)
    if find(a) != find(b):
        ans += c
        union(a,b)
        
print(ans)

최소비용의 간선을 구하는 데에는 힙 자료구조를 사용하면 빠르게 구할 수 있다.

 

 

위상 정렬 알고리즘이란?

순서가 정해진 작업을 수행하기 위해 그래프를 이용해 순서를 결정하는 알고리즘이다.

 

가장 많이 사용하는 방법은 큐를 이용한 방법이다.

1. 그래프의 두 정점이 연결된 경우 도착지점의 진입차수를 1개씩 증가시킨다.

2. 진입차수가 0인 정점을 큐에 삽입한다.

3. 큐에서 원소를 하나씩 꺼내며 연결된 간선을 제거한다.(연결된 정점의 진입차수를 1개씩 감소시킨다)

4. 진입차수가 0이 된 정점을 새롭게 큐에 삽입한다.

5. 큐가 빌 때까지 3-4의 과정을 반복한다.

 

https://www.acmicpc.net/problem/2252

 

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net

import sys
from collections import deque

n,m = map(int,sys.stdin.readline().strip().split())
indegree = [0]*(n+1) #진입차수 배열
graph = [[] for _ in range(n+1)]
que = deque()

for i in range(m):
    a,b = map(int,sys.stdin.readline().strip().split())
    graph[a].append(b)
    indegree[b] += 1
    
for i in range(1,n+1):
    if indegree[i] == 0:
        que.append(i)
        
while que:
    now = que.popleft()
    print(now,end = " ")
    
    for nextPoint in graph[now]:
        indegree[nextPoint] -= 1
        if indegree[nextPoint] == 0:
            que.append(nextPoint)

 

https://www.acmicpc.net/problem/2042

 

2042번: 구간 합 구하기

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄

www.acmicpc.net

세그먼트 트리란?

 

여러개의 데이터 중에서 특정 구간의 합(곱, 최대, 최솟값 등)을 빠르게 구할 수 있는 자료구조이다.

투 포인터 역시 구간의 합을 구하는 알고리즘이지만 시간복잡도가 O(N) 이므로

똑같은 데이터가 주어지고 탐색을 여러번 반복해야 하는 상황이라면 효율적이지 못하다.

 

세그먼트 트리는 이진트리 구조를 활용하며 루트 노드(1번 노드) 에는 모든 구간의 합

그 밑의 자식노드(2번 노드, 3번 노드)는 부모 노드의 절반 구간까지의 합을 삽입하는식으로 계속 진행한다.

 

재귀함수를 이용하면 구현이 간단하며 루트 노드를 1번 노드로 설정하면 부모 노드 * 2가 왼쪽 자식 노드로 이어진다.

노드의 총 개수는 데이터의 개수 * 4로 설정하면 충분하다.

import sys
n,m,k = map(int,sys.stdin.readline().rstrip().split())
lst = [int(sys.stdin.readline().strip()) for _ in range(n)]
tree = [0]*n*4

def init(index,start,last): #범위를 좁혀나가는 식으로 재귀함수 이용 구현
    if start >= last:
        tree[index] = lst[start-1]
    else:
        c = int((start+last)/2)
        tree[index] = init(index*2,start,c) + init(index*2+1,c+1,last)
    return tree[index]

def find(index,start,last,left,right):
    if start > right or last < left:
        return 0
    elif start <= left and last >= right:
        return tree[index]
    else:
        c = int((left+right)/2)
        return find(index*2,start,last,left,c) + find(index*2+1,start,last,c+1,right)

def update(d,x,index,start,last):
    if x >= start and x <= last:
        tree[index] += d
        if start != last:
            c = int((start+last)/2)
            update(d,x,index*2,start,c)
            update(d,x,index*2+1,c+1,last)
        
init(1,1,n)

for i in range(m+k):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    
    if a == 1:
        d = c - lst[b-1]
        lst[b-1] = c
        update(d,b,1,1,n)
    else:
        if b > c:
            b,c = c,b
        print(find(1,b,c,1,n))

재귀함수를 이용하여 start,last를 이용 start와 last 사이의 중간값 c를 구한 후

init(index,start,last) = init(index*2,start,c) + init(index*2 + 1,c+1,last)와 같은 식으로 재귀적으로 구현하면 된다.

init 함수와 find 함수를 조금 수정하면 구간의 합 뿐 아니라 구간의 최대값,최솟값, 곱 등도 구할 수 있다.

GCD 알고리즘은 최대 공약수를 구하는 알고리즘이다.

GCD를 구현하는데 가장 흔히 알고리즘은 유클리드 호제법을 이용한 알고리즘이다.

수학적 증명은 그냥 넘어가자

def gcd(a,b):
    if a > b:
        a,b = b,a
        
    while b > 0:
        a,b = b,a%b
        
    return a

두 수 a,b(a < b)가 있을 때

b가 0이 될때까지 a에 b를, b를 a로 나눈 나머지를 계속 b에 대입시키면 남는 a가 최대 공약수가 된다.

 

https://www.acmicpc.net/problem/11689

 

11689번: GCD(n, k) = 1

자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오.

www.acmicpc.net

이 문제는 n이 주어졌을때 GCD(n,k) = 1이 되는 k 즉 서로소가 되는 n이하 자연수 k의 개수를 찾는 문제인데 n의 범위가 매우 커서 유클리드 호제법을 사용한다면 시간초과가 발생한다.

이 문제는 오일러 피 함수를 이용해 풀었다.

오일러 피 함수는 특정한 수 n을 소인수분해 해 p1^a1  *  p2^a2  * p3^a3... 꼴로 나올때 1~N중 N과 서로소인 숫자의 개수는 p1^a1(1 - (1/p1)) * p2^a2(1-(1/p2)) .... 라는 함수이다.

 

소인수 분해하는 과정은 에라토스테네스의 체를 이용해 최대한 빠르게 구현했고 그 이후 오일러 피 함수를 이용해 서로소인 숫자의 개수를 구했다.

n = int(input())
ans = 1
temp = int((n**(1/2)) + 1)
lst = [True]*temp
stack = []


for i in range(2,temp): # 에라토스테네스의 채
    if lst[i] == True:
        j = 2
        while i*j < temp:
            lst[i*j] = False
            j += 1
        
        if n%i == 0:
            stack.append(i)
            

i = 0

while i < len(stack) and stack[i] < n: # 오일러 피 함수 구현
    if n % stack[i] == 0:
        ans *= stack[i]
        n = n/stack[i]
    else:
        ans = ans*(1-(1/stack[i]))
        i += 1

if n != 1:
    ans = ans * n * (1 - (1/n))
    
print(int(ans))

 

투 포인터 알고리즘은 말 그대로 포인터 두 개를 이용해 문제를 해결하는 알고리즘을 말한다.

특정한 조건을 만족하는 배열의 연속된 부분합을 O(N)의 시간 안에 구해야 할 때 사용된다.

조건으로는 주로 더해서 특정한 수가 되는 부분합 찾기 등이 있다.

https://www.acmicpc.net/problem/1806

 

1806번: 부분합

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

www.acmicpc.net

이 문제의 조건은 주어진 수열에서 일정한 수 이상의 연속된 부분합 중 가장 짧은 것의 길이를 구하는 것이었다.

 

일반적인 투 포인터 알고리즘은 다음과 같이 작동한다.

포인터 두 개를 p1,p2라고 할 때

1. p1,p2를 모두 배열의 첫번째 인덱스를 가리키게 한다(p1 = 0, p2 = 0)

2. p1과 p2사이의 배열의 부분합을 구하고 조건에 맞는지 확인한다.

3. 조건을 충족시키지 못한다면 p2를 한칸 오른쪽으로 옮긴다(p2 += 1)

4. 조건을 충족시키면 모두 오른쪽으로 한칸씩 옮긴다 (p1 += 1, p2 +=1)

5. p2가 배열의 크기보다 커지기 전까지 2-5를 반복한다.

 

하지만 이 문제에선 일정 수 이상인 부분합의 길이 중 가장 짧은 것을 찾아야 하기 때문에 조건을 충족할 때 P1과 P2를 모두 이동시켜선 안된다.

(배열의 숫자 하나로도 일정 수 보다 클 수 있기 때문에 조건을 충족할때 배열의 길이를 줄여나가는 식으로 찾아야만 한다)

n,m = map(int,input().split())
lst = list(map(int,input().split()))

ans = 1000001
p1 = 0
p2 = 0
sumlst = lst[0]

while p1 <= p2:
    if sumlst >= m: #구간합이 m 이상일때
        if p2 - p1 +1 <ans:
            ans = p2 - p1 + 1
        sumlst -= lst[p1] #p1 1 증가
        p1 += 1
    else: #구간합이 m보다 작을때
        p2 += 1 #p2 1 증가
        if p2 >= n:
            break
        sumlst += lst[p2]
        
if ans == 1000001:
    print(0)
else:
    print(ans)

따라서 일반적인 투 포인터 알고리즘에서 조건 충족시에 p1만 증가하도록 바꾸고 반복문의 조건에 p1이 p2 보다 작을 때를 추가해주면 된다.

 


중간에서 만나기(meet in the middle) 알고리즘은 특정한 조건을 만족하는 조합(부분수열)을 구할때 배열을 두 부분으로 나누어 시간 복잡도를 줄이는 알고리즘이다.
https://www.acmicpc.net/problem/1208

 

1208번: 부분수열의 합 2

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

www.acmicpc.net

이 문제는 정수로 된 수열에서 부분수열의 합이 특정한 수 s가 되도록 하는 부분수열의 개수를 찾는 것이 목표이다.

모든 부분수열을 만들고 그 합을 확인해보면 풀 수 있지만 이러한 풀이의 시간 복잡도는 O(2^^n)이 되어 시간초과가 발생한다.

이때 주어진수열을 두개로 나눠 각각의 부분수열을 만든 후 합쳐본다면 시간 복잡도는 O(2^^n / 2)이 되어 문제를 풀 수 있게 된다.

n,s = map(int,input().split())
lst = list(map(int,input().split()))
center = n//2
lst1 = lst[:center] #1번째 배열
lst2 = lst[center:] #2번째 배열

dplst1 = []
dplst2 = []

def dfs1(start,count,last): # 첫번째 배열로 부분수열 만들기
    if start == last:
        dplst1.append(count)
    else:
        dfs1(start+1,count+lst1[start],last)
        dfs1(start+1,count,last)
        
def dfs2(start,count,last): # 두번째 배열로 부분수열 만들기
    if start == last:
        dplst2.append(count)
    else:
        dfs2(start+1,count+lst2[start],last)
        dfs2(start+1,count,last)
    
dfs1(0,0,center)
dfs2(0,0,n-center)
dplst1.sort()
dplst2.sort()

def lower_bound(nums, target):
    
    left, right = 0, len(nums)
    
    while left < right:  #left와 right가 만나는 지점이 target값 이상이 처음 나오는 위치
        mid = left + (right - left) // 2
        
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    
    return right

def upper_bound(nums, target):

    left, right = 0, len(nums)

    while left < right:  #left와 right가 만나는 지점이 target값 보다 큰 값이 처음 나오는 위치
        mid = left + (right - left) // 2

        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid 

    return right

ans = 0
for i in dplst1:
    ans += upper_bound(dplst2,s-i) - lower_bound(dplst2,s-i)
    
# print(dplst1)
# print(dplst2)
if s == 0:
    print(ans - 1)
else:
    print(ans)

부분수열을 만드는 과정은 dfs를 이용하면 쉽게 구현할 수 있다.

부분수열을 만든 후 첫번째 부분수열 배열에서 고른 수와 두번째 부분수열 배열에서 고른 수의 합이 s가 되는 조합의 수를 찾으면 된다.

두 부분수열 배열을 정렬한 후 첫번째 부분수열 배열을 반복문을 이용해서 모두 탐색하면서

합이 s가 되는 수가 두번째 배열에 있는지 이진탐색을 이용해서 찾아보면 빠르게 구할 수 있다.

 

이진 탐색 알고리즘이란?

 

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. - 위키백과

 

알고리즘의 작동원리 및 구현 방법은 다른 블로그에서 더 잘 설명해줄거니까 생략한다.

def binarySearch(lst,value):
    low = 0
    high = len(lst)-1
    
    while low < high:
        c = int((low+high)/2)
        if lst[c] < value:
            low = c + 1
        elif lst[c] == value:
            return c
        else:
            high = c -1
            
    return False

 

백준 문제를 풀던 중 시간초과가 발생했을 때 첫번째로 확인할 부분은 코드에 시간복잡도를 잡아먹는 부분이 있는가를 찾아봤는데

주로 나왔던 실수는

 

1. 반복문 안에서 배열을 초기화했을 때 배열을 매번 새로 만들면서 시간초과

2. 배열을 순차탐색하는 코드의 존재였다.

 

2번 같은 문제를 해결하는데 가장 유용한 해결책으로 이진 탐색을 자주 사용했다.

 

이진탐색의 응용인 upper_bound, lower_bound를 사용하면 문제가 효과적으로 풀리는 경우도 많이 존재했다.

def lower_bound(lst,value): # value 보다 크거나 같은 숫자가 처음으로 나타나는 위치 반환
    low = 0
    high = len(lst)
    
    while low < high:
        c = int((low+high)/2)
        if lst[c] < value:
            low = c + 1
        else:
            high = c
            
    return low

def upper_bound(lst,value): # value 보다 큰 숫자가 처음으로 나타나는 위치 반환
    low = 0
    high = len(lst)
    
    while low < high:
        c = int((low+high)/2)
        if lst[c] <= value:
            low = c + 1
        else:
            high = c
            
    return low

upper_bound, lower_bound 함수는 배열 안에서 특정 수의 위치를 찾아야하는 상황에서 사용되는데

그냥 이진탐색과 다르게 배열 안에 같은 숫자가 여러개 존재하거나 찾는 숫자가 배열에 존재하지 않을 수도 있을때

즉 여러가지 조건이 붙은 상황에서 탐색할때 굉장히 효과적으로 사용된다.

또 하나의 배열안에 특정한 숫자가 몇개나 있는지 알아야 할 때

upper_bound() - lower_bound() 를 이용하면 빠르게 알아낼 수 있다.

 

 

 

1. 이분탐색

2. 중간에서 만나기, 투포인터

3. GCD, 유클리드 호제법

4. 세그먼트 트리

5. CCW

6. 우선순위큐

7. 유니온파인드, 최소 스패닝 트리, 위상정렬

8. LIS

 

 

 

 

 

 

 

뭔가 정체기가 온 듯한 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분도 안되서 금방 풀 수 있었다.

 

 

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

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

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

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

 

1) 백준 13549 : 숨바꼭질 3

import heapq
INF = int(1e9)
minlst = [INF]*100001

n,k = map(int,input().split())

def dijkstra(start,end):
    minlst[start] = 0
    heap = [(0,start)]
    
    while heap:
        dist,now = heapq.heappop(heap)
        
        if now == k:
            break
        elif dist > minlst[now]:
            continue
        else:
            graph = [(now-1,1),(now+1,1),(now*2,0)]
            for endPoint,w in graph:
                if endPoint >= 0 and endPoint <= 100000 and dist+w < minlst[endPoint]:
                    minlst[endPoint] = dist + w
                    heapq.heappush(heap,(minlst[endPoint],endPoint))
        
dijkstra(n,k)          
print(minlst[k])

처음엔 BFS를 먼저 생각했으나 이동할때마다 걸리는 시간이 다르므로 불가능했다.

다익스트라 알고리즘을 조금 변형해 풀 수 있었다.

 

2) 백준 11404 : 플로이드

import sys
INF = int(1e9)

n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())
floid = [[INF]*n for _ in range(n)]

for i in range(m):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    if c < floid[a-1][b-1]:
        floid[a-1][b-1] = c
        
    
def fw(now):
    for i in range(n):
        for j in range(n):
            if i == j:
                floid[i][j] = 0
            else:
                if floid[i][j] > floid[i][now] + floid[now][j]:
                    floid[i][j] = floid[i][now] + floid[now][j]
    
for i in range(n):
    fw(i)
    
for i in range(n):
    for j in range(n):
        if floid[i][j] == INF:
            print(0,end = " ")
        else:
            print(floid[i][j], end = " ")
    print()

한 정점에서 다른 정점으로 향하는 최단 경로를 구하는 플로이드-워셜 알고리즘을 공부하고 기본 문제를 풀어봤다.

플로이드-워셜 알고리즘의 시간복잡도가 O(N**3) 이라는 점을 기억하자

 

3) 백준 1865 : 웜홀

import sys
INF = int(1e9)

t = int(sys.stdin.readline().strip())

for i in range(t):
    n,m,w = map(int,sys.stdin.readline().strip().split())
    floid = [[INF]*n for _ in range(n)]

    for i in range(m):
        a,b,c = map(int,sys.stdin.readline().strip().split())
        if c < floid[a-1][b-1]:
            floid[a-1][b-1] = c
        if c < floid[b-1][a-1]:
            floid[b-1][a-1] = c

    for i in range(w):
        a,b,c = map(int,sys.stdin.readline().strip().split())
        c = -c
        if c < floid[a-1][b-1]:
            floid[a-1][b-1] = c
    
    def fw(now):
        for i in range(n):
            for j in range(n):
                if floid[i][j] > floid[i][now] + floid[now][j]:
                    floid[i][j] = floid[i][now] + floid[now][j]
                
                if i == j and floid[i][j] < 0:
                    return -1
        return 0
    
    answer = "NO"
    for i in range(n):
        temp = fw(i)
        if temp == -1:
            answer = "YES"
            break
    
    print(answer)

마찬가지로 플로이드-워셜 알고리즘을 이용해 푸는 문제였다.

floyd 스펠링을 몰라서 floid 라고 쓴 건 넘어가자

 

4) 백준 14500 : 테트로미노

코드 133줄짜리 구현 문제였다.

배열과 반복문을 잘 다루는게 구현 문제를 잘 푸는 방법인 것 같다.

 

5) 백준 1719 : 택배

import sys
INF = int(1e9)

n,m = map(int,sys.stdin.readline().strip().split())
graph = [[INF]*n for _ in range(n)]
answer = [["-"]*n for _ in range(n)]

for i in range(m):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    graph[a-1][b-1] = c
    graph[b-1][a-1] = c
    
    answer[a-1][b-1] = b
    answer[b-1][a-1] = a
    
def fw(now):
    for i in range(n):
        for j in range(n):
            if i == j:
                graph[i][j] = 0
            if graph[i][j] > graph[i][now] + graph[now][j]:
                graph[i][j] = graph[i][now] + graph[now][j]
                answer[i][j] = answer[i][now]
        
for i in range(n):
    fw(i)
    
for i in range(n):
    for j in range(n):
        print(answer[i][j] , end = " ")
    print()

마찬가지로 플로이드-워셜 알고리즘을 사용해 푸는 문제였다.

특정 정점을 거쳐갔을 때 경로가 더 짧아진다면 배열을 갱신하는 플로이드-워셜 알고리즘의 원리를 잘 기억하자

 

6) 백준 1916 : 최소비용 구하기

import sys,heapq

INF = int(1e9)
n = int(sys.stdin.readline().strip())
m = int(sys.stdin.readline().strip())

graph = [[] for _ in range(n)]

for i in range(m):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    graph[a-1].append((b-1,c))
    
start,end = map(int,sys.stdin.readline().strip().split())
    
def dijkstra():
    minlst = [INF]*n
    minlst[start-1] = 0
    heap = [(0,start-1)]
    
    while heap:
        dist,now = heapq.heappop(heap)
        
        if now == end-1:
            print(dist)
            return
        elif minlst[now] < dist:
            continue
        else:
            for endPoint,w in graph[now]:
                if minlst[endPoint] > dist + w:
                    minlst[endPoint] = dist + w
                    heapq.heappush(heap,(minlst[endPoint],endPoint))
    
    
dijkstra()

간단한 다익스트라 활용문제였다

 

 

다익스트라, 플로이드-워셜 알고리즘을 이용한 문제들을 풀어봤는데

확실히 알고리즘의 기본 난이도가 높은 편이라 그런지 응용 문제들을 푸는게 굉장히 까다로워졌다.

지금 4일째 한 문제도 못 풀고 있는데 정체기가 온 것 같다.

 

2월까지 골드 1 달기로 목표를 바꿔봐야겠다.

사실 입대하기 전 알고리즘 공부를

 

DP, 트리 자료구조 정도에서 멈췄던 것 같다.

 

DP를 조금 더 풀어보고 다익스트라 알고리즘, 트리, 힙을 조금 더 공부해보려고 했다.

 

1) DP - 백준 11053 : 가장 긴 증가하는 부분 수열

#DP
import sys

n = int(sys.stdin.readline().strip())
lst = list(map(int,sys.stdin.readline().strip().split()))

answer = [[] for _ in range(n)]


def dp(i):
    j = i-1
    while j >= 0:
        temp = answer[j]
        if temp[-1] < lst[i] and len(temp) >= len(answer[i]):
            answer[i] = temp+[lst[i]]
        j -= 1
    if answer[i] == []:
        answer[i] = [lst[i]]
    
max = 0
for i in range(n):
    dp(i)
    if len(answer[i]) > max:
        max = len(answer[i])
print(max)

처음 생각했던 방식이 메모리초과로 잘 돌아가지 않았던 기억이 난다

주어진 문제를 분할해서 푼다는 개념을 떠올렸더니 풀이에 도움이 됐던 것 같다.

 

2) DP - 백준 2096 : 내려가기

import sys,copy

n = int(sys.stdin.readline().strip())

temp = list(map(int,sys.stdin.readline().strip().split()))
maxlst = copy.deepcopy(temp)
minlst = copy.deepcopy(temp)

for i in range(1,n):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    
    max0 = max(maxlst[0],maxlst[1]) + a
    min0 = min(minlst[0],minlst[1]) + a
    
    max1 = max(maxlst[0],maxlst[1],maxlst[2]) + b
    min1 = min(minlst[0],minlst[1],minlst[2]) + b
    
    max2 = max(maxlst[2],maxlst[1]) + c
    min2 = min(minlst[2],minlst[1]) + c
    
    maxlst = [max0,max1,max2]
    minlst = [min0,min1,min2]
    
    
print(f"{max(maxlst)} {min(minlst)}")

이 문제 역시 문제를 분할해서 푼다는 개념을 떠올리면 금방 풀 수 있었다.

 

3) 다익스트라 - 백준 1753 : 최단경로

 

import sys,heapq

INF = int(1e9)

v,e = map(int,sys.stdin.readline().strip().split())
start = int(sys.stdin.readline().strip())
graph = [[] for _ in range(v)]
minlst = [INF]*v

for i in range(e):
    a,b,w = map(int,sys.stdin.readline().strip().split())
    graph[a-1].append((b-1,w))
           
def dijkstra(start):
    heap = [(0,start)]
    minlst[start] = 0
    
    while heap:
        dist,now = heapq.heappop(heap)
        if minlst[now] < dist:
            continue
            
        for endPoint,w in graph[now]:
            if minlst[endPoint] > minlst[now] + w:
                minlst[endPoint] = minlst[now] + w
                heapq.heappush(heap,(minlst[endPoint],endPoint))
        
                 
dijkstra(start-1)

for i in range(v):
    if minlst[i] == INF:
        print('INF')
    else:
        print(minlst[i])

다익스트라 알고리즘은 그래프의 한 정점에서 다른 정점으로 가는 최단경로를 구하는 알고리즘이다.

이 때 정점간의 거리(간선의 가중치)가 항상 양수일때만 사용할 수 있다.

 

이때 힙 자료구조를 활용하면 시간복잡도를 개선할 수 있다.

처음에 힙을 이용하지 않고 풀려다가 시간초과가 발생했고

반복문의 조건을 제대로 따지지 않았다가 힙의 크기가 너무 커져 메모리초과가 발생했던 기억이 난다.

 

그냥 구현하는 법을 외워두는게 좋은 것 같다.

 

4) 다익스트라 - 백준 1504 : 특정한 최단 경로

import sys,heapq
INF = int(1e9)

n,e = map(int,sys.stdin.readline().strip().split())
graph = [[] for _ in range(n)]
minlst = [0]*n

for i in range(e):
    a,b,c = map(int,sys.stdin.readline().strip().split())
    graph[a-1].append((b-1,c))
    graph[b-1].append((a-1,c))
    
v1,v2 = map(int,sys.stdin.readline().strip().split())


def dijkstra(start):
    for i in range(n):
        minlst[i] = INF
        
    minlst[start] = 0
    heap = [(0,start)]
    
    while heap:
        dist,now = heapq.heappop(heap)
        
        if dist > minlst[now]:
            continue
        else:
            for endPoint,w in graph[now]:
                if dist + w < minlst[endPoint]:
                    minlst[endPoint] = dist + w
                    heapq.heappush(heap,(minlst[endPoint],endPoint))

ans1 = [0,0,0]
ans2 = [0,0,0]

dijkstra(0)
ans1[0] = minlst[v1-1]
ans2[0] = minlst[v2-1]

dijkstra(v1-1)
ans1[1] = minlst[v2-1]
ans2[1] = minlst[v2-1]

dijkstra(n-1)
ans1[2] = minlst[v2-1]
ans2[2] = minlst[v1-1]

if INF in ans1 and INF in ans2:
    print(-1)
elif INF in ans1:
    print(sum(ans2))
elif INF in ans2:
    print(sum(ans1))
else:
    print(min(sum(ans1),sum(ans2)))

다익스트라 알고리즘을 3번 사용하면 풀리는 문제였다.

정점간의 간선에 방향이 존재하지 않을 시

두 정점간의 최단거리는 출발지와 도착지가 바뀌어도 차이가 없다는 사실을 기억하자

+ Recent posts