세상의 변화에 대해 관심이 많은 이들의 Tech Blog search

파이썬 정규표현식(re) 사용법 - 01. Basic

|

파이썬 정규표현식(re) 사용법 - 01. Basic
파이썬 정규표현식(re) 사용법 - 02. 문자, 경계, flags
파이썬 정규표현식(re) 사용법 - 03. OR, 반복
파이썬 정규표현식(re) 사용법 - 04. 그룹, 캡처
파이썬 정규표현식(re) 사용법 - 05. 주석, 치환, 분리
파이썬 정규표현식(re) 사용법 - 06. 치환 함수, 양방탐색, 조건문
파이썬 정규표현식(re) 사용법 - 07. 예제(숫자)
파이썬 정규표현식(re) 사용법 - 08. 예제(단어, 행)
파이썬 정규표현식(re) 사용법 - 09. 기타 기능


이 글에서는 정규표현식 기초와 python library인 re 패키지 사용법에 대해서 설명한다.

본 글에서 정규표현식은 regex와 같이, 일반 문자열은 ‘regex’와 같이 표시하도록 한다.

파이썬 버전은 3.6을 기준으로 하나, 3.x 버전이면 (아마) 동일하게 쓸 수 있다.
2.7 버전은 한글을 포함한 비 알파벳 문자 처리가 다르다.


정규표현식의 기초

일대일 매칭되는 문자

정규표현식 안에서, 바로 다음 절에서 설명하는 메타문자를 제외한 모든 문자 하나는 일반 문자열 하나와 매칭된다. 예를 들어, a는 a와 매칭되고, 는 ‘가’와 매칭되는 식이다.
당연히 a가 ‘b’ 또는 ‘가’와 매칭되지는 않는다.

메타문자

어떤 프로그래밍 언어의 정규표현식이든 메타문자라는 것이 존재한다.
이는 특수한 기능을 하는 문자로, import 등 파이썬의 예약어와 비슷한 역할을 맡는 문자라고 생각하면 된다.

파이썬 re 모듈의 메타문자는 총 12개로 다음과 같은 것들이 있다.

` $()*+.?[\^{ `

이들 메타문자는 각각의 문자 하나에 매칭되지 않는다.
예를 들어 일반 문자인 a는 문자 ‘a’에 매칭하지만, 여는 소괄호 (는 문자 ‘(‘와 매칭하지 않는다.

그럼 찾고자 하는 문자열에 소괄호가 있으면 어떻게 하나?

위의 문자들의 앞에 백슬래시 \를 붙여 주면 일반 문자처럼 한 글자에 매칭된다. 예를 들어 \(는 문자 ‘(‘와 매칭된다.

이들의 사용법은 차차 알아보도록 하자.

semi-메타문자

사실 이건 필자가 붙인 이름이지만… 이들 문자는 평소에는 메타문자가 아니지만, 특수한 상황에서는 메타문자 역할을 하는 문자들이다.
], -, ) 가 있다.

닫는 괄호야 당연히 여는 괄호에 대응된다는 것은 알 수 있을 것이다. -는 이후에 설명한다.


re 패키지 기본 method

import

물론 py 파일에서는 import re를 해주어야 쓸 수 있다.

re.match(pattern, string, flags)

01_match

re.match 함수는 “문자열의 처음”부터 시작하여 패턴이 일치되는 것이 있는지를 확인한다.
다음과 같이 사용한다.

matchObj = re.match('a', 'a')
print(matchObj)

print(re.match('a', 'aba'))
print(re.match('a', 'bbb'))
print(re.match('a', 'baa'))
# 사실 match의 결과를 바로 print하지는 않는다. 결과를 활용하는 방법은 나중에 설명할 matchObj.group 함수를 쓰는 것이다.

결과

<_sre.SRE_Match object; span=(0, 1), match='a'>
<_sre.SRE_Match object; span=(0, 1), match='a'>
None
None

re.match 함수는 문자열의 처음부터 시작하여 패턴이 일치되는 것이 있는지를 확인한다.
위의 예시에서 첫번째는 패턴과 문자열이 동일하므로 매치되는 것을 확인할 수 있다.
두번째 예시는 문자열이 ‘a’로 시작하기 때문에 매치가 된다.
나머지 두 개는 ‘a’로 시작하지 않아 패턴 a와 매치되지 않는다. 매치되지 않을 때 re.match 함수는 None을 반환한다.

매치가 되었을 때는 match Object를 반환한다. 위의 결과에서 _sre.SRE_Match object를 확인할 수 있다.

re.match 함수는 인자로 1)pattern 2)string 3)flags를 받는다. 3번은 필수 인자는 아닌데, 어떤 옵션이 있는지는 뒤에서 설명한다.
각 인자는 각각 1)패턴 2)패턴을 찾을 문자열 3)옵션을 의미한다.

re.search(pattern, string, flags)

02_search

re.search 함수는 re.match와 비슷하지만, 반드시 문자열의 처음부터 일치해야 하는 것은 아니다.

다음 예시를 보자.

matchObj = re.search('a', 'a')
print(matchObj)

print(re.search('a', 'aba'))
print(re.search('a', 'bbb'))
print(re.search('a', 'baa'))

결과

<_sre.SRE_Match object; span=(0, 1), match='a'>
<_sre.SRE_Match object; span=(0, 1), match='a'>
None
<_sre.SRE_Match object; span=(1, 2), match='a'>

네 번째 결과가 달라졌음을 볼 수 있다. re.search 함수는 문자열의 처음뿐 아니라 중간부터라도 패턴과 일치되는 부분이 있는지를 찾는다.
따라서 네 번째 문자열 ‘baa’의 경우 1번째 index(두 번째 문자) ‘a’와 매치된다.

위의 결과에서 span=(0, 1) 를 확인할 수 있다. 위의 두 결과는 span=(0, 1)인데,
이는 0번째 문자부터 1번째 문자 전까지(즉, 0번째 문자 하나인 ‘a’)가 패턴과 매치되었음을 뜻한다.
span=(1, 2)의 경우 1번째 문자(‘baa’ 의 첫 번째 ‘a’이다)가 패턴과 매치되었음을 볼 수 있다.

re.findall(pattern, string, flags)

03_findall

이름에서 알 수 있듯이 re.findall 함수는 문자열 중 패턴과 일치되는 모든 부분을 찾는다.

matchObj = re.findall('a', 'a')
print(matchObj)

print(re.findall('a', 'aba'))
print(re.findall('a', 'bbb'))
print(re.findall('a', 'baa'))
print(re.findall('aaa', 'aaaa'))

결과

['a']
['a', 'a']
[]
['a', 'a']
['aaa']

각 예시에서, 문자열의 a의 개수를 세어 보면 잘 맞는다는 것을 확인할 수 있다.

함수 설명을 잘 보면, “non-overlapping” 이라고 되어 있다. 즉 반환된 리스트는 서로 겹치지 않는다는 뜻이다. 마지막 예시가 이를 말해주고 있다. 겹치는 것을 포함한다면 두 개가 반환되어야 했다.

re.finditer(pattern, string, flags)

04_finditer

re.findall과 비슷하지만, 일치된 문자열의 리스트 대신 matchObj 리스트를 반환한다.

matchObj_iter = re.finditer('a', 'baa')
print(matchObj_iter)

for matchObj in matchObj_iter:
    print(matchObj)

결과

<callable_iterator object at 0x000002795899C550>
<_sre.SRE_Match object; span=(1, 2), match='a'>
<_sre.SRE_Match object; span=(2, 3), match='a'>

iterator 객체 안에 matchObj가 여러 개 들어 있음을 확인할 수 있다.

re.fullmatch(pattern, string, flags)

05_fullmatch

re.fullmatch는 패턴과 문자열이 남는 부분 없이 완벽하게 일치하는지를 검사한다.

matchObj = re.fullmatch('a', 'a')
print(matchObj)

print(re.fullmatch('a', 'aba'))
print(re.fullmatch('a', 'bbb'))
print(re.fullmatch('a', 'baa'))
print(re.fullmatch('aaa', 'aaaa'))

결과

<_sre.SRE_Match object; span=(0, 1), match='a'>
None
None
None
None

맨 위의 예시만 문자열이 남는 부분 없이 정확하게 일치하므로 매칭 결과를 반환했다. 나머지 예시는 문자열이 뒤에 남기 때문에 매치되는 결과 없이 None을 반환했다.

match Object의 메서드들

match Object를 그대로 출력해서 쓰고 싶은 사람은 별로 없을 것이다. re.match 등의 결과로 얻은 matchObj를 활용하는 방법을 정리하면 다음과 같다.

Method Descrption
group() 일치된 문자열을 반환한다.
start() 일치된 문자열의 시작 위치를 반환한다.
end() 일치된 문자열의 끝 위치를 반환한다.
span() 일치된 문자열의 (시작 위치, 끝 위치) 튜플을 반환한다.
matchObj = re.search('match', "'matchObj' is a good name, but 'm' is convenient.")
print(matchObj)

print(matchObj.group())
print(matchObj.start())
print(matchObj.end())
print(matchObj.span())

결과

<_sre.SRE_Match object; span=(1, 6), match='match'>
match
1
6
(1, 6)

잘 세어보면 ‘match’가 1번째 문자부터 6번째 문자 직전까지임을 알 수 있다. 인덱스는 0부터이다.


다음 글에서는 정규표현식의 기초를 더 살펴보도록 한다.

Comment  Read more

It will update soon...

|

곧 업데이트됩니다…

Comment  Read more

BOJ 06086(최대 유량) 문제 풀이

|

참조

분류 URL
문제 최대 유량
참조 라이브러리 dinic.h, sharifa_header.h
이 글에서 설명하는 코드 06086_최대 유량

개요

시간복잡도: $ O(V^2 \cdot E) $

공간복잡도: $ O(V + E) $

문제 풀이

이 문제는 생긴 것부터가 네트워크 플로우 문제이다. Maximum Flow를 찾는 많은 알고리즘이 있지만, 디닉 알고리즘이 가장 빠르기 때문에 필자는 이 알고리즘을 사용하도록 하겠다.

구현

네트워크 플로우 문제는 모델링이 굉장히 중요한데, 이 문제는 모델링이 어렵지는 않다.

주의할 점으로는 간선을 입력받아 그래프를 생성할 때, 각 파이프가 양방향 수송이 가능하다고 하였으므로 최대 유량을 똑같이 (0이 아닌) cap으로 설정해주어야 한다는 것이다. 또 문자를 정점 번호로 변환할 때 번호가 겹치지 않도록 주의한다.

#include "../library/dinic.h"

#define MAX_V 52
#define S 0     // source
#define T 25    // sink
#define INF 1000000009

int E, cap, u, v;
Dinic network(MAX_V, S, T);

int main_06086() {
    ios::sync_with_stdio(false);    cin.tie(NULL);
    cin >> E;

    while (E--) {
        char x, y;
        cin >> x >> y >> cap;

        u = 'A' <= x && x <= 'Z' ? x - 'A' : x - 'a' + 26;
        v = 'A' <= y && y <= 'Z' ? y - 'A' : y - 'a' + 26;

        network.addEdge(u, v, cap, true);
    }

    int ans = 0;

    while (network.bfs()) {
        network.reset_next_v();
        while (true) {
            int flow = network.dfs(S, INF);
            if (!flow)
                break;
            ans += flow;
        }
    }

    cout << ans;

    return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있을까?

Comment  Read more

디닉 알고리즘(Dinic's Algorithm)

|

참조

분류 URL
문제 최대 유량
응용 문제 스포일러 1
참조 라이브러리 sharifa_header.h, bit_library.h
이 글에서 설명하는 라이브러리 dinic.h

그림 출처: wikipedia


개요

시간복잡도: $ O(V^2 \cdot E) $

공간복잡도: $ O(V^2) $ 또는 $ O(V+E) $

  • V는 정점(vectex)의 수, E는 간선(edge)의 수이다.

이 글에서는 네트워크 플로우(Network Flow) 분야에서 Maximum Flow를 구하는 알고리즘인 디닉 알고리즘에 대해서 설명한다.

Maximum Flow를 구하는 다른 대표적인 알고리즘으로 에드몬드-카프 알고리즘(Edmonds–Karp algorithm), 포드-풀커슨 알고리즘(Ford–Fulkerson algorithm)이 있지만, 현재 PS에서 구현할 만한 알고리즘 중 가장 빠른 알고리즘은 디닉 알고리즘이다. 그래서 여러 개 외울 필요 없이 알고리즘 하나만 알아두는 것이 좋을 듯 하다.

Network Flow(네트워크 플로우)

네트워크 플로우에 대한 기본적인 설명을 조금 적어 두려고 한다. 예를 하나 들면, Network Flow는 파이프가 복잡하게 연결되어 있고, 각 파이프는 물이 흐를 수 있는 최대 양이 정해져 있고, source에서 sink방향으로 물이 흐를 때, 물이 흐를 수 있는 최대 양을 구하는 것이라고 보면 된다.

01_network_flow

  • s는 source를 의미한다. 물이 나오는 원천이라고 생각하면 된다.
  • t는 sink를 의미한다. 물이 최종적으로 들어가는 곳이라 생각하면 된다. 모든 물(유량)은 source에서 sink로 흐른다.
  • 두 정점을 잇는 간선은 해당 정점 사이에 흐를 수 있는 최대 물(유량)을 의미한다. s에서 1번 정점으로 0/10이라고 적혀 있는데, 여기서 10이 최대 유량이다.
  • 잔여유량은 최대유량에서 현재 유량을 뺀 값이다. s에서 1번 정점으로 0/10인 것은 현재 유량이 0이고 따라서 잔여유량은 10이다.

네트워크 플로우의 Maximum Flow는 Minimum Cut과 깊은 연관이 있다.


알고리즘

디닉 알고리즘은 크게 두 단계로 이루어진다.

  1. BFS를 써서 레벨 그래프(Level Graph)를 생성하는 것
  2. DFS를 써서, 레벨 그래프에 기초한 차단 유량(Blocking Flow)의 규칙을 지키면서, 최대 유량을 흘려주는 것

레벨 그래프(Level Graph)

레벨 그래프는 각 정점들에 source로부터의 최단 거리를 레벨 값을 할당한 그래프이다. 아래 그림에서 source의 레벨은 0이되고 source와 인접한 1번과 2번 정점의 레벨은 1, 이후는 2… 등이 된다. 빨간색 숫자로 적혀 있는 것이 레벨이다.

02_residual_capacity

레벨 그래프는 BFS로 구현한다.

차단 유량(Blocking Flow)

디닉 알고리즘에서는, 유량을 흘려보낼 때 레벨 차이가 딱 1이 나는 정점으로만 유량을 보낼 수 있다. 즉 바로 위의 그림에서의 간선과 같은 곳으로만 보낼 수 있다. 레벨이 같아도 안 된다.

유량을 흘려보내는 것은 DFS로 구현한다. source에서 시작하여, 차단 유량 규칙을 만족하는 정점으로만 따라가면서 최종적으로 sink에 도달할 때까지 탐색하는 과정을 반복한다.

위의 레벨 그래프에서는 다음 세 경로를 DFS로 찾을 수 있다.

(s, 1, 3, 4): 유량 4
(s, 1, 4, t): 유량 6
(s, 2, 4, t): 유량 4

반복

BFS 1번 그리고 DFS를 한번씩 해서는 최대 유량이 찾아지지 않는다. 다만 복잡한 것은 아니고, 위의 과정을 반복해주면 된다.

다시 BFS를 돌려 레벨 그래프를 새로 생성한다.

03_residual_capacity

위의 레벨 그래프에서는 다음 경로를 DFS로 찾을 수 있다.

(s, 2, 4, 3, t): 유량 5

다시 레벨 그래프를 그리면, 더 이상 sink로 가는 경로가 없음(sink의 레벨이 $\inf$)을 알 수 있다. 알고리즘을 종료한다.

04_residual_capacity

구현

BFS는 어려운 부분이 아니기 때문에 설명은 생략하도록 하겠다.

DFS의 구현은 조금 까다롭다.

  1. 우선 sink(T)에 도달하면 종료한다.
  2. 종료할 때 max_flow라는 것을 리턴한다. 이는 Network Flow에서 수송량은 경로에 포함된 파이프 최대 유량의 최솟값이기 때문이다. flow의 계산식을 잘 보면 최대 유량과 min 연산을 취하는 것을 볼 수 있다.
  3. 레벨 차이가 1 나는지를 먼저 검사한다. 그리고 그 정점의 잔여 용량이 0보다 큰지 또한 검사한다.
  4. 만약 그런 정점을 찾았으면, 재귀적으로 DFS를 수행한다.
  5. DFS가 리턴되어 반환한 flow 값이 0보다 크면, 아직 DFS로 탐색할 수 있는 경로가 남아 있다는 뜻이다.
  6. 경로를 찾았으므로, 해당 경로를 따라서(스택에 재귀 호출로 쌓인 함수에 의해 자동으로 역추적됨) 잔여 용량을 줄여준다.
  7. 만약 어떤 flow도 0이라면, 경로를 찾지 못한 것이므로 종료한다.
  8. next_v라는 배열(벡터)이 있다. 이는 DFS에서 다음 경로를 효율적으로 찾기 위해 존재하는 배열이다.
    1. DFS로 경로를 탐색할 떄 정점 번호가 낮은 정점부터 탐색한다.
    2. 만약 처음에 1번 정점으로 가는 경로를 모두 찾았다면, 더 이상 1번 정점으로는 갈 필요가 없다. 이때 next_v[u]를 1 증가시켜, 다음부터는 2번 정점부터 탐색을 시작하도록 한다.
    3. 2번도 끝났으면 또 next_v[u]를 증가시킨다. 이를 반복한다.
    4. 코드 상으로는 int &i로 되어 있다. i가 레퍼런스로 선언되어 있기 때문에 for loop의 i++ 구문에 따라 같이 증가한다(i는 next_v[u]와 값을 공유한다)
    int dfs(int u, int max_flow) {
        if (u == T)
            return max_flow;

        for (int &i = next_v[u]; i < edges[u].size(); i++) {
            int v = edges[u][i].v, cap = edges[u][i].cap;

            if (level[u] + 1 == level[v] && cap > 0) {
                int flow = dfs(v, min(max_flow, cap));

                if (flow > 0) {
                    edges[u][i].cap -= flow;
                    edges[v][edges[u][i].ref].cap += flow;
                    return flow;
                }
            }
        }
        return 0;
    }

addEdge 함수의 inv는 각 간선이 양방향 수송이 가능하면 true로 지정하면 된다. sparse graph일 경우를 대비해 edges를 2차원 배열로 표현하지 않고 대신 역방향 간선에 대한 참조를 저장하고 있다. 이러면 정점이 많을 경우에도 메모리 사용량을 줄일 수 있다.

구현은 다음과 같다.

#pragma once

#include "sharifa_header.h"

struct Edge {   // u -> v
    int v, cap, ref;
    Edge(int v, int cap, int ref) :v(v), cap(cap), ref(ref) {}
};

class Dinic {
    int S, T;
    vector<vector<Edge> > edges;    // graph
    // level: 레벨 그래프, next_v: DFS에서 flow 계산 시 역추적에 사용
    vector<int> level, next_v;

public:
    Dinic(int MAX_V, int S, int T):S(S), T(T) {
        edges.resize(MAX_V);
        level.resize(MAX_V);
        next_v.resize(MAX_V);
    }

    void addEdge(int u, int v, int cap, bool inv) {
        edges[u].emplace_back(v, cap, (int)edges[v].size());
        edges[v].emplace_back(u, inv ? cap : 0, (int)edges[u].size() - 1);
    }

    bool bfs() {
        fill(level.begin(), level.end(), -1);

        queue<int> q;
        level[S] = 0;
        q.push(S);

        while (!q.empty()) {
            int u = q.front();   q.pop();
            for (auto edge : edges[u]) {
                int v = edge.v, cap = edge.cap;

                if (level[v] == -1 && cap > 0) {
                    level[v] = level[u] + 1;
                    q.push(v);
                }
            }
        }
        return level[T] != -1;
    }

    void reset_next_v() {
        fill(next_v.begin(), next_v.end(), 0);
    }

    int dfs(int u, int max_flow) {
        if (u == T)
            return max_flow;

        for (int &i = next_v[u]; i < edges[u].size(); i++) {
            int v = edges[u][i].v, cap = edges[u][i].cap;

            if (level[u] + 1 == level[v] && cap > 0) {
                int flow = dfs(v, min(max_flow, cap));

                if (flow > 0) {
                    edges[u][i].cap -= flow;
                    edges[v][edges[u][i].ref].cap += flow;
                    return flow;
                }
            }
        }
        return 0;
    }
};

문제 풀이

BOJ 06086(최대 유량)

문제: 최대 유량

풀이: BOJ 06086(최대 유량) 문제 풀이

스포일러 문제

문제: 스포일러 문제

풀이: 스포일러 풀이

Comment  Read more

BOJ 11658(구간 합 구하기 3) 문제 풀이

|

참조

분류 URL
문제 구간 합 구하기 3
참조 라이브러리 fenwick_tree_2D_BIT.h, sharifa_header.h
이 글에서 설명하는 코드 11658_구간 합 구하기 3

개요

시간복잡도: $ O(N^2 + M \log^2 N) $

공간복잡도: $ O(N^2) $

  • N은 원소의 수, M은 연산의 수이다.

문제 풀이

이 문제도 역시 인덱스 트리라고 부르는 자료구조를 써도 풀리긴 하지만, 펜윅 트리가 굉장히 간단하기 때문에 이것으로 문제를 풀었다.

원소가 하나씩 업데이트될 때, 구간의 합을 구하라는 문제는 그냥 펜윅 트리를 쓰라는 문제이다. 왜냐하면 BIT가 그에 최적화되어 있기 때문이다.

이 문제는 구간 합 구하기와는 달리 2차원이기 때문에, data 배열도 2차원으로 잡아야 한다. 즉, data[][] 형식이 될 것이다.

구간 합을 구하는 것은 1차원을 2차원으로 확장한 것에 불과하다.

  • 1차원은 sum(a,b) = sum(b) - sum(a-1)이었다.
  • 2차원은 sum(x1~x2, y1~y2) = sum(x2, y2) - sum(x1-1, y2) -sum(x2, y1-1) + sum(x1-1, y1-1)이다.
    • 손으로 그림을 딱 한번만 그려보면 위 식이 단번에 이해될 것이다.

업데이트 연산 역시 2차원으로 확장한 것에 불과하다.

구현

이 문제는 2차원이기 때문에 sum과 update에서 중첩 while문을 볼 수 있을 것이다.
그리고 BOJ 02042(구간 합 구하기) 문제 풀이와는 달리 arr 배열을 만들지 않고 풀이를 적었다.

#include "../library/sharifa_header.h"
#include "../library/fenwick_tree_2D_BIT.h"

int N, m;

int main_11658() {
	ios::sync_with_stdio(false);    cin.tie(NULL);

	cin >> N >> m;

    FenwickTree2D BIT(N);

    int w, x1, y1, x2, y2, val;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> val;
			BIT.update(i, j, val);
		}
	}
	while(m--){
        cin >> w >> x1 >> y1;
		if (w){
            cin >> x2 >> y2;
			cout << BIT.sum(x1, y1, x2, y2) << '\n';
        } else {
            cin >> val;
			BIT.update(x1, y1, val);
		}
	}
	return 0;
}

주의: 이 코드를 그대로 복붙하여 채점 사이트에 제출하면 당연히 틀린다. 저런 헤더 파일이 채점 사이트에 있을까?

Comment  Read more