22.05.18. 풀었던 문제들

1. 모두 0으로 만들기

leaf부터 탐색하면 최적값이 나올 거라 생각해서 unvisited edge가 1인 node들부터 차곡차곡 방문하고, 해당 node와 adjacent한 node들의 edge 개수를 갱신하려 했는데 이러면 너무 복잡하다. 그럴 필요 없이, 트리 후위 순회를 돌려버리면 leaf부터 방문하니 상관없고, 해당 문제의 경우 'tree임이 보장되어 있으므로 어느 점을 root로 잡든 leaf는 생긴다...'

​

​

2. N으로 표현

간단한 DP였는데 몇 가지 때문에 헷갈렸다.

1) 연산 끝에 숫자를 붙이지 못한다. 무슨 말이냐면 1(1 + 1)1로 121을 만들지 못한다. 숫자를 연속해서 만들 수 있는 것은 1, 11, 111, ...이다.

2) c를 만들 때, a + b도 되지만 b + a도 c를 만들 수 있으며, +, *는 교환법칙이 성립하지만 -, /는 교환법칙이 성립하지 않기 때문에 이에 대한 처리를 해 주어야 했다.(길이 8짜리를 구한다면 1짜리 + 7짜리, 2짜리 + 6짜리, ...를 했어야 했다)

 

​

내일은 순위, 다단계 칫솔 판매, 금은 운반하기 적어도 이 3문제는 풀고 싶다. 그러면 카카오 문제만 남고, 인턴십 - 블라인드 채용 - 카카오코드 본선 순으로 문제를 풀면 되지 않을까? 다 풀면 아마 28일쯤 될 것이니 그때 알고리즘 개념들을 조금 정리하고, 공부를 좀 해야겠다.(특히 union-find, graph쪽 topological sort 등등) 그 다음은 lv 4다. lv4까지 끝나면 백준으로 넘어가서 단계별 풀기 전부 다 풀고 부족하다고 느끼는 DP쪽을 좀 조져봐야 겠다.