패스트캠퍼스 챌린지 49일차

류호석배 코딩테스트 3회

 

 

문제 1 : 빌런 호석 

 • 출제 의도

  - 올바른 접근 방법을 떠올리는가?

  - 시간 & 공간 복잡도는 제대로 계산 하였는가

  - 문제를 편하게 구현하였는가

 

 • 총 정리 

  - diff_one 함수 구현

  - 이를 이용한 diff 함수 구현

  - Y를 1부터 N까지 바꿔보면서 변환 횟수가 P이하인지 확인

  - 총 시간 복잡도는 O(N * K) 이다

 

 

---

문제 2 : 정보 상인 호석 

 • 출제 의도

  - 문제가 요구하는 상황을 이해 했는가?

  - 문자열을 잘 다루는가?

  - 필요한 연산을 정의할 줄 아는가?

  - 자료구조를 나열하고 시간 복잡도를 따져서 최선의 자료구조를 선택할 수 있는가?

 

 • 접근 방법

  - 먼저 고릴라의 이름을 어떻게 다룰 것인가?

  1.  문자열 그 자체를 이용하는 경우

  2. 숫자로 변경해서 이용하는 경우

  -> 익숙한  것으로 선택하여 진행한다.

 

 • 필요한 연산 정의

   1. 고릴라 Gx 가 {C1,C2,Ck}의 정보를 획득한다 -> O(k)

   2. 고릴라 Gx가 가진 정보중 가장 비싼 b개를 구매한다. -> max를 찾기 & max를 삭제하기 = O(N) => O(N*b)

 

 • 총 정리

  - 고릴라 마다 가지고 있는 정보의 가치들을 자료구조(Max Heap)에 담아두고 있다.

  - 총 시간은 정보를 삽입하고 삭제하는 과정에서 소모되는 시간이다

  - 정보가 많아야 100만개가 삽입 & 삭제 되기 때문에 O(100만 log 100만)에 비례하는 시간이 걸리고 시간은 충분하다

---

문제 3 : 트리 디자이너 호석

 • 출제 의도

  - Rooted Tree 구조에 익숙한가?

  - 완전 탐색에서 동적 프로그래밍으로의 연결을 지을 수 있는가?

  - 동적 프로그래밍 풀이를 스스로 수행할 수 있는가?  

 

 • 생각의 흐름 1 - 정답의 최대치

  - 가능한 경우가 가장 많은 입력은?

  - 정점 10만개가 일렬로 존재하고, 모두 0인 경우 => 정점을 어떻게 선택해도 조건을 만족하므로 2^10000 가지 가능

 

 • 생각의 흐름 2 - 동적 프로그래밍 

  - 모든 경우를 하나씩 찾으면 당연히 "시간 초과"를 받을것을 예상할 수 있다   

    => 해당 경우 동적 프로그램이 접근 시도

 

 • 생각의 흐름 3 - 문제 정의 

   - Dy[i][k] = i 번 정점을 root로 하는 subtree에서, 조건을 만족하게 선택하면서 마지막 숫자가 k인 경우

    정답 : Dy[1][0] + ... Dy[1][9]

    초기화 : Dy[i][a[i]] = 1 (i번 정점만 선택하는 경우)

 

 • 생각의 흐름 4 - 점화식 

   - Dy[i][...] 을 계산하기 전에 i의 모든 자식 정점에 대해 문제를 이미 해결했다고 하자

    1. i 번 정점을 선택하는 경우

    2. i 번 정점을 선택하지 않는 경우

   두가지를 모두 고려해서 Dy[i][...]에 반영하면 된다.

 

 • 총 정리

  - Rooted Tree에서의 Dynamic Programming

  - 시간 복잡도는 모든 정점을 한 번씩 보기 때문에 O(N)이다

  

   

49일차 인증

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]