Algorithm-바이러스

in Algorithm, Graph, DFS

백준 2606 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • DFS

  • 설명

    • 시작 정점에서부터 도달할 수 있는 노드의 수를 계산

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    n = int(input())
    m = int(input())
    adj = [[] for _ in range(n + 1)]
    visited = [False] * (n + 1)
    count = 0

    for _ in range(m):
        x, y = map(int, input().split())
        adj[x].append(y)
        adj[y].append(X)

    def dfs(now_pos):
        global count
        count += 1
        visited[now_pos] = True
        for next_pos in adj[now_pos]:
            if not visited[next_pos]:
                dfs(next_pos)

    dfs(1)
    print(count - 1)

Comment and share

Algorithm-숨박꼭질

in Algorithm, Graph, BFS

백준 1697 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS

  • 설명

    • 특정 위치까지 이동하는 최단 시간을 계산
    • 이동 시간이 모두 1초로 동일, BFS를 이용하여 해결

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    from collections import deque

    MAX = 100001
    n, k = map(int, input().split())
    array = [0] * MAX

    def bfs():
        q = deque([n])
        while q:
            now_pos = q.popleft()
            if now_pos == k:
                return array[now_post]
            for next_pos in (now_pos - 1, now_pos + 1, now_pos * 2):
                if 0 <= next_pos < MAX and not array[next_pos]:
                    array[next_pos] = array[now_pos] + 1
                    q.append(next_pos)

    print(bfs())

Comment and share

Algorithm-DFS와 BFS

in Algorithm, Graph

백준 1260 : 문제링크

  • 문제유형 :

    • 그래프 탐색

    • BFS DFS

  • 설명

    • 정점 번호가 작은것부터 방문
    • 모든 노드와 모든 간선을 차례대로 조회하여 O(N + M)의 시간 복잡도

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    from collections import deque

    def dfs(v):
        print(v, end = ' ')
        visited[v] = True
        for e in adj[v]:
            if not(visted[e])
                dfs(e)

    def bfs(v):
        q = deque([v])
        while q:
            v = q.popleft()
            if not(visited[v]):
                visited[v] = True
                print(v, end = ' ')
                for e in adj[v]:
                    if not visited[v]:
                        q.append(e)

    n, m, v = map(int, input().split())
    adj = [[] for _ in range(n + 1)]

    for _ in range(m):
        x, y = map(int, input().split())
        adj[x].append(y)
        adj[y].append(x)

    for e in adj:
        e.sort()

    visited = [False] * (n + 1)
    dfs(v)
    print()
    visited = [False] * (n + 1)
    bfs(v)

Comment and share

Algorithm-가장 높은 탑 쌓기

in Algorithm, Dynamic Programming

백준 9251 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍

  • 설명

    • 곡의 개수가 N, 볼륨의 최댓값은 M이므로 동적프로그래밍을 이용하여 시간 복잡도 O(NM)

    • 핵심 아이디어: 모든 볼륨에 대하여 연주 가능 여부 계산

    • D[i][j+1] => i번째 노래일 때 j 크기의 볼륨으로 연주 가능한지 여부

    • 노래를 순서대로 확인, 매 번 모든 크기의 볼륨을 검사

    • D[i][j - V[i]] = True if D[i-1][j] = True

    • D[i][j + V[i]] = True if D[i-1][j] = True

      스크린샷 2020-11-06 오후 9 02 20

  • 풀이

        n, s, m = map(int, input().split())
    array = list(map(int, input().split()))

    dp = [[0] * (m + 1) for _ in range(n + 1)]
    dp[0][s] = 1

    for i in range(1, n + 1):
        for j in range(m + 1):
            if dp[i - 1][j] == 0:
                continue
            if j - array[i - 1] >= 0:
                dp[i][j - array[i - 1]] = 1
            if j + array[i - 1] <= m:
                dp[i][j + array[i - 1]] = 1

    result = -1
    for i in range(m, -1, -1):
        if dp[n][i] == 1:
            result = i
            break

    print(result)

Comment and share

Algorithm-기타리스트

in Algorithm, Dynamic Programming

백준 2655 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍

  • 설명

    • 벽돌의 수가 N개일 때, 시간복잡도 O(N^2)

    • 벽돌의 번호를 출력해야함 -> 계산된 테이블 역추적 가능해야함

    • 먼저 벽돌을 무게 기준으로 정렬

    • D[i] = 인덱스 i인 벽돌을 가장 아래에 두었을 때의 높이

    • 모든 0 <= j < i에 대해, D[i] = max(D[i], D[j] + height[i]) if area[i] > area[j]

      스크린샷 2020-11-06 오후 9 33 07

    • 이후에 Max Value에서 테이블 역추적

  • 풀이

        n = int(input())
    array = []

    array.append((0, 0, 0, 0))
    for i in range(1, n + 1):
        area, height, weight = map(int, input().split())
        array.append((i, area, height, weight))

    array.sort(key=lambda data: data[3])

    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        for j in range(0, i):
            if array[i][1] > array[j][1]:
                dp[i] = max(dp[i], dp[j] + array[i][2])

    max_value = max(dp)
    index = n
    result = []

    while index != 0:
        if max_value == dp[index]:
            result.append(array[index][0])
            max_value -= array[index][2]
        index -= 1

    result.reverse()
    print(len(result))
    [print(i) for i in result]

Comment and share

Algorithm-LCS

in Algorithm, Dynamic Programming

백준 9251 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍

  • 설명

    • 두 수열의 길이가 N 미만일 때, 시간 복잡도 O(N^2)으로 문제를 해결할 수 있습니다.
    • 수열 각각을 X, Y라고 함
    • D[i][j] = X[0..i]와 Y[0..j]의 공통 부분 수열의 최대 길이
    • 두 문자열의 길이를 조금씩 늘려가며 확인, 공통 부분 수열의 최대 길이를 계산
    • 점화식
      스크린샷 2020-11-06 오후 6 30 38

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    x = input()
    y = input()

    dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]

    for i in range(1, len(x) + 1):
        for j in range(1, len(y) + 1):
            if x[i - 1] == y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i][j - 1], dp[i - 1][j])

Comment and share

Algorithm-가장 긴 증가하는 부분 수열

in Algorithm, Dynamic Programming

백준 11053 : 문제링크

  • 문제유형 :

    • 탐색

    • 동적 프로그래밍

  • 설명

    • 수열의 크기가 N일 때, 기본적으로 동적 프로그래밍 알고리즘으로 O(N^2)으로 해결

    • D[i]는 array[i]를 마지막 원소로 가지는 부분 수열의 최대 길이

    • 모든 0 <= j < i에 대하여, D[i] = max(D[i], D[j] + 1) if array[j] < array[i]

    • N = 6 일 때

      스크린샷 2020-11-05 오후 9 30 40

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    n = int(input())
    array = list(map, input().split())
    dp = [1] * n

    for i in range(1, n):
        for j in range(0, i):
            if array[j] < array[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    print(max(dp))

Comment and share

Algorithm-평범한 배낭

in Algorithm, Dynamic Programming

백준 12865 : 문제링크

  • 문제유형 :

    • 탐색

    • 동적 프로그래밍

  • 설명

    • 물품의 수 N, 배낭에 담을 수 있는 무게 K

    • 동적 프로그래밍을 이용하여 시간 복잡도(NK)

    • 핵심 아이디어: 모든 무게에 대하여 최대 가치를 저장하기

    • D[i][j] = 배낭에 넣은 물품의 무게 합이 j일 때 얻을 수 있는 최대 가치

    • 각 물품의 번호 i에 따라서 최대 가치 테이블 D[i][j]를 갱신하여 문제를 해결

    • 점화식
      스크린샷 2020-11-05 오후 9 09 54

    • N = 4, K = 7 일 때
      스크린샷 2020-11-05 오후 9 11 23

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    n, k = map(int, input().split())
    dp = [[0] * (k + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = map(int, input().split())
        for j in range(1, k + 1):
            if j < weight:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight] + value)

    print(dp[n][k])

Comment and share

Algorithm-01타일

in Algorithm, DynamicProgramming

백준 1904 : 문제링크

  • 문제유형 :

    • 동적 프로그래밍

  • 설명

    • 동적 프로그래밍 문제를 풀기 위해서는 점화식(인접한 항들 사이의 관계식)을 세워야 한다.

      스크린샷 2020-10-30 오후 7 19 58

    • D[i] = 수열의 길이가 i일 때의 경우에 수

    • D[i] = D[i-1] + D[i-2]

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    n = int(input())

    dp = [0] * 1000001
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n+1)
        dp[i] = (dp[i - 2] + dp[i - 1]) % 15746

    print(d[[n]])

Comment and share

Java-Advanced11-RegularExpressions

in Java, Java Advanced

정규표현식 (Regular Expression)

정규표현식

  • 특정 조건에 맞는 문자열을 검색/치환하는 패턴 기반의 식
  • 이메일, 전화번호 등 특정한 형식에 맞는지 validation하는 데에 사용

정규표현식 표현 방법

  • 정규 표현식의 기본 작성 방식

    1
    "/패턴/[플래그(Opt.)]"

  • 기본 메타 문자

    메타 문자 의미
    ^x x로 시작
    x$ x로 끝
    .x x앞에 하나의 문자가 있음
    x+ x가 1번 이상 반복
    x? x가 있거나 없음
    x* x가 0번 이상 반복
    `x y`

  • 괄호의 활용

    regexp 의미
    (xy) 괄호 안의 내용을 그룹화
    x{n} n번 반복됨
    x{n,} n번 이상 반복됨
    x{n, m} n번 이상, m번 이하 반복됨
    [xy] x 또는 y
    [a-z] 알파벳 소문자 (a~z)
    [0-9] 숫자
    [가-힣] 한글
    [^x] x가 아닌 것
    [^0-9] 숫자가 아닌 것

  • \ 축약 문자

    regexp 의미
    \^, \., … \ 뒤에 나오는 문자를 문자로 처리
    \b 단어의 경계를 찾는다.
    \B 단어의 경계가 아닌 것을 찾는다.
    \d 숫자를 찾는다.
    \D 숫자가 아닌 것을 찾는다.
    \s 공백 문자를 찾는다.
    \S 공백 문자가 아닌 것을 찾는다.
    \w [a-zA-Z0-9_]
    \W [^a-zA-Z0-9_]

    JAVA에서는 \\\ 처럼 입력해야 \\처럼 동작한다

  • 유용한 정규식 예

    • 한글 이름 : ^[가-힣]{2,5}$
    • 핸드폰 번호: ^01(0|1|2|6|9)[-\s]?\d{3,4}[-\s]?\d{4}$
    • 이메일 주소: ^[\w\.-]{1,64}@[\w\.-]{1,252}\.\w{2,4}$

Flag

Flag 기능
g 문자열 내 모든 패턴을 찾음
i 대소문자를 구분하지 않음
m 문자열의 모든 줄에서 찾음

정규표현식을 사용하는 클래스

Pattern 클래스

  • 정규식의 컴파일된 표현 입니다(정규식을 적용 가능하도록 컴파일해서 가지고 있습니다).

  • Pattern 클래스는 공개된 생성자를 제공하지 않습니다.

  • 패턴을 생성하려면 Pattern객체를 반환하는 정적 compile 메소드를 호출해야 합니다.

  • 이 메소드는 첫 번째 인자로 정규식 문자열을 받아 들입니다.

    메소드 설명
    public static Pattern compile(String regex) Pattern 객체를 생성
    public Matcher matcher(CharSequence input) 입력을 분석하는 Matcher 객체 생성
    public static boolean matches(String regex, CharSequence input) 입력이 regexp에 해당하는지 판단

Matcher 클래스

  • 패턴을 해석하고 입력 문자열에 대해 일치 작업을 수행하는 엔진입니다.

  • Pattern 클래스와 마찬가지로 Matcher는 어떤 공개된 생성자도 정의하고 있지 않습니다.

  • Matcher객체는 Pattern 객체의 matcher 메소드를 호출해서 얻습니다.

    메소드 설명
    find() 정규표현식에 부합되는 내용이 문자열에 포함되어 있는지 반환. 이전 검색 위치부터 이어서 검색.
    start() 패턴에 부합되는 요소의 시작 인덱스 반환
    end() 패턴에 부합되는 요소가 끝나는 위치 + 1을 반환
    matches() 문자열 전체가 정규표현식에 일치하는지 반환
    lookingAt() 비교하려는 문자열이 정규표현식으로 시작하는지 반환. 0번 인덱스부터 검색.
    replaceFirst() 일치하는 첫 패턴을 문자열로 대체
    replaceAll() 일치하는 모든 패턴을 문자열로 대체
    reset() Matcher의 정보를 리셋하여 0번 인덱스부터 다시 검색

정규식 캡쳐 그룹

  • 정규표현식에서 캡쳐링 그룹은 괄호로 둘러싼 영역이다.

  • 사용 예

    • 순서로 그룹 가져오기

      1
      2
      3
      4
      5
      6
      7
      8
      9
      Pattern pattern2 = Pattern.compile("^\\w+):(\\w+)\\.(\\w+)$");
      Matcher matcher2 = pattern2.matcher("filename:temp.png");

      matcher2.find();
      System.out.println(matcher2.group()); // 매칭된 전체가 출력
      System.out.println(matcher2.group(0)); // 매칭된 전체가 출력
      System.out.println(matcher2.group(1)); // 첫번째 그룹
      System.out.println(matcher2.group(2));
      System.out.println(matcher2.group(3));

    • Name으로 그룹 가져오기

      1
      2
      3
      4
      5
      6
      7
      8
       Pattern pattern2 = Pattern.compile("^(?<field>\\w+):(?<name>\\w+)\\.(?<ext>\\w+)$");
      Matcher matcher2 = pattern2.matcher("filename:temp.png");

      matcher2.find();

      System.out.println(matcher2.group("field")); // name group
      System.out.println(matcher2.group("name"));
      System.out.println(matcher2.group("ext"));

Comment and share

Yechan Kim

author.bio


author.job