기본기 문제 리스트

기본기를 다지기 위한 드릴 루틴으로 사용하는 문제들이다.

총 8개로 각 문제의 주제는 다음과 같다.

1. DFS와 BFS

2. 퀵정렬

3. 이진탐색

4. 다익스트라

5. 플로이드 워셜

6. 서로소 집합

7. 크루스칼

8. 위상정렬

 

문제 링크와 정답 코드

1. DFS와 BFS

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

1260번: DFS와 BFS

from collections import deque

input_n, input_m, input_v = map(int,input().split())
graph_list=[[] for _ in range(input_n+1)]

for i in range(input_m):
    node1, node2 = map(int, input().split())
    target_idx=0
    while target_idx<len(graph_list[node1]):
        if graph_list[node1][target_idx]>=node2: break
        target_idx+=1
    graph_list[node1]=graph_list[node1][:target_idx] + [node2] + graph_list[node1][target_idx:]
    target_idx=0
    while target_idx<len(graph_list[node2]):
        if graph_list[node2][target_idx]>=node1: break
        target_idx+=1
    graph_list[node2]=graph_list[node2][:target_idx] + [node1] + graph_list[node2][target_idx:]
        
    
dfs_history=[]
bfs_history=[]

def dfs(graph, v, visited):
    global dfs_history
    visited[v]= True
    dfs_history.append(v)
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

def bfs(graph, v, visited):
    global bfs_history
    visited[v]=True
    queue=deque([v])
    while queue:
        cur_node=queue.popleft()
        bfs_history.append(cur_node)
        for i in graph[cur_node]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True


dfs(graph_list, input_v, [False for _ in range(input_n+1)])
bfs(graph_list, input_v, [False for _ in range(input_n+1)])

for i in dfs_history:
    print("%d "%i, end="")
print()
for i in bfs_history:
    print("%d "%i, end="")

간선 정보를 인접 리스트에 담을 때, 오름차순으로 담기 위해 선형탐색 알고리즘이 포함되었다.

이부분을 이진탐색을 활용하거나 힙 자료형을 활용하는 방식으로 개선 가능하다.

 

2. 퀵정렬

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

2750번: 수 정렬하기

import sys
sys.setrecursionlimit(15000)

input_n=int(input())
li=[]
for i in range(input_n):
    li.append(int(input()))


def QuickSort(array, start, end):
    if start>=end: return
    pivot=start
    left=start+1
    right=end

    while left<=right:
        while left<=end and array[left]<=array[pivot]:
            left+=1
        while right>start and array[right]>=array[pivot]:
            right-=1
        if right<left:
            array[right], array[pivot]=array[pivot], array[right]
        else:
            array[left],array[right]=array[right], array[left]
    
    QuickSort(array,start,right-1)
    QuickSort(array,right+1,end)

QuickSort(li, 0, len(li)-1)
for i in li:
    print(i)

재귀 제한을 풀어주어야 한다.

부등호에서 등호의 포함 여부, 조건의 순서 등 신경 쓸 부분이 많은 코드이니 주의하자.

또한 연습때 left와 start, right와 end를 혼동하여 쓰는 실수가 있었으니 주의하자.

3. 이진탐색

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

1920번: 수 찾기

def Binary_Search(array, target, start, end):
    while start<=end:
        #print("looping..")
        mid = (start+end)//2
        if array[mid]==target:
            return mid
        elif target<array[mid]:
            end=mid-1
        else:
            start=mid+1
    return None


N=int(input())
array=list(map(int,input().split()))
array.sort()
M=int(input())
targets=list(map(int,input().split()))

for i in range(M):
    if Binary_Search(array, targets[i], 0, N-1) == None:
        print(0)
    else:
        print(1)

마찬가지로 부등호에 주의하자.

연습용 문제의 경우 입력받은 리스트를 정렬해야하는데, 예시코드에서는 맘편히 리스트의 sort 메서드를 사용했다.

퀵정렬까지 한번에 연습하고싶으면 퀵정렬 알고리즘을 구현해서 사용해도 연습에 좋을것이다.

4. 다익스트라

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

1753번: 최단경로

import heapq
import sys

INF = int(1e9)

def FastInput():
    return sys.stdin.readline().rstrip()

node_num, vertex_num = map(int,FastInput().split())
starting_node=int(FastInput())

graph=[[] for _ in range(node_num+1)]
distance=[INF for _ in range(node_num+1)]

for i in range(vertex_num):
    a,b,c=map(int,FastInput().split())
    graph[a].append((b,c))

def Dijkstra(graph, starting_node, distance):
    q=[]
    heapq.heappush(q, (0, starting_node))
    distance[starting_node]=0;
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost=dist+i[1]
            if cost < distance[i[0]]:
                distance[i[0]]=cost
                heapq.heappush(q, (cost, i[0]))

Dijkstra(graph, starting_node, distance)

for i in range(1, node_num+1):
    if distance[i]==INF:
        print("INF")
    else:
        print(distance[i])

부등식에서 등호에 주의하자.

도시와 도시 사이에 간선이 여러개여도 알아서 최적경로를 찾아주니 걱정하지말자.

 

5. 플로이드 워셜

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

11404번: 플로이드

import sys
def FastInput():
    return sys.stdin.readline().rstrip()
INF=int(1e9)

N=int(input())
M=int(input())

cost_table=[[INF for i in range(N+1)] for j in range(N+1)]

for m in range(M):
    a,b,c=map(int,FastInput().split())
    if cost_table[a][b]>c:
        cost_table[a][b]=c


for i in range(1, N+1):
    cost_table[i][i]=0

for pivot in range(1, N+1):
    for node1 in range(1, N+1):
        for node2 in range(1, N+1):
            cost_table[node1][node2]=min(cost_table[node1][node2], cost_table[node1][pivot]+cost_table[pivot][node2])

for i in range(1,N+1):
    for j in range(1,N+1):
        if cost_table[i][j]==INF:
            print("%d "%(0), end="")
        else:
            print("%d "%cost_table[i][j], end="")
    print()

삼중 반복문으로 구현하는 플로이드 워셜 알고리즘이다.

삼중 반복문에서 pivot이 가장 바깥 반복문에 들어가야 함에 주의하자.

6. 서로소 집합

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

1717번: 집합의 표현

import sys
sys.setrecursionlimit(100000)

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

def Union(parent, a, b):
    a=Find(parent,a)
    b=Find(parent,b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b

def FastInput():
    return sys.stdin.readline().rstrip()

N, M=map(int, FastInput().split())

parent=list(range(N+1))

for i in range(M):
    operation_type, a, b= map(int,FastInput().split())
    if operation_type == 0:
        Union(parent, a, b)
        continue
    
    a=Find(parent, a)
    b=Find(parent, b)
    if a == b:
        print("YES")
    else:
        print("NO")

경로압축기법을 잘 기억하도록하고,

재귀제한을 더 크게 설정하는 것을 잊지 말자.

7. 크루스칼

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

1922번: 네트워크 연결

import sys
sys.setrecursionlimit(1000000)

def FastInput():
    return sys.stdin.readline().rstrip()

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

def Union(parent, a, b):
    a=Find(parent, a)
    b=Find(parent, b)
    if a<b:
        parent[b]=a
    else:
        parent[a]=b


N=int(FastInput())
M=int(FastInput())

parent=list(range(N+1))
edges=[]
total_cost=0

for i in range(M):
    a,b,c=map(int,FastInput().split())
    edges.append((c,a,b))

edges.sort()

for e in edges:
    cost, a, b= e
    if Find(parent, a)!=Find(parent, b):
        Union(parent, a, b)
        total_cost+=cost

print(total_cost)

 

 

 

그리디 알고리즘과 서로소 집합 알고리즘을 활용하는 크루스칼 알고리즘 예제이다.

8. 위상정렬

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

2252번: 줄 세우기

from collections import deque
import sys
sys.setrecursionlimit(1000000)

def FastInput():
    return sys.stdin.readline().rstrip()

N, M = map(int,FastInput().split())
indegree=[0]*(N+1)
graph=[[] for i in range(N+1)]

for i in range(M):
    a, b = map(int, FastInput().split())
    graph[a].append(b)
    indegree[b]+=1


def TopologySort(graph, indegree):
    result = []
    q = deque()

    for i in range(1, N+1):
        if indegree[i]==0:
            q.append(i)
    
    while q:
        now = q.popleft()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                q.append(i)

    for i in result:
        print(i, end=' ')


TopologySort(graph, indegree)