[파이썬 알고리즘 심화 스터디] 4주차 정리

4주차

알고리즘

• 10828 스택

  있는 그대로 구현하면 되는 무난한 문제였지만 첫 제출 시 시간초과로 틀렸었기 때문에 시간복잡도 계산하는 것을 더 신경써야겠다. 이 문제는 input()을 sys.stdin.readline() 로 바꿔야 통과가 된다. 실전에서 제대로 잘 짜놓고 이런 차이로 틀리면 많이 속상할 것 같다. 그냥 애매한 문제들은 처음부터 속도가 빠른 sys.stdin.readline()를 사용하는게 마음이 편할 것 같다.

시험

• 2606 바이러스

  항상 1번 컴퓨터에 줄줄이 연결된 컴퓨터들만 감염되고, 이는 1번 컴퓨터를 시작으로 깊이 우선 탐색(dfs) 하는 상황이다. 인접 리스트로 입력받은대로 그래프를 작성하고, stack 자료구조를 활용해 dfs 함수를 만들어서 해결했다.

  BFS로 푼 스터디원의 풀이도 보며 유연하게 풀 수 있는 문제임을 알 수 있었다.

• 1697 숨바꼭질

  x - 1, x + 1 2x 이 세 가지로 계속 분기되는 트리 구조로 이루어져 있다는 것까진 생각해냈지만, 피보나치 수열 문제의 재귀를 떠올리며 DP 문제인줄 알고 삽질을 했다. 하지만 알고보니 그렇게 트리를 옆으로 작성해 내려가다가 가장 먼저 보이는(최단거리) 경우를 찾아내면 되는 BFS 문제였다. 처음엔 알고리즘을 잘 못 짜서 당황했지만, 생각하는 방향을 넓힐 수 있었다.

• 9461 파도반 수열

  그림의 장황함에 움츠러들어서 2번 문제만 잡고 있다가 못 풀었지만, 문제에서 주어진 P(1) ~ P(10)의 결과가 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 임을 알고 유심히 쳐다보니 3번째 전 숫자 + 2번째 전 숫자 = 현재 숫자인 구조였다. 이는 DP의 메모이제이션 방식으로 구현하면 풀 수 있었다.

지금은 시험 문제들의 풀이를 다 기억하기 때문에, 시간이 조금 흐른 뒤 복습할 때 다시 풀어봐야겠다.