Algorithm-컵라면

in Algorithm, Greedy

백준 1781 : 문제링크

  • 문제유형 :

    • 탐욕 알고리즘

  • 설명

    • 정렬 및 우선순위 큐를 이용하여 O(NlogN)의 시간에 해결할 수 있다
    • 데드라인 기준으로 오름차순 정렬을 수행한다
    • 각 문제의 컵라면 수를 우선순위 큐에 넣으면서, 데드라이을 초과할 결우 최소원소를 제거한다

  • 풀이

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

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

    for i in range(n):
        a, b = map(int, input().split(' '))
        array.append((a, b))
    array.sort()

    for i in array:
        a = i[0]
        heapq.heappush(q, i[1])
        if a < len(q):
            heapq.heappop(q)

Comment and share

Algorithm-도서관

in Algorithm, Greedy

백준 1461 : 문제링크

  • 문제유형 :

    • 탐욕 알고리즘

  • 설명

    • 일직선상에 책들을 순서대로 위치시킨다
    • 0보다 큰 책들과 0보다 작은 책들을 나누어서 처리한다
    • 음수와 양수 좌표를 위해 두 개의 우선순위 큐를 이용한다
    • 마지막 책을 놓을 때는 다시 0으로 돌아올 필요가 없기 때문에, 가장 먼 책을 마지막으로 놓는다

  • 풀이

    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 = list(map(int, input().split(' ')))
    positive = []
    negative = []

    largest = max(max(array), - min(array))

    for i in array:
        if i > 0:
            heapq.heappush(positive, -i)
        else:
            heapq.heappush(negative, i)

    result = 0

    while positive:
        result += heapq.heappop(positive)
        for _ in range(m - 1):
            if positive:
                heapq.heappop(positive)

    while negative:
        result += heapq.heappop(negative)
        for _ in range(m - 1):
            if negative:
                heapq.heappop(negative)

    print(-result * 2 - largest)

Comment and share

Algorithm-센서

in Algorithm, Greedy

백준 1092 : 문제링크

  • 문제유형 :

    • 탐욕 알고리즘

  • 설명

    • 정렬만 수행하면 되므로 시간복잡도는 O(NlogN)
    • 각 센서를 오름차순으로 정렬한다
    • 각 센서 사이의 거리를 계산한다
    • 가장 거리가 먼 순서대로 k - 1개의 연결 고리르 제거한다

  • 풀이

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

    n = int(input())
    k = int(input())

    if k >= n:
        print(0)
        sys.exit()

    array = list(map(int, input().split(' ')))
    array.sort()

    distance = []
    for i in range(1, n):
        distances.append(array[i] - array[i - 1])
    distance.sort(reverse=True)

    for i in range(k - 1):
        distances[i] = 0
    print(sum(distances))

Comment and share

Algorithm-배

in Algorithm, Greedy

백준 1092 : 문제링크

  • 문제유형 :

    • 탐욕 알고리즘

  • 설명

    • 크레인과 박스를 무게 기준으로 내림차순 정렬한다
    • 무거운 박스부터 크레인이 옮기도록한다
    • 크레인의 수 N, 박스의 수 M일때 시간복잡도는 O(NM)이다

  • 풀이

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

    n = int(input())
    cranes = list(map(int, input().split()))

    m = int(input())
    boxes = list(map(int, input().split()))

    if max(cranes) < max(boxes):
        print(-1)
        sys.exit()

    positions = [0] * n
    checked = [False] * m

    cranes.sort(reverse=True)
    boxes.sort(reverse=True)

    result = 0
    count = 0

    while True:
        if count == len(boxes):
            break
        for i in range(n):
            while position[i] < len(boxes):
                if not checked[position[i]] and cranes[i] >= boxes[position[i]]:
                    checked[position[i]] = True
                    position[i] += 1
                    count += 1
                    break
                position[i] += 1
        result += 1

    print(result)

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

키로거

in Algorithm, Greedy

백준 5397: 문제링크

  • 문제유형 :

  • 설명

    1. 스택을 두 개 생성하고, 스택 두 개의 중앙을 커서라고 생각한다.

    2. 문자 입력: 왼쪽 스택에 삽입

    3. ‘-‘ 입력 : 왼쪽 스택에서 삭제

    4. ‘<’ 입력 : 왼쪽 스택에서 오른쪽 스택으로 이동

    5. ‘>’ 입력 : 오른쪽 스택에서 왼쪽 스택으로 이동

  • 풀이

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

    for _ in range(test_case):
        left_stack = []
        right_stack = []
        data = input()
        for i in data:
            if i == '-':
                if left_stack:
                    left_stack.pop()
            elif i == '<':
                if left_stack:
                    right_stack.append(left_stack.pop())
            elif i == '>':
                if right_stack:
                    left_stack.append(right_stack.pop())
            else:
                left_stack.append(i)
    left_stack.extend(reversed(right_stack))
    print(''.join(left_stack))

Comment and share

프린터 큐

in Algorithm, Greedy

백준 1874: 문제링크

  • 문제유형 : 큐, 구현, 그리디

  • 설명

    1. queue의 head의 값이 최대값과 동일한 지 확인한다.

    2. 동일하면 지정한 값과 동일한 지 확인한다.

      아니면 값을 queue의 tail로 보낸다

    3. 지정한 값과 동일하면 출력 아니면 값을 제거한다.

  • 풀이

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

    for _ in range(test_case):
        n, m = list(map(int, input().split(' ')))
        queue = list(map(int, input().split(' '))
        queue = [(i, idx) for idx, i in enumerate(queue)]

        count = 0
        
        while True:
            if queue[0][0] == max(queue, key=lambda x : x[0])[0]:
                count += 1
                if queue[0][1] == m:
                    print(count)
                    break
                else:
                    queue.pop(0)
            else:
                queue.append(queue.pop(0))

Comment and share

스택 수열

in Algorithm, Greedy

백준 1874: 문제링크

  • 문제유형 : 스택, 그리디

  • 설명

    1. 스택에 특정 수에 도달할 때까지 push한다.

    2. 스택이 특정 수에 도달하면 pop한다.

    3. 수의 배열을 완성하면 출력하고 불가능하면 NO를 출력한다

  • 풀이

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

    count = 1
    stack = []
    result = []

    for i in range(1, n + 1): # 데이터 개수만큼 반복
        data = int(input())

        while count <= data: # 입력 받은 데이터에 도달할 때 까지 삽입 
            stack.append(count)
            count += 1
            result.append('+')

        if stack[-1] == data: # 스택의 최상위 원소가 데이터와 같을 때 출력
            stack.pop()
            result.append('-')
        else: # 불가능한 경우
            print('NO')
            exit(0)

    print('\n'.join(result)) # 가능한 경우

Comment and share

  • page 1 of 1

Yechan Kim

author.bio


author.job