Krafton_jungle 5기 8일차 TIL - 알고리즘 문제풀이

백준 문제풀이

 

1629 곱셉

 

귀납법 써서 풀었음

하노이의 탑 생각하면서 푸니깐 실마리가 보였다.

 

2493 탑

탑의 갯수만큼 배열을 선언하고,  스텍에 탑을 쌓은 뒤, 조건에 부합하면 해당 인덱스에 탑의 위치를 넣어주는 방식으로 해결했다.

골드치고는 쉬운편

 

2504 괄호의 값

이건 디버깅을 하며 보면 이해가 편한데 괄호가 닫히기 전까지의 해당 괄호의 값을 곱해준다고 생각하면 편하다.

현재 값의 상태를 저장해두는 tmp와 그렇게 괄호가 닫히면 현재 값을 저장해주는 result를 선언해서 풀었다.

 

 

2630 색종이

전형적인 분할정복 문제.

3일 연속으로 재귀만 지긋지긋하게 봤더니 어렵지 않게 풀었다.

 

3190 뱀

from collections import deque

# 방향 : 우 상 좌 하
direction = deque([[1, 0], [0, 1], [-1, 0], [0, -1]])
# 오른쪽 회전
direction.rotate(-1)
# 왼쪽 회전
direction.rotate(1)

n = int(input())

square = [[0 for _ in range(n)] for _ in range(n)]

apple_count = int(input())
for _ in range(apple_count):
    apple_location = list(map(int, input().split()))
    square[apple_location[1]-1][apple_location[0]-1] = 1

move_list = deque()
move_count = int(input())
for _ in range(move_count):
    change_direction = input().split()
    move_list.append(change_direction)

seconds = 0
snake = deque([[0,0]])
# 게임 시작
while True:
    if len(move_list) != 0 and seconds == int(move_list[0][0]) and move_list[0][1] == "L":
        # 왼쪽 회전
        direction.rotate(1)
        move_list.popleft()
    elif len(move_list) != 0 and seconds == int(move_list[0][0]) and move_list[0][1] == "D":
        # 오른쪽 회전
        direction.rotate(-1)
        move_list.popleft()
    snake.append([snake[-1][0]+direction[0][0], snake[-1][1]+direction[0][1]])
    # 머리가 게임판을 벗어나면
    seconds += 1
    if max(snake[-1]) >= n or min(snake[-1]) < 0:
        break
    # 머리가 몸통에 닿으면
    if snake.count(snake[-1]) != 1:
        break
    if square[snake[-1][0]][snake[-1][1]] != 1:
        snake.popleft()
    if square[snake[-1][0]][snake[-1][1]] == 1:
        square[snake[-1][0]][snake[-1][1]] = 0

print(seconds)

조건 맞추는게 정말 까다로웠던 문제.

오늘 하루중 가장 많은 시간을 쏟아부었다.

 

11279 최대힙

직접 구현해서 하니 시간 초과가 뜨더라...

결국 굴복하고 라이브러리의 힘을 빌렸다.

 

11866 요세푸스 문제

m의 값이 배열의 총량을 넘어서면 그 나머지값을 m으로 다시 지정해주며 풀었다.

 

18258 큐2

너무 쉬운 문제.

파이썬엔 switch문이 없어서 좀 더럽게 구현됐다.

 

 

이 밖에 퀵정렬과 힙정렬을 복습했다.

하루종일 알고리즘 문제만 계속해서 풀었더니 정말 뇌가 녹아내릴것같다.

오늘은 빨리퇴근