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

Algorithm-문제집

in Algorithm, Search

백준 1766 : 문제링크

  • 문제유형

    • 탐색
    • 힙
    • 위상정렬

  • 설명

    • 위상정렬
      1. 진입 차수가 0인 정점을 큐에 삽입
      2. 큐에서 원소를 꺼내 해당 원소와 간선을 제거
      3. 제거 이후 진입 차수가 0이 된 정점을 큐에 삽입
      4. 큐가 빌 때까지 2 ~ 3을 반복
    • 위상정렬 사용이유 : 2번 조건 - 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.)
    • 힙 사용이유 : 3번 조건 - 가능하면 쉬운 문제부터 풀어야 한다

  • 풀이

    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
    import heapq

    n, m = map(int, input().split())
    array = [[] for i in range(n + 1)]
    indegree = [0] * (n + 1)

    heap = []
    result = []

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

    for i in range(n+1):
        if indegree[i] == 0:
            heapq.heappush(heap, i)
        
    result = []

    while heap:
        data = heapq.heappop(heap)
        result.append(data)
        for y in array[data]:
            indegree[y] -= 1
            if indegree[y] == 0:
                heapq.heappuh(heap, y)

    for i in result:
        print(i, end = ' ')

Comment and share

Algorithm-카드 정렬하기

in Algorithm, Search

백준 1715 : 문제링크

  • 문제유형 :

    • 탐색
    • 힙
    • 그리디

  • 설명

    • 가장 작은 숫자의 카드 묶음을 먼저 합쳤을 때 최소값
    • heap을 사용해서 작은 값 두개를 pop한다
    • 추출한 두 개의 값을 합해서 결과에 더한다
    • 합한 값을 다시 heap에 push한다
    • heap에 값이 한 개 남았을 때 종료한다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    import heapq

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

    for i in range(n):
        data = int(input())
        heaq.heappush(heapq, data)

    result = 0

    while len(heap) != 1:
        one = heapq.heappop(heap)
        two = heapq.heappop(heap)
        sum_value = one + two
        result += sum_value
        heapq.heappush(heap, sum_value)

    print(result)

Comment and share

Algorithm-최소 힙

in Algorithm, Search

백준 1927 : 문제링크

  • 문제유형 :

    • 탐색

    • 힙

  • 설명

    • 파이썬에서 heapq 라이브러리를 이용하면 힙 구현 가능하다.

  • 풀이

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

    n = int(input())
    heap = []
    result = []

    for _ in range(n):
        data = int(input())
        if data = 0:
            if heap:
                result.append(heapq.heappop(heap))
            else:
                result.append(0)
        else:
            heapq.heappush(heap, data)

    for data in result:
        print(data)

Comment and share

Algorithm-중량제한

in Algorithm, Search, Binary Search

백준 1939 : 문제링크

  • 문제유형 :

    • 탐색

    • 이진탐색

    • BFS

  • 설명

    • 다리의 개수 M의 최대 100,000, 중량 제한 C는 최대 1,000,000,000

    • 이진탐색을 이용하면 시간 복잡도는 O(M * logC)

    • DFS로 도착지에 옮길 수 있는 지 확인

    • 한 번에 옮길 수 있는 물품의 최대값을 이진탐색으로 찾아낸다.

  • 풀이

    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
    37
    38
    39
    from collections import deque

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

    def bfs(c):
        queue = deque([start_node])
        visited = [False] * (n + 1)
        visited[start_node] = True
        while queue:
            x = queue.popleft()
            for y, weight in adj[x]:
                if not visited[y] and weight >= c:
                    visited[y] = True
                    queue.append(y)
        return visited[end_node]

    start = 1000000000
    end = 1

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

    start_node, end_node = map(int, input().split())

    result = start
    while(start <= end):
        mid = (start + end) // 2
        if bfs(mid):
            result = mid
            start = mid + 1
        else:
            end = mid - 1

    print(result)

Comment and share

Algorithm-공유기 설치

in Algorithm, Search, Binary Search

백준 2110 : 문제링크

  • 문제유형 :

    • 탐색

    • 이진탐색

  • 설명

    • 집의 개수 N의 최대는 200,000 이고 집의 좌표 X의 최대 1,000,000,000이다

    • 이진탐색을 이용하면 시간 복잡도는 O(N * logX)

    • 집 간 거리 Gap에 대해서 이진탐색을 한다.

  • 풀이

    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
    n, c = list(map(int, input().split(' ')))`

    array = []
    for _ in range(n):
        array.append(int(input()))
    array = sorted(array)

    start = array[1] - array[0]
    end = array[-1] - array[0]
    result = 0

    while(start <= end):    // 시간 복잡도 : O(logX)
        mid = (start + end) // 2
        value = array[0]
        count = 1
        for i in range(1, len(array)): // 시간 복잡도 : O(N)
            if array[i] >= value + mid:
                value = array[i]
                count += 1
        if count >= c:
            start = mid + 1
            result = mid
        else:
            end = mid - 1

    print(result)

Comment and share

성 지키기

in Algorithm, Search

백준 1236 : 문제링크

  • 문제유형 :

    • 탐색

  • 설명

    • 행 기준, 열 기준 중 더 큰 값을 출력한다.

  • 풀이

    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
    n, m = map(int, input().split())
    array = []

    for _ in range(n):
        array.append(input())

    row = [0] * n
    column = [0] * m

    for i in range(n):
        for j in range(m):
            if array[i][j] == 'X':
                row[i] = 1
                column[j] = 1

    row_count = 0
    for i in range(n):
        if row[i] == 0:
            row_count += 1

    column_count = 0
    for i in range(m):
        if column[j] == 0:
            column_count +=  1
        
    print(max(row_count, column_count))

Comment and share

트로피 진열

in Algorithm, Search

백준 1668 : 문제링크

  • 문제유형 :

    • 탐색

  • 설명

    • N의 최대값이 50이기 때문에 단순 구현

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    def ascending(array):
        now = array[0]
        result += 1
        for i in range(1, len(array)):
            if now < array[i]:
                result += 1
                now = array[i]
        return result

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

    for _ in range(n):
        array.append(int(input()))

    print(ascending(array))
    array.reverse()
    print(ascending(array))

Comment and share

베스트셀러

in Algorithm, Search

백준 1302 : 문제링크

  • 문제유형 :

    • 탐색

  • 설명

    • 파이썬 dictionary 자료형 사용(HashMap)

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    n = int(input())

    books = {}

    for _ in range(n):
        book = input()
        if book not in books:
            books[book] = 1
        else:
            books[book] += 1

    target = max(books.values())
    array = []

    for book, number in books.items():
        if number == target:
            array.append(book)

    print(sorted(array)[0])

Comment and share

새

in Algorithm, Search

백준 1543 : 문제링크

  • 문제유형 :

    • 탐색

  • 설명

    • N이 최대 1000000000 이다

    • K가 반복적으로 증가하므로, 새의 마리 수는 빠르게 증가한다

    • 요구하는 대로 단순 구현하면 된다

  • 풀이

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    n = int(input())
    result = 0
    k = 1

    while n != 0:
        if k > n:
            k = 1
        n -= k
        k += 1
        result += 1
        
    print(result)

Comment and share

Yechan Kim

author.bio


author.job