크래프톤 정글 week01, day10 - 알고리즘 문제

어제에 이어서 알고리즘 문제만 하루종일 풀었다.

​

나무 자르기

# # 입력 : 
# # 나무 개수값 n, 상근이가 가져가고 싶은 길이값 m, 나무 길이들
# # 출력 :
# # 절단기의 설정 값
# import sys

# namu = list(map(int, sys.stdin.readline().split()))
# namu_length = list(map(int, sys.stdin.readline().split()))
# namu_length.sort(reverse=True)

# # 자른 길이
# # 톱 높이 나무가 제일 큰게 20이면 19로 설정
# saw_height = namu_length[0] - 1

# # 톱 높이를 제일 큰 나무의 -1부터 시작해서 1씩 감소
# for saw_count in range(saw_height, 0, -1):
#     # 매번 돌 때마다 자른 길이를 초기화
#     cut_meter = 0
#     print('톱 높이', saw_height)
#     # 나무 목록에서 톱의 높이보다 긴 나무는 잘라서 자른 길이에 누적
#     for namu_height in namu_length:
#         if namu_height <= saw_height:
#             print('안잘린나무 길이', namu_height)
#             continue
#         else:
#             cut_meter += namu_height - saw_height
#             print('잘린나무 길이', namu_height)
    
#     # 자른 길이가 가져가고자 하는 값과 같으면 for문 탈출
#     if cut_meter == namu[1]:
#         saw_height = saw_count
#         break
    
#     saw_height -= 1
#     print('자른 길이', cut_meter)
# print(saw_height)

import sys

n, m = list(map(int, sys.stdin.readline().split()))
tree_heights = list(map(int, sys.stdin.readline().split()))

start, end = 1, max(tree_heights)

# 검색 트리의 최대를 가장 긴 나무로 잡기
while start <= end:
    # 톱으로 자를 위치를 중간으로 잡기
    mid = (start + end) // 2
    # 나무들의 길이에서 중간을 뺸 값이
    # 0보다 크면 뺸 값을 cut_tree에 넣기
    # 0보다 작으면 넣지 말기
    cut_tree = 0
    for height in tree_heights:
        if height - mid > 0:
            cut_tree += height - mid
        else:
            cut_tree += 0
    
    # 만약 자르는 값이 자른 나무보다 적으면 start값을 중간 위로 올리기 
    if cut_tree >= m:
        start = mid + 1
    # 자르는 값이 자른 나무보다 많으면 start값을 중간 밑으로 내리기
    else:
        end = mid - 1

print(end)

 

상단의 주석처리된 쪽은 기존에 풀었던 방식인데 제일 긴 나무길이에 맞춰서 1줄씩 자르면서 합을 맞추는 방식이였다. 작동은 제대로 되지만 백준문제 특성상 최대값으로 테스트를 하기때문에 당연히 시간 초과가 떴다.

 

이분 탐색을 이용해 푸는 방식이였지만, 어떻게 적용해야할지 이해를 못해서 열심히 지피티의 힘을 빌려 학습했다.

​

색종이 만들기

# n 이 2의7승 중에 입력되고, n x n 의 색종이가 있는데
# 색종이가 다 차있지 않으면 반절로 쪼개면서 채워지는 색종이가 있을때까지 쪼개기

# n x n 값 받기
N = int(input())
# n x n의 종이 값을 받아오기
paper = [list(map(int, input().split())) for _ in range(N)]
# 흰색과 파란색 수를 초기화
white = 0
blue = 0

def cut(x, y, n):
    # 재귀할때마다 초기화되면 안되기 때문에 흰색, 파란색을 전역변수로 가져온다.
    global blue, white
    # 이차원배열에 입력된 x와 y값 넣기(0,0) 부터 시작
    check = paper[x][y]
    # [0][0]부터 [n-1][n-1]까지 완전탐색 하면서
    for i in range(x, x + n):
        for j in range(y, y + n):
            # check값의 색[0][0]이랑 현재 색종이의 색이랑 다르면 재귀를 시작
            # 1/4로 쪼개기 때문에 재귀를 4번 사용해 4분할을 다 검색
            if check != paper[i][j]: 
                cut(x, y, n//2)
                cut(x, y + n//2, n//2)
                cut(x + n//2, y, n//2)
                cut(x + n//2, y + n//2, n//2)
                return

    # 체크값이 0이면 흰색을 1 누적하고, 1이면 파란색을 1 누적한다
    if check == 0: 
        white += 1
        return
    else: 
        blue += 1
        return
# check값을 위해 첫 x, y값을 0,0으로 설정하고 입력값을 길이로 받기 
cut(0, 0, N)
print(white)
print(blue)

 

볼 때마다 재귀는 진짜 이해를 못해서 알고리즘을 사용 못할 것 같다 하노이탑 열심히 풀면서 적응된 줄 알았는데 문제 바뀌니까 바로 못 풀어버리기

 

n값이 2의 거듭제곱 중에 입력되므로 만약 기존 n x n에 다른 색이 있으면 없다고 가정하고 4등분으로 쪼개서 그 안에서 하나씩 다시 체크한다.

 

완전탐색에 값이 다르다 인식하면 바로 종료하고 다음 재귀로 넘어가는 백트래킹 방식을 사용하는 것 같다.

​

스택

# 스택 기능 구현 문제
# 출력할 명령어의 개수를 입력
import sys
n = int(sys.stdin.readline())
stack = []

# 각 단어가 입력될 때마다 if문 타서 실행
for _ in range(n):
    # 입력이 push일 경우는 값이랑 쪼개져서 인덱스 2개로 담기고
    # 그 외의 입력은 1개의 인덱스만 담겨 [0]번째에만 데이터가 있음음
    order = sys.stdin.readline().split()
    # push x일 때 정수 x를 배열에 담는다.
    if order[0] == 'push':
        stack.append(order[1])
    # pop일 때 배열에 가장 뒤에 값을 삭제하고 값을 출력한다
    elif order[0] == 'pop':
        if len(stack) == 0:
            print('-1')
        else:
            print(stack[-1]) 
            del stack[-1] 
    # size일 때 배열에 있는 인덱스의 개수를 출력
    elif order[0] == 'size':
        print(len(stack))
    # empty일 때 배열이 인덱스가 없으면 1, 있으면 0을 출력한다
    elif order[0] == 'empty':
        if len(stack) == 0:
            print('1')
        else:
            print('0')
    # top일 때 배열의 가장 뒤의 값을 출력하고 없으면 -1을 출력
    elif order[0] == 'top':
        if len(stack) == 0:
            print('-1')
        else:
            print(stack[-1])

 

 

이론으로만 본 스택을 직접 풀게 되었다. 스택의 각 기능들을 작성해 구현하는 코드였는데 LIFO방식을 생각해 삭제할 때 인덱스의 마지막 배열에 접근해 삭제하는 것이라 괜찮았던 것 같다.

 

학습하며 배운건데 배열[-1]은 자동으로 마지막 인덱스를 향한다고 하더라

 

탑

# n개의 탑은 각각 왼쪽에 신호를 쏘는데 왼쪽에 본인보다 큰 탑에만 수신이 가능하다
# 각 탑마다 누가 신호를 받는지 출력
import sys

# 탑의 개수 n, n개만큼 리스트로 탑을 받는다
n = int(sys.stdin.readline())
tower = list(map(int, sys.stdin.readline().split()))
# stack배열은 신호를   탑이 신호를 받을 탑이 있는지 확인하는 result
stack = []
result = [0] * n

# 
for i in range(n):
    # 스택에 값이 있고 가장 마지막에 있는 tower가 i번째 값보다 낮을 때
    while stack and tower[stack[-1]] < tower[i]:
        # 맨 위의 값을 제거
        stack.pop()
    # 스택에 값이 있으면 i번째 result 값을 stack마지막값 + 1로 변경한다
    if stack:
        result[i] = stack[-1] + 1
    # stack리스트에 result를 추가
    stack.append(i)

# split()과 다르게 여러 출력값을 붙여서 출력
print(' '.join(map(str, result)))

 

이 문제는 어떻게 작성해야하는진 바로 이해했는데 아무리 생각해도 로직이 안짜여져서 지피티한테 열심히 물어봤다.

 

탑은 각각 왼쪽으로 신호를 쏘며 자기보다 큰 탑에만 수신이 가능하다고 하니 스택의 성질을 이용해 값을 넣고 비교해서 더 작으면 그 값을 그대로 제거하는 방식으로 작성했다.

​

요세푸스 문제

import sys

# n[0] = 인원 수, n[1] = 제거할 간격
n = list(map(int, sys.stdin.readline().split()))
arr = []
# 인덱스 시작이 1이기 때문에 제거될 위치에서 1 깎아주기
cnt = n[1] - 1
result = []

# [1, 2, 3, 4, 5, 6, 7]
for i in range(1, n[0]+1):
    arr.append(i)

# 배열을 무한으로 돌며 배열의 길이가 cnt보다 작아지면 cnt의 나머지값을 넣고 다시 진행
while arr:
    if cnt >= len(arr):
        cnt = cnt % len(arr)

    # result에 cnt값 자리의 값을 삭제 후 result로 이동
    result.append(arr.pop(cnt))
    cnt += n[1]-1

jjin_result = '<' + ", ".join(map(str, result)) + '>'
print(jjin_result)

 

이 문제는 처음에 이해를 잘못해서 n의 배수로 하면 금방 하겠네 하고 풀었다가 에러 잔뜩 나고 다시 이해했다.

 

n번째 제거를 하면 그 만큼 인덱스를 줄여야하고, 마지막 인덱스로 오면 다시 영점으로 돌아가 반복하는 것이기 때문에 단계 조절이 필요했다.

 

시작이 1부터 시작하기 때문에 기존 n값에서 -1을 해줘 맞춰주고, 인덱스가 마지막일 때 이동 횟수가 남으면 길이값으로 나머지를 구해 그만큼 이동 값에 넣었다

​

큐 2

import sys

n = int(sys.stdin.readline())
queue = []
cnt = 0

for i in range(n):
    order = list(map(str, sys.stdin.readline().split()))

    if order[0] == 'push':
        queue.append(order[1])

    if order[0] == 'pop':
        if len(queue)-cnt == 0:
            print('-1')
        else:
            print(queue[cnt])
            cnt += 1

    if order[0] == 'size':
        print(len(queue)-cnt)

    if order[0] == 'empty':
        if len(queue)-cnt == 0:
            print('1')
        else:
            print('0')

    if order[0] == 'front':
        if len(queue)-cnt == 0:
            print('-1')
        else:
            print(queue[cnt])

    if order[0] == 'back':
        if len(queue)-cnt == 0:
            print('-1')
        else:
            print(queue[len(queue)-1])

 

스택과 같이 큐의 기능들을 구현해보는 문제였기 때문에 재밌게 풀었는데 역시 백준 문제가 효율 중시의 거지같은 문제들이 많아서 시간 초과가 났다

 

원인은 pop 구현에 있었다. 큐는 FIFO 방식으로 먼저 넣은게 나가기 때문에 앞 인덱스를 삭제하면 그만큼 남은 배열을 땡겨야하는데 백준의 최대값이 10만이다. pop할때마다 남은 9999개를 땡겨와야하기 때문에 시간 초과가 발생한 것 같다.

 

해결은 배열을 속여버렸다. 구글링해서 찾았는데, 삭제하는게 아니라 현재 보이는 인덱스 배열을 기존 인덱스는 그대로 있고 체크하는 위치만 삭제 횟수만큼 뒤로 밀어버렸다. 삭제되고 땡기는 과정이 없어지니까 자연스럽게 시간 안에 되더라. 문제가 정말 이상하다.

​

최대 힙

import heapq
import sys

# 총 몇개를 입력받을지 n값에 담기
n = int(sys.stdin.readline())
# 리스트값을 담을 배열
heap = []

# n만큼 반복하면서 price 변수에 입력값 하나씩 집어넣기
for i in range(n):
    price = int(sys.stdin.readline())
    # 입력값이 0일 때 heap배열의 정수가 없으면 0을 출력
    if price == 0:
        if len(heap) == 0:
            print(0)
        # 그게 아니라면 힙에서 원소를 하나 제거하고 원래 값을 출력
        else:
            print(heapq.heappop(heap)[1])
    # 입력값이 0이 아니라면 [-x, x]방식으로 값을 넣는다
    # 힙 라이브러리는 최소 힙을 구현하기 때문에 가장 작은 값이 위치해야 하는데
    # 최대 힙을 구해야 하는 문제기 떄문에 -를 줘서 작은 값이 우선순위를 가지게 되어
    # x보다 -x가 먼저 위치하게 된다.
    else:
        heapq.heappush(heap, [-price, price])

 

이건 본인이 힙이라는 개념을 잘 몰랐어서 그냥 해설을 보고 학습했다.

 

힙은 트리 형식으로 한 노드씩 내려가며 타는 형식인 것 같은데, 2주차에 배울 개념이 벌써 나와 예습느낌인가 했다.

 

기존의 힙은 최소를 구하는 방식이기 때문에 원래는 최소값부터 찾아야하는데, 알고리즘 문제가 최대 힙을 구하는 문제여서 heapq 라이브러리를 이용해 최소값을 구하는 코드에 -를 붙여 우선순위를 바꾸었다.

​

일주일간 푼다고 열심히 풀었는데 이제껏 푼 건 '하' 문제와 가끔씩 보이는 '중' 문제일뿐, '상' 문제는 예제 이해도 못했을 뿐더러 코드를 봐도 구현로직을 모르겠다..

'상' 문제 풀때까지 열심히 달려봐야겠다

​

학습시간 : 10 ~ 26시