알고리즘

백준(수업)

• 백준 11657 타임머신으로 빨리가기 - 벨만포드

  
  

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
edges=[]
distance=[sys.maxsize]*(n+1)

for i in range(m):
    start,end,time=map(int,input().split())
    edges.append((start,end,time))

distance[1]=0

for _ in range(n-1):
    for start,end,time in edges:
        if distance[start] != sys.maxsize and distance[end]>distance[start]+time:
            distance[end]=distance[start]+time

mcycle=False
for start,end,time in edges:
    if distance[start] != sys.maxsize and distance[end] > distance[start] + time:
        mcycle=True

if not mcycle:
    for i in range(2,n+1):
        if distance[i]!=sys.maxsize:
            print(distance[i])
        else:
            print(-1)

else:
    print(-1)

• 백준 11404 가장 빠른 노선 구하기 - 플로이드 워셜

import sys
input=sys.stdin.readline
n=int(input()) #도시 5
m=int(input()) #노선개수 14
distance=[[sys.maxsize for j in range(n+1)] for i in range(n+1)]#6x6 인접행렬

for i in range(1,n+1): #인접 행렬 초기화
    distance[i][i]=0 #인접 행렬 초기화

for i in range(m):
    s,e,v = map(int,input().split())
    if distance[s][e]>v: #중복된 노선중 더 저렴한 버스가 있으면
        distance[s][e]=v

#플로이드 워셜 수행
for k in range(1,n+1):
    for i in range(1,n+1):
        for j in range(1,n+1):
            if distance[i][j]>distance[i][k]+distance[k][j]:
                distance[i][j]=distance[i][k]+distance[k][j]

for i in range(1,n+1):
    for j in range(1,n+1):
        if distance[i][j]==sys.maxsize:
            print(0,end=' ')
        else:
            print(distance[i][j],end=' ')
    print()

• 백준 1197 최소신장트리 구하기

import sys
from queue import PriorityQueue

input=sys.stdin.readline
n,m=map(int,input().split())
pq=PriorityQueue()
parent=[0]*(n+1)

#유니온파인드를 위한 대표노드 리스트 초기화
for i in range(n+1):
    parent[i]=i

for i in range(m):
    s,e,w=map(int,input().split())
    pq.put((w,s,e))

def find(a):
    if a==parent[a]:
        return a
    else:
        parent[a]=find(parent[a])
        return parent[a]

def union(a,b):
    a=find(a)
    b=find(b)
    if a!=b:
        parent[b]=a

useedge=0
result=0

while useedge<n-1:#mst는 항상 n-1의 엣지를 사용함
    w,s,e=pq.get()
    if find(s)!=find(e):#같은 부모가 아닌 경우만 연결
        union(s,e)
        result+=w
        useedge+=1

print(result)

백준(자습)

• 백준 5622 다이얼

  
  

• 문제분석

  
  1) 입력 문자열 list 형태로 바꿔서 저장 ex) 입력:abc / mylist=['a','b','c']
  2) list의 길이만큼 반복하면서 list에 저장된 원소의 ascii 값을 문제가 요구하는 범위별로 나눠서 time에 누적하여 더함

• 백준 10812 바구니 순서 바꾸기

  
  

• 문제분석(오래걸림)

  
  1) n : 5 일 때 emp=[1,2,3,4,5]로 초기화
  2) m번 반복하면서 문제가 요구하는대로 잘라서 넣음
  3) ex) i,j,k 가 2,7,4 일 때 emp[i-1:j] = emp[k-1:j]+emp[i-1:k-1]
  --> 2,3,4,5,6,7 = 4,5,6,7 + 2,3 / 리스트 슬라이싱할 때 i:j 로 슬라이싱하면 i+1부터 j까지라서 i번째 리스트 원소도 포함해서 슬라이싱 하고싶다면 자르는 범위를 i:j가 아닌 i-1:j로 설정해야함