[WEEK03] 11월 3주차 정글

📖 What I Learned...

3주차 키워드 : 그래프, BFS, DFS, 위상정렬

그래프

• 백준 5639번 이진 검색 트리
  정석적으로 클래스 선언하고 insert 함수 만들어서 제출했는데 시간초과가 났다..^^.. 전위순회의 첫 번째 요소는 항상 root라는 걸 이용하고, 그 root값보다 값이 커지는 분기점이 있다는 것을 이용해 분할정복으로 풀면 무사히 통과할 수 있다.
  자세한 설명은 여기를 참고해보자.

DFS

• 백준 11725 트리의 부모 찾기
  처음엔 union find인가? 했다가 아니란 걸 깨닫고 바로 DFS를 시도했다. 근데 메모리 초과가 나서... 이 분 블로그 보고 해결했다. 각 row마다 연결되어 있는 col만 저장하는 2차원 행렬을 사용하고, 방문 체크 + 부모 노드 저장을 하나의 리스트로 해결한다는 게 중요한 문제였던 것 같다.

• 백준 21606 아침산책
  모든 실내에 대해 탐색을 하면 60점이 나온다..! 실외를 기준으로 인접한 실내 개수를 세는 게 더 빠르다. 그리고 실내 - 실내일 때는 +2를 해주고 나중에 실내-실외-실내의 경우와 실내-실내의 경우를 더한 값을 출력해주면 된다. 나는 이곳을 보고 이해했다.

• 백준 14888 연산자 끼워넣기
  이게 어떻게 DFS지..? 라고 생각했지만 이걸 보고 바로 알게 됐다. 각 연산자의 개수가 0 초과일 때 재귀함수를 돌린다는 것과 함수의 파라미터로 모든 연산자 개수를 넣어주는 것을 생각할 수 있으면 그 다음부터는 쉽게 풀 수 있을 것 같다.

• 백준 2573 빙산

• 백준 2617 구슬 찾기

BFS

• 백준 1916 최소비용 구하기
  다익스트라 알고리즘을 사용하는 전형적인 문제라고 한다. 물론 linear하게 구현하면 안 되고, 우선순위 큐를 사용해 시간복잡도를 줄여야 한다.

• 백준 2665 미로 만들기
  appendleft를 처음 사용해봤던 문제! 흰 방을 먼저 방문해야 하므로 appendleft를 해주고 검은 방을 지날 때는 count += 1에 append만 해주면 쉽게 풀 수 있다.

• 백준 7569 토마토
  3차원 행렬 활용법, 이미 토마토인 곳을 큐에 먼저 다 넣어두는 아이디어, 마지막에 3차원 행렬을 돌면서 0인 곳이 하나라도 있다면 -1을, 아니라면 그 중 max 값을 출력하는 아이디어가 끝이라고 할 수 있다!

• 백준 3055 탈출
  고슴도치 큐가 빌 때까지 모든 물을 BFS 돌리고 (for문으로), 고슴도치 BFS 돌리고 (for문으로) 적절한 조건문을 사용해 비버 굴에 도착했을 때 종료해준다면 생각보다 쉽게 풀 수 있는 문제다. (물론 처음 풀어보면 쉽지 않다는 게 함정이지만)

• 백준 2294 동전 2

위상정렬

• 백준 2637 장난감 조립
  관점을 반대로 하면 풀 수 있는 문제인 것 같다. 원래 위상정렬은 indegree가 0인 것부터 시작하는 걸로 알고 있었지만, 여기에서는 outdegree가 0인 완제품부터 시작해 중간 부품인지, 아닌지에 따라 부품들을 더하거나 곱해서 더해주면 된다.

• 백준 1432 그래프 수정

• 백준 1948 임계경로

What I Realized...

실수를 줄이고 정확도를 높이는 연습을 하자. 그냥 냅다 백준에 제출해보는 것 금지 XXX 코드 짤 때부터 신중하게 짜보자. 안 그러면 디버깅하는 시간이 더 오래 걸릴 수도 있다ㅎ

그리고 지나간 것들에 대해 정리를 하자. 아직 꾸역꾸역 머릿속에 개념들을 집어 넣느라 힘들지만 복습만이 살 길이다. 고딩 때 악착같이 교과서 5회독을 했던 경험을 되살려보자. 그렇게 여러번 보다 보면 언젠간 내 머릿 속에 들어와 있겠지?