백준 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


백준 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


백준 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


백준 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

키로거

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

백준 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

백준 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