oneway's history

정규표현식 regex 은 Regular Expression 의 줄임말.

1950년 Stephen Cole Kleene에 의해 개발됨

1. ^ 

문자열의 시작에 있는 문자

2. $

문자열의 마지막에 있는 문자

3. / (백슬래쉬)

/ 다음에 오는 표현식 (ex ^, $ 같은) 들을 문법적인 요소로서 작동하게 하지 않고 하나의 문자로 보게 만듬

escape 라고 부른다고 함

4. . (점)

어떠한 문자건, 공백이건 특수문자든 모든것을 포함

Q) ......

sol) 6개의 길이를 가진 문자 어느것이든 가능

5. [ ]

bracket 안에 있는 문자를 포함하는걸 찾음

Q) "How do you do?"에서 [oyu] 

sol) o, o, you, o

Q) "How do you do?" [owy][owy]

sol) ow, yo

6. [ - ]

[C-K] 하면 [CDEFGHIJK] 랑 똑같은 것

[C-Ka-d2-6] 하면 [CDEFGHIJKabcd23456] 이랑 똑같음

7. [^] (대괄호 안의 캐럿)

제외하고 나머질 찾음.

[^CD] 라고 쓰면 C, D를 제외한 모든걸 찾는 것

8. ( | )

(ab|cd|ed) 라고 하면 ab, cd, ed를 찾음

(Mon|Tues|Wednes)day 라고 하면 Monday, Tuesday, Wednesday 를 찾음

9. *

* 앞에 있는 것이 0 또는 여러개 존재하는지?

Q) .*

sol) .............. 와 같은것이니까 모든것을 전부 포함

Q) -A*-

sol) --, --A--, --AA--, --AAA-- 등 이런것들을 포함

10. +

+ 앞에 있는 것이 1개 이상으로 존재하는지?

( * 와 차이점은 *은 0개 있어도 판별함)

11. ?

? 앞에 있는 것이 0개 이거나 1개 인지?

( * 와 + 와의 차이점은 ?는 여러개를 판별하지 않음)

tip) *, +, ? 는 수량자 라고 부름

12. { }

{n} : 중괄호 앞에 있는 녀석이 n개 만큼인걸 찾음

{n,} : 중괄호 앞에 있는 녀석이 n개 이상인걸 찾음

{n,m} : 중괄호 앞에 있는 녀석이 n 이상 m 이하인걸 찾음

ex) AB*A 는 AB{0,}A 와 같다

ex) AB+A 는 AB{1,}A 와 같다 

ex) AB?A 는 AB{0,1}A 와 같다

13. 수량자(*, +, ?) 뒤에 붙은 ?

*? 하면 0개를 뜻함. 왜냐면 *은 0~여러개 를 뜻하는데, 그 중 가장 작은 0을 뜻하게 만드는 것

+? 하면 1개를 뜻함. 이유는 위와 같이 +는 1~여러개 를 뜻하는데, 그 중 가장 작은 1을 뜻함

?? 하면 0개를 뜻함. 이유는 위와 같다

(*, +, ?)는 탐욕적인(greedy) 수량자라서 가장 넓은 범위의 문자열을 가져옴.

ex) "<div>test</div><div>test2</div>" 라는 텍스트에서

<div>.+</div> 를 하면 "<div>test></div><div>test2</div>" 를 들고오지만

<div>.+?</div> 를 하면 "<div>test</div>" 를 가져온다.

이러한 ?를 게으른(lazy) 수량자 라고 함.

14. /w

word. 알파뱃, 숫자, "_" 를 포함하는 단어

[A-z0-9_] 랑 똑같음.

15.  /W

/w의 정반대. word가 아닌 것. 공백, 특수문자, 숫자를 포함하는 단어

16. /d

digit. 0~9를 포함하는 단어

17. /D

digit이 아닌 것. /d의 반대.

18. /b

boundary. 앞에 붙이면 앞에있는걸, 뒤에 붙이면 뒤에있는걸 체크

19. /B

/b의 반대

20. /A

가장 앞의 것을 체크

^와 다른점은, ^은 멀티라인일 때 앞에 붙은애를 모두 포함한다면 /A는 1개만 포함한다.

21. /Z

가장 뒤에 것을 체크

$와 다른점은, $은 멀티라인일 때 뒤에 붙은애를 모두 포함한다면 /Z는 1개만 포함한다.

22. (?="문자")

"문자" 를 포함하여 검색을 하지만, 결과로 포함을 시키지는 않는다.

"문자" 가 아니어도 /w /d /W /D 이런녀석들이 들어가도 됨.

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/2623

도대체 어떻게 푸는거지? 감이 전혀 안잡혀서 '알고리즘 분류'를 살펴봤더니

위상정렬 이라는 알고리즘 종류가 있다는 것을 알았다.

갓 동빈나 선생님께서 유튜브에 영상으로 설명을 잘 해주신 것이 있어서

보고 공부했다.

import sys
from collections import deque

input = sys.stdin.readline
N, M = map(int, input().split(" "))
indegree = [0 for i in range(N)]
graph = [[] for i in range(N)]

for _ in range(M):
    mlist = list(map(int, input().split(" ")))
    for a, b in zip(mlist[1:], mlist[2:]):
        # 간선 그리고 진입차수 세기
        graph[a-1].append(b-1)
        indegree[b-1] += 1

result = []
queue = deque()
# 진입차수 0인거만 골라 넣기
for i in range(N):
    if indegree[i] == 0:
        queue.append(i)

# 큐가 빌 때 까지 반복
while queue:
    # 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. 제거하면서 진입차수가 변경되는데, 0으로 된 녀석은 다시 큐에 넣어줌.
    now = queue.popleft()
    result.append(now + 1)
    for i in graph[now]:
        indegree[i] -= 1
        if indegree[i] == 0:
            queue.append(i)

# 큐가 끝났는데 진입차수가 남아있다는건 모든 정점을 돌지 못했다는 것 == 결론을 낼 수가 없음
if sum(indegree) > 0:
    print(0)
else:
    for i in result:
        print(i)

# 1 4 3 이라 하면, 3으로 가기 위해 4을 거쳐야 하고, 4로 가기위해 1을 거쳐야 함.
# 6 2 5 4 도 마찬가지로 4로 가기 위해 5를, 5로 가기 위해 2를, 2를 가기 위해 6을 거쳐야 함.
# 이러한 규칙을 만족하는 순서를 만들자.
# => 위상정렬 알고리즘 사용하기

# 위상정렬
# 1. 진입차수 (들어오는 간선의 개수)가 0인 정점을 큐에 삽입한다.
# 2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다. (이 때 꺼낸 순서를 result에 담음)
# 3. 간선 제거 이후 진입차수가 0이 된 정점을 큐에 삽입한다.
# 4. 큐가 빌 때 까지 2,3번 과정을 반복한다. 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.
# 위상정렬 정보 출처: https://www.youtube.com/watch?v=qzfeVeajuyc

MySQL 내에 있는 import Wizard 쓰면 오류가 겁나게 난다.

cmd로 접속해서 load data infile 해주니 됐다.

https://curriculum.cosadama.com/basic-sql/2-4/

https://ohgyun.com/777