백준 && 프로그래머스 문제 풀이 정리!

다시 볼 만한 문제 정리!

1325 효율적인 해킹

완전히 얕봤다가 생각보다 너무 헤맸다.

알고리즘

'각 노드' 마다 BFS 를 돌아서 간선 갯수를 세면 된다. 시간이 5초 이므로 이러한 풀이가 가능하다.

프로그래머스 - 야근 지수

알고리즘

이 문제는 단순 구현 문제이지만 heapq 를 쓰면 조금 더 간단하게 풀 수 있다.

16120 PPAP

알고리즘

이 문제는 Stack 을 사용한다는 걸 알면서도 풀지 못했는데, `지나간 PPAP 를 모아두는 스택` ,`검사(PPAP인지)를 위한 스택`, `남은 PPAP String` 이렇게 2개의 스택을 쓰고 있었다. 굳이 이렇게 하지 않고 `PPAP String 을 계속 모아두다가, PPAP[-4:] 부터 PPAP 인지` 검사하면 되는 문제였다.

1613 역사

알고리즘

매번 트리와 유사해 보이는 문제는 다 union-find 로 풀려고 했고, 플로이드 와샬을 이런식으로 사용할 수 있다고 생각을 못했던 문제. 플로이드 와샬은 최단 경로를 구하기 위한, 다익스트라를 사실상 n번 수행하는 알고리즘이라고 생각했는데 핵심은 '거쳐가는 노드' 였다. 거쳐가는 노드를 통해 서로 이어져있는지를 확인할 수 있다.

28707 배열 정렬

알고리즘

다익스트라 문제는 늘, 고정된 노드들로만 구성되어 있는 문제였다. 근데 이 문제는 동적으로 노드들을 추가시키면서 다익스트라를 돌려야한다.