손가락놀이터

문제 후기

1. 이전에 프로그래머스에서 푼 순위라는 문제와 비슷하다고 생각했습니다. 아래에 링크를 남기겠습니다.
2. 순위에서 푼 방식대로 모든 사람의 해쉬를 만들고 비교한 값을 통해 갱신하는 방식으로 하니 메모리 초과로 틀렸고 알고리즘을 변경하기로 했습니다.
3. 알고리즘을 생각하다 DFS로 생각했고 문제를 풀었습니다.
4. DFS외에, 위상정렬이라는 것이 있는 것을 알게 됐고 모르는 방식이라 공부를 했습니다. terms.naver.com/entry.nhn?docId=3579618&cid=59086&categoryId=59093를 보고 위상정렬이 어떤 것인지 파악했습니다.
5. 위상 정렬 알고리즘으로 비교에서 큰 적이 없는 값부터 시작해서 DFS 방식으로 하나씩 차례대로 나아가는 방식으로 해결했습니다.

문제링크

from sys import stdin
from _collections import deque

N, M = map(int, stdin.readline().split())

num_dict = {}

for n in range(1,N+1):
    num_dict[n] = []


taller = [0] * (N+1)    # 큰 횟수
queue = deque([])       # 큐 생성


for _ in range(M):
    A, B = map(int, stdin.readline().split())
    # B에 큰 횟수를 저장
    taller[B] += 1
    # A에서 B로 갈 수 있도록 설정(DFS)
    num_dict[A].append(B)

# 비교에서 큰 적이 없는 값
for num in range(1,N+1):
    if taller[num] == 0:
        queue.append(num)
# 결과값
answer = []

# queue에 값이 있는 동안 반복
while queue:
    now = queue.popleft()
    # 결과값에 추가
    answer.append(str(now))

    # 간선 파악
    for i in num_dict[now]:
        # 1이면 queue에 추가
        if taller[i] == 1:
            queue.append(i)
        taller[i] -= 1
print(" ".join(answer))

문제 후기

1. 문제를 보고 이전에 프로그래머스에서 풀어본 풍선 터뜨리기와 비슷한 문제라고 생각을 했습니다. 아래에 링크를 남기겠습니다.
2. 풍선 터뜨리기 처럼 가장 큰 값을 이용해서 풀려고 했으나 반례가 있어서 다른 방법으로 풀어야했습니다.
3. 최악의 경우를 고려해봤을때 단순히 모든 배열을 탐색해도 된다 판단하여 모든 배열을 기준으로 찾기로 했습니다.
4. 각 인덱스 값을 기준으로 왼쪽부분과 오른쪽부분으로 나눠 스택과 이분탐색을 활용하여 스택을 만들었습니다.
5. 문제의 예시를 들면, 1 5 2 1 4 3 4 5 2 1이고 굵은 5가 기준이면 왼쪽 배열은 아래와 같은 순서로 이뤄집니다.
   1. [1]   비어있는 배열에 1 추가
   2. [1,2]   스택의 맨 위의 값 1보다 크므로 스택에 2 추가
   3. [1,2]   스택의 맨 위의 값 2보다 작으므로 이분탐색하여 1->1 교체 (이분탐색하면 idx가 0)
   4. [1,2,4] 스택의 맨 위의 값 2보다 크므로 스택에 4 추가
   5. [1,2,3] 스택의 맨 위의 값 4보다 작으므로 이분탐색하여 4->3 교체 (이분탐색하면 idx가 2)
   6. [1,2,3,4] 스택의 맨 위의 값 3보다 크므로 스택에 4 추가

문제링크

from sys import stdin
from bisect import bisect_left

N = int(stdin.readline())

arr = list(map(int, stdin.readline().split()))

# 만약 배열 크기가 1이면 1출력하고 종료
if len(arr) == 1:
    print("1")
else:

    answer = 0  # 결과값
    # 모든 인덱스 탐색
    for idx in range(len(arr)):
        # 왼쪽 부분과 오른쪽 부분 나눠서 실행
        # 값 부분은 stack으로 숫자 입력
        left_stack, right_stack = [], []
        
        # 왼쪽 부분
        for i in range(idx):
            # 해당값보다 큰 경우 넘어가기
            if arr[i] >= arr[idx]:
                continue
            # 첫번째 값.
            elif left_stack == []:
                left_stack.append(arr[i])
            else:
                # 만약 stack 마지막 값보다 큰 경우는 추가
                if left_stack[-1] < arr[i]:
                    left_stack.append(arr[i])
                # 만약 stack 마지막 값보다 작은 경우
                # 이분 탐색으로 해당 값이 들어갈 위치 찾아서 교체
                else:
                    left_stack[bisect_left(left_stack, arr[i])] = arr[i]

        # 오른쪽 부분
        for i in range(len(arr) - 1, idx,-1):
            # 해당값보다 큰 경우 넘어가기
            if arr[i] >= arr[idx]:
                continue
            # 첫번째 값
            elif right_stack == []:
                right_stack.append(arr[i])
            else:
                # 만약 stack 마지막 값보다 큰 경우는 추가
                if right_stack[-1] < arr[i]:
                    right_stack.append(arr[i])
                # 만약 stack 마지막 값보다 작은 경우
                # 이분 탐색으로 해당 값이 들어갈 위치 찾아서 교체
                else:
                    right_stack[bisect_left(right_stack, arr[i])] = arr[i]

        # 만약 오른쪽 부분이 있는 경우 해당값 추가
        if right_stack:
            right_stack.append(arr[idx])
        # 없는 경우에는 왼쪽 부분에 해당값 추가
        else:
            left_stack.append(arr[idx])
        # answer와 왼쪽, 오른쪽 배열 갯수 비교하여 큰 값 저장
        answer = max(answer, len(left_stack) + len(right_stack))

    print(answer)

문제후기

1. 문제를 보고 이해하는데 오래걸렸습니다. 문제는 R, G, B 값이 하나씩 주어지는데 이때 앞뒤의 집과 달라야한다는 것과 R, G, B를 그리는데 사용되는 페인트의 양이 최소가 되도록 하는 것입니다. 문제를 보고 DP를 보고 풀면 되겠다고 생각했고 이전에 프로그래머스에서 푼 땅따먹기와 같다고 판단했습니다.
2. R, G, B값과 이전까지 더해진 값의 합을 다시 저장합니다. 이때 이전 위치와 같은 경우는 제외합니다.
3. 마지막 줄에서 가장 최소의 값을 찾습니다.

예시 풀이

문제 예시를 DP를 이용하면 최종적으로 아래의 값이 나온다.

프로그래머스에서 비슷한 문제

문제링크

from sys import stdin

# N 개의 줄
N = int(stdin.readline())

# 배열 RGB값 n개
arr = [list(map(int, stdin.readline().split())) for _ in range(N)]

# 초기 설정값
answer = 1e9

# 1번쨰 줄부터 시작
for n in range(1,N):
    for i in range(3):
        # 미니멈 초기값
        minimum = 1e9
        for j in range(3):
            # 이전과 같은 색인 경우 제외
            # 가장 작은 값 찾기
            if i != j and arr[n][i] + arr[n-1][j] < minimum:
                minimum = arr[n][i] + arr[n-1][j]
        # 가장 작은 값 기록
        arr[n][i] = minimum

print(min(arr[-1]))

문제후기

1. 처음 문제를 보고 BFS를 활용해서 문제를 풀려고 했습니다. 최악의 경우 500 * 500을 BFS로 탐색하는 경우이지만 시간제한이 2초로 애매하지만 통과할 수 있다고 생각하고 코드를 작성했습니다.
2. BFS로 제출한 결과 시간초과에서 걸려서 알고리즘이 틀린 것으로 생각하고 알고리즘을 변경했습니다.
3. 다시 생각해낸 알고리즘은 DP로 최대 Heap과 연관시켜 생각했습니다. 대나무가 많은 순서로 Heap 정렬을 해준 이후 pop을 하면서 메모이제이션을 했습니다. 상하좌우의 메모 중 가장 큰 값 + 1로 메모를 갱신했습니다.
4. Heap에 남은 값이 없으면 모든 메모가 끝났으므로 메모 중에서 가장 큰 값을 출력했습니다.

문제링크

from sys import stdin
import heapq
from itertools import chain

# 상하좌우
dy = [-1,0,1,0]
dx = [0,-1,0,1]

# n 개 매트릭스
n = int(stdin.readline())
# 매트릭스 값 입력
matrix = [list(map(int, stdin.readline().split())) for _ in range(n)]
# 메모이제이션
memoization = [[0] * n for _ in range(n)]
# 최대 힙정렬 할 배열
heap = []

# 최대 힙 정렬
for y in range(n):
    for x in range(n):
        # heapq는 최소힙정렬이므로 -1을 곱해서 최대힙정렬로 한다.
        heapq.heappush(heap, (-1 * matrix[y][x], y, x))


# heap에 값이 없을때까지
while heap:
    _, y, x = heapq.heappop(heap)
    chk_arr = []
    # 상하좌우 체크
    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < n and 0 <= nx < n:
            # 만약 상,하,좌,우 값이 더 크다면 해당 메모값 배열에 추가
            if matrix[y][x] < matrix[ny][nx]:
                chk_arr.append(memoization[ny][nx])

    if chk_arr: # 만약 배열에 값이 있으면 가장 큰 값 + 1
        memoization[y][x] = max(chk_arr) + 1
    else: # 배열에 값이 없으면 1
        memoization[y][x] = 1
# 메모 중에서 가장 큰 값 출력
print(max(chain(*memoization)))

문제후기

1. 우선순위 큐를 활용한 문제로 Python은 우선순위 큐를 heap을 활용해서 해결합니다.
2. 절대값이 기준이고 그 다음 기준이 숫자이므로 (절대값, 숫자) 형식으로 heap에 push합니다.
3. 0이 나올 경우 heap에서 pop을 해서 출력합니다.

문제링크

from sys import stdin
import heapq

N = int(stdin.readline())
# 우선순위 큐
heap = []

for n in range(N):
    num = int(stdin.readline())
    if num != 0:
        # 0이 아닌 경우 우선순위 큐에 (절대값, 숫자) 삽입
        heapq.heappush(heap,(abs(num), num))
    # 0인경우
    else:
        # 큐가 비어있으면 0 출력
        if len(heap) == 0:
            print(0)
        else:
            # 큐에 값이 있으면 pop
            print(heapq.heappop(heap)[1])

문제후기

1. 해당 문제는 1부터 시작해서 g와 h를 거친 이후 최종 목적지로 가는 것을 확인하는 문제로 다익스트라를 활용해야겠다고 생각을 했습니다. 시간초과를 피하기 위해서 우선순위 큐도 적용했습니다.
2. 최종 목적지 후보로 도착하기 전에 g와 h 사이의 직선을 거쳐야하므로 1 -> g -> h -> 최종 or 1 -> h -> g -> 최종입니다.
3. 처음 문제를 풀고 제출을 했을때 틀렸는데 문제에서 2번에서 가는 것이 1-> 최종보다 작야한다는 것을 파악하지 못했습니다.

문제링크

from sys import stdin
import heapq

# 방문여부 확인용 초기값
INF = 1e9

# 다익스트라 알고리즘
def dijkstra(start, last):
    # 방문여부
    dp = [INF] * (n+1)
    # 시작 값 0부터 시작
    dp[start] = 0
    heap = []
    # 힙에 (거리값, 정점) push, 우선순위 큐
    heapq.heappush(heap, (dp[start], start))

    # 힙이 있을때까지
    while heap:
        
        weight, now = heapq.heappop(heap)
        for end, dis in node_dict[now]:
            # 조건을 만족하는 값 heap정렬
            if dp[end] > weight + dis:
                dp[end] = weight + dis
                heapq.heappush(heap, (dp[end], end))
    return dp[last]


T = int(stdin.readline())
for _ in range(T):
    n, m, t = map(int, stdin.readline().split())
    s, g, h = map(int, stdin.readline().split())


    # 노드 hash화
    node_dict = {}

    for _ in range(m):
        a, b, d = map(int, stdin.readline().split())
        node_dict[a] = node_dict.get(a,[]) + [(b,d)]
        node_dict[b] = node_dict.get(b, []) + [(a, d)]
    
    # 1번 시작 -> g -> h -> 최종
    # 2번 시작 -> h -> g -> 최종
    answer1, answer2 = 0, 0

    answer1 = dijkstra(s, g) + dijkstra(g, h)
    answer2 = dijkstra(s, h) + dijkstra(h, g)

    candidate = []
    minimum = INF
    for _ in range(t):
        node = int(stdin.readline())
        answer = min(answer1 + dijkstra(h, node), answer2 + dijkstra(g, node))
        chk_answer = dijkstra(s, node)

        if chk_answer >= answer:
            heapq.heappush(candidate, node)


    while candidate:
        print(heapq.heappop(candidate), end="")
        if candidate:
            print(" ", end="")
        else:
            print("")

문제후기

1. 해당 조건(N은 10^5보다 작거나 같은 자연수이다. 둘째 줄에 k가 주어진다. k는 min(10^9, N^2)보다 작거나 같은 자연수이다)을 확인하고 완전탐색을 하게되면 시간초과가 발생할 것을 예상했습니다. 알고리즘은 이분탐색(logN)을 활용해야겠다고 생각하게 됐습니다
2. 배열에 있는 값을 어떻게 하면 이분탐색으로 할 수 있을지 고민하는데 오래걸렸습니다. 같이 문제푸는 사람과 이야기를 하다가 몫과 나머지를 활용하면 어떻게 되지 않을까라는 말이 나와 몫을 활용하기 시작했습니다.
3. 몫을 활용해서 해당 숫자가 정답을 만족하게 되는 경우 마지막값(end)을 땡기고 만족하지 않는 경우 시작값(start)을 미루는 방식으로 진행했습니다.

자세한 예시를 들어보면

문제에서 제시한 예시 3으로 보여드리겠습니다. 3을 2차배열로 만들게 되면 아래와 같아집니다.

위의 도표를 봤을때 찾는 방식은 행의 첫번째 값을 기준으로 나누는 것입니다. 중간값은 시작(1), 마지막(9)이므로 5입니다.

1.  첫 번째 줄은 1번 값이 1. 그러므로 중간값을 1로 나누면 5//1 = 5이므로 N 3보다 크므로 5보다 작은값은 3개.
2.  두 번째 줄은 1번 값이 2. 그러므로 중간값을 2로 나누면 5//2 = 2이므로 N 3보다 작으므로 5보다 작은값은 2개.
3.  세 번째 줄은 1번 값이 3. 그러므로 중간값을 3로 나누면 5//3 = 1이므로 N 3보다 작으므로 5보다 작은값은 1개.
4. 전체 총 6개가 5보다 작습니다.
5. 시작값과 마지막값을 조정하면서 위의 과정을 반복해 K번째 값을 찾으면 됩니다.

문제링크

from sys import stdin

# Input 값
N = int(stdin.readline())
K = int(stdin.readline())

# 이분탐색 시작값과 마지막 값.
start, end = 1, N ** 2
answer = 0  # 정답값

# 이분탐색 실행.
while start <= end:
    middle = (start + end) // 2
    count = 0
    # 해당 값이 N이상으로 나눠지는지, N개인지, 그보다 적은지 판단
    # middle보다 작은 값 갯수 카운팅
    for i in range(1, N+1):
        count += min(middle//i, N)
    
    # 만약 갯수가 K보다 많거나 작으면 end값 땡겨서 범위 축소
    if count >= K:
        end = middle - 1
        answer = middle
    # 만약 갯수가 K보다 적으면 start값 땡겨서 범위 축소
    else:
        start = middle + 1
print(answer)
print(start)

문제후기

1. 문제를 보고 DP를 활용하는 문제라고 판단했습니다.
2. 계산을 편하게 하기 위해서 좌표와 메트릭스의 크기를 동일하게 하고 계산했습니다.
3. 물 웅덩이가 없는 경우 해당 위치까지 똑같은 크기만큼 이동했기 때문에 비교할 필요 없이 더하면 됩니다.
4. 물 웅덩이가 있는 경우 값을 0으로 만들어 제외했습니다.

문제링크

def solution(m, n, puddles):

    # 매트릭스 제작.
    matrix = [[0] * (m + 1) for _ in range(n + 1)]

    # 출발, 집 좌표
    matrix[1][1] = 1

    # DP 시작
    for y in range(1, n + 1):
        for x in range(1, m + 1):
            # 출발 값
            if y == 1 and x == 1:
                continue
            # 웅덩이가 있는 경우 패쓰
            if [x, y] in puddles:
                matrix[y][x] = 0
            else:
                # 해당 위치 값은 이전값 2개의 합.
                matrix[y][x] = matrix[y - 1][x] + matrix[y][x - 1]

    return matrix[n][m] % 1000000007