oneway's history

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

그래프 복습.

이번 문제는 DFS를 이용하는 문제였다.

연결된 노드를 따라 건너면서 step이 4 이상이 되면 조건에 맞는다고 판단한다.

import sys
input = sys.stdin.readline
N, M = map(int, input().split(" "))
graph = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split(" "))
    graph[a].append(b)
    graph[b].append(a)

for i in range(N):
    graph[i].sort()

isEnd = False


def DFS(v, step, visited):
    # print("v = {}, step = {}, visited = {}".format(v, step, visited))
    global isEnd
    if isEnd == True:
        return
    if step >= 4:
        isEnd = True
        return

    for i in graph[v]:
        if visited[i] == False:
            visited[i] = True
            DFS(i, step+1, visited)
            visited[i] = False


for i in range(N):
    visited = [False for i in range(N)]
    visited[i] = True
    DFS(i, 0, visited)
    visited[i] = False
    if isEnd == True:
        break

print(0 if isEnd == False else 1)

백트랙킹이면 DFS함수 나올 때 visited[i] = False 해줘야하는데, 그거 까먹어서 1번 틀렸다,.

ㅇhttps://www.acmicpc.net/problem/5430

뭔가 딱봐도 deque를 써야할 것 같은 문제였다.

배열의 pop(0) 보다 deque의 popleft가 더 빠르기 때문이다.

처음에 빈 배열이 들어올 때, 그걸 아무것도 들어있지 않은 배열로 입력받아야 하는데

string형태로 받으면 얘가 [''] 이런 형태로 입력해버린다.

그래서 처음에 입력받을때 int형으로 받았다가, 마지막에 str형으로 변환해준다.

꽤 비효율적인 방법인 것 같으나 어쨌든 통과는했다.

import sys
from collections import deque
input = sys.stdin.readline

TC = int(input())
for tc in range(TC):
    isReversed = False
    isError = False
    text = input().rstrip()
    n = int(input())
    try:
        nlist = list(map(int, (input().rstrip()[1:-1].split(","))))
    except:
        nlist = []
    queue = deque()
    for i in nlist:
        queue.append(i)

    for order in text:
        if order == "R":
            isReversed = not isReversed
        elif order == "D":
            if len(queue) == 0:
                isError = True
                break
            else:
                if isReversed == False:
                    queue.popleft()
                else:
                    queue.pop()

    result = list(map(str, queue))
    if isError == True:
        print("error")
    else:
        if isReversed == False:
            print("[" + ",".join(result) + "]")
        else:
            print("[" + ",".join(result[::-1]) + "]")

https://school.programmers.co.kr/learn/courses/30/lessons/17680?language=python3 

LRU가 뭔지 일단 알아야 하는 문제. 알고나면 쉽다.

배열의 pop(0) 이 아주 시간복잡도를 올리는 녀석으로 알고있는데,

배열의 index 찾아주는 기능을 사용해야 했기 때문에 deque 같은 다른 자료구조 말고 배열을 사용했다.

def solution(cacheSize, cities):
    answer = 0
    cachebox = []

    if cacheSize == 0:
        answer = 5 * len(cities)
        return answer

    for city in cities:
        ref = city.lower()
        if ref in cachebox:
            answer += 1
            cachebox.append(cachebox.pop(cachebox.index(ref)))
        else:
            answer += 5
            if len(cachebox) != cacheSize:
                cachebox.append(ref)
            else:
                cachebox.pop(0)
                cachebox.append(ref)

    return answer

# LRU (Least Recently Used) 알고리즘을 활용하는 문제
# 반례가 있었는데 못찾아서 1시간동안 헤맸다.

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

처음엔 그냥 for문 써서 모든 경우를 찾았다.

그런데 더 쉬운 풀이방법과, 정규표현식을 이용한 방법도 깨달아서 업로드 해본다.

1번째 소스코드

import sys
input = sys.stdin.readline

# ===== 1차 풀이 ===== 108ms
T = input()
text = input().rstrip()

leng = len(text)
idx = 0
answer = 0
while idx < len(T)-leng:
    if T[idx:idx+leng] == text:
        idx += leng
        answer += 1
    else:
        idx += 1

print(answer)

2번째 소스코드

문자열에 count 하면 중복되지 않게 찾아준다는 점이 놀라웠다.

import sys
input = sys.stdin.readline

# ===== 2차 풀이 ===== 116ms
T = input().rstrip()
text = input().rstrip()
print(T.count(text))

3번째 소스코드

import re
import sys
input = sys.stdin.readline

# ===== 3차 풀이 ===== 196ms
T = input().rstrip()
text = input().rstrip()
regex = re.compile(text)
cnt = 0
while True:
    m = regex.search(T)
    if not m:
        break
    cnt += 1
    T = T[m.end():]
print(cnt)

정규표현식이 제일 느렸다.

꼭 정규표현식을 써야할 일이 아니면 그냥 for문 때리거나 내장함수 count 쓰는게 나은 것 같다.

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

여러개의 순서 조건이 등장하는게 마치 위상정렬을 써야할 것 같았는데

연관이 되지 않은 그룹이 두 개 이상 있을 때 판단할 수가 없단걸 생각하지 못했다.

왜냐면 위상정렬은 정렬 결과 1차원배열일 것이기 때문에.

플로이드 워셜 알고리즘이 어차피 출발지점에서 어느 지점을 건너 도착지점까지 가는걸

갱신하면서 최단거리를 구하는거라

비슷하게 생각하면 갱신이 됐다? -> 이어져있다 라는걸 이용해서 풀면 됐다.

플로이드 워셜 알고리즘을 통과하고 나면 만약 1 -> 2, 2 -> 4 처럼 1 -> 4 이렇게 이어지지 않았어도

graph[1][4] 의 값은 1가 되어있을 것.

그 의미는 4 라는 사건이 일어나기 전엔 1를 통과해야 한다는 의미다.

근데 그 역방향을 어떻게 생각해야하는건지 잘 모르겠어서

구글링의 힘을 좀 빌렸다,,

너무 간단했다. 1가 4보다 먼저 발생했느냐를 묻는다면

당연히 1 -> 4 가 이어진 상태니까, 즉 1 가 4보다 먼저 일어난거니까 -1을 출력하면 되는거고

4가 1보다 먼저 발생했느냐를 따질땐 그냥 4 -> 1 가 이어진 상태냐? 를 물으면 되는거였다.

풀이 코드

import sys
input = sys.stdin.readline

N, K = map(int, input().split())
graph = [[0 for i in range(N+1)] for i in range(N+1)]

for i in range(K):
    a, b = map(int, input().split(" "))
    graph[a][b] = 1

for k in range(1, N+1):
    for i in range(1, N+1):
        for j in range(1, N+1):
            if graph[i][k] and graph[k][j]:  # 거쳐갈 수 있는 길이 있으면
                graph[i][j] = 1

qn = int(input())
for i in range(qn):
    before, after = map(int, input().split(" "))
    if graph[before][after] == 1:
        print(-1)
    elif graph[after][before] == 1:
        print(1)
    else:
        print(0)

# 위상정렬을 사용해봤으나 연관 없는 두 그룹을 비교하는게 불가능하다는걸 깨달음
# after -> before 가는걸 graph[after][before] 로 판별할 수 있다는걸 생각하지 못했네..
# https://www.acmicpc.net/problem/1613

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

다익스트라와 흡사한 최단경로 구하기 알고리즘인

플로이드 워셜을 공부해봤다.

각 노드사이의 최단거리를 모두 구할 수 있다는게 장점이다.

거치는 k, 시작 i, 도착 j 을 기억하고

3중 for문 돌리는 것만 이해하면 쉬운 알고리즘인 것 같다.

풀이 소스코드

import sys

input = sys.stdin.readline
INF = sys.maxsize
N = int(input())  # 도시의 개수 2 ~ 100
M = int(input())  # 버스의 개수 1 ~ 100,000

graph = [[INF for i in range(N+1)] for i in range(N+1)]
for i in range(N+1):
    graph[i][i] = 0

# 시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있음을 주의
for m in range(M):
    a, b, w = map(int, input().split())
    if graph[a][b] > w:
        graph[a][b] = w

for k in range(1, N+1):  # 거치는
    for i in range(1, N+1):  # 출발
        for j in range(1, N+1):  # 도착
            if graph[i][k] + graph[k][j] < graph[i][j]:
                graph[i][j] = graph[i][k] + graph[k][j]

for i in graph[1:]:
    for j in i[1:]:
        # 갈 수 없는 경우 0을 출력한다는 조건을 조심
        if j == INF:
            print(0, end=" ")
        else:
            print(j, end=" ")
    print()

# 플로이드 워셜 알고리즘 => 어딘가를 거쳐서 갈 수 있는지를 구해라 or 어딘가부터 어디로 이동할 때 최소비용을 구해라
# graph를 잘 작성하고, k, i, j 만 기억하면 쉽다.

결과

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

코테에서 다익스트라 문제가 자주 등장하길래 꼭 숙지해야겠다 싶어서 다시 공부한다.

익숙해질때까지 비슷한 유형 문제들을 반복풀이 해야겠다.

소스코드

import sys
import heapq
input = sys.stdin.readline

dr = [-1, 1, 0, 0]
dc = [0, 0, -1, 1]

INF = sys.maxsize
TC = 1
while True:
    N = int(input())
    if N == 0:
        break
    graph = []
    distance = [[INF for i in range(N)] for i in range(N)]

    for n in range(N):
        s = list(map(int, input().split()))
        graph.append(s)

    heap = []
    heapq.heappush(heap, (0, 0, graph[0][0]))  # r, c, cost
    distance[0][0] = 0
    while heap:
        r, c, cost = heapq.heappop(heap)

        if r == N-1 and c == N-1:
            print("Problem {}: {}".format(TC, cost))
            TC += 1
            break

        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                newCost = cost + graph[nr][nc]

                # 앞으로 가려는 곳의 누적 cost가 지금까지 distance에 저장된 cost보다 싸면 갱신
                if newCost < distance[nr][nc]:
                    distance[nr][nc] = newCost
                    heapq.heappush(heap, (nr, nc, newCost))

# 다익스트라, heap 사용

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

DP를 곁들인 위상정렬 문제이다.

지난번에 풀었던 선수과목 문제랑 상당히 비슷했다.

2차원 배열로 graph를 쓰는 것 대신 collections의 defaultdict를 사용해보았다.

그런데 이것은 상당히 느렸다. 그냥 좀 더 타이핑 쳐서 2차원 배열로 하는게 나을 것 같다.

그리고 sys를 import 해놓고서 input = sys.stdin.readline 하는걸 잊어먹었는데도 잘 돌아가더라.

input()이 어쨌든 원래 있는 함수라 그랬다.

코드를 추가해주니 확연히 빨라졌다.

소스코드

import sys
from collections import defaultdict, deque
input = sys.stdin.readline

TC = int(input())
for tc in range(TC):
    N, K = map(int, input().split(" "))
    indegree = [0 for i in range(N+1)]
    result = [0 for i in range(N+1)]
    # graph = defaultdict(list)
    graph = [[] for i in range(N+1)]
    time = [0]
    tmp = list(map(int, input().split(" ")))
    for i in tmp:
        time.append(i)

    for k in range(K):
        a, b = map(int, input().split(" "))
        graph[a].append(b)
        # 진입차수
        indegree[b] += 1

    queue = deque()
    for i in range(1, N+1):
        if indegree[i] == 0:
            queue.append((i, time[i]))  # idx num, time
            result[i] = time[i]

    while queue:
        now, nowtime = queue.popleft()
        for i in graph[now]:
            indegree[i] -= 1
            result[i] = nowtime + time[i] if nowtime + \
                time[i] >= result[i] else result[i]
            if indegree[i] == 0:
                # queue.append((i, nowtime + time[i]))
                queue.append((i, result[i]))

    answerNum = int(input())
    print(result[answerNum])

# 위상정렬 + DP

result[i]로 갱신 해준걸 계속해서 들고 queue에 들어가야하는데,

그것을 잘못 생각해서 틀렸었다. (주석되어있는게 틀린코드)

defaultdict 쓰고, input = sys.stdin.readline 안해주었던게 944ms 이고

defaultdict 빼고 위 코드 넣어준게 592ms 이다.