oneway's history

ㅇ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://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 이다.

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

이거 위상정렬 문제 맞나 의심이 돼서 DFS 비슷하게 풀어봤는데 택도없이 시간초과났다.

바로 어제 공부한게 위상정렬인데.. 막상 써먹질 못하다니 ㅠ

배운점

1. 2차원 배열로 그래프를 그리는게 아니라 collections 의 defaultdict 사용하는 방법도 있더라.

    - 근데 이거 쓰면 좀 더 느림

성공코드

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

N, M = map(int, input().split())
# graph = [[] for i in range(N+1)]
graph = defaultdict(list)
indegree = [0 for i in range(N+1)]
result = [1 for i in range(N+1)]

for i in range(M):
    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, 1))  # 정점 번호, count

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

print(" ".join(map(str, result[1:])))

# 위상정렬. 거기에 dp적인 요소를 첨가함.
# 2차원 배열 graph 말고 collections 의 defaultdict 을 사용하면 좀 더 편리 (그러나 시간은 더 늘어나더라)

괴상한 DFS로 풀었다가 실패한 코드

import sys
from collections import deque

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

for i in range(M):
    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, 1))  # 정점 번호, count
        while queue:
            now, count = queue.pop()
            result[now] = count if result[now] < count else result[now]
            for j in graph[now]:
                queue.append((j, count+1))

print(" ".join(map(str, result[1:])))

결과

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

[실패] 라고 떠있길래 이걸 왜못풀었지? 싶었는데 못푼 이유가 있었다.

시간복잡도를 상당히 신경써야 하는 문제...

그냥 대충 행렬로 만들면 안됐다.

이전에 자바로 [실패] 를 엄청 많이 했길래 이걸 못풀었어? 하고 슥 풀라했다가

이번에도 [실패] 난무했다.

항상 풀던대로 visited 를 이용해줬는데,

얘를 빼고 풀어보니 통과가 됐다.

그리고 answer 리스트에 답을 담는 과정에서 불필요하게 if문이 도는걸 막았다.

import sys
from collections import deque
input = sys.stdin.readline
N, M, R = map(int, input().split())
graph = [[] for i in range(N+1)]
# visited = [False for i in range(N+1)]
answer = [0 for i in range(N+1)]

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

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


queue = deque()
queue.append(R)
answer[R] = 1
cnt = 2
while queue:
    num = queue.popleft()
    # visited[num] = True
    # if answer[num] == 0:
    #     answer[num] = cnt
    #     cnt += 1

    for idx in graph[num]:
        if answer[idx] == 0:  # 방문한적 없으면 고
            queue.append(idx)
            answer[idx] = cnt
            cnt += 1

for i in answer[1:]:
    print(i)

# visited 이녀석 생성하는 시간이 오래걸렸나? 
# visited 역할을 answer가 대신 하게 해줬더니 통과됐다.