log 2021-07-20
job
데브코스 면접
blog
요즘은 패턴상 마무리 커밋을 저녁에 하기가 어려우므로 미리 할 필요가 있다.
sport
kakao 2021 blind - 매출 하락 최소화
풀이 과정 익히는 것을 목표로, 2시간 잡고 시도하고 안되면 답보기
트리에서 팀장 : 중간 노드 팀원 : 말단 노드 가 된다. 팀은 팀장+팀원 즉 특정 부모에 대해 해당 부모와 그 자식들의 집합
- 모든 팀은 최소 1명 이상의 직원 참석
- 즉 모든 부모에 대해 팀원을 선택해야 한다.
- 그러려면 각 부모가 부모가 아닌 자식 노드들을 선택하면 될 듯?
- 아니다, 부모 노드는 그저 팀이 두 가지의 선택을 할 수 있는 것이다.
- 탐욕법으로 가능할까? 일단 말단 노드에 대해서는 부모보다 낮다면 무조건 그 최소 노드를 선택하는게 나을 듯하다.
- 그러나, 부모 노드가 최소값을 가질 경우, 그 부모를 선택하고, 그 부모가 팀원인 팀의 다른 말단 노드를 선택하거나, 덜 낮은 말단 녿를 선택하고 그 부모를 그 팀의 말단 노드로서 선택하는 두 가지 방법이 있다.
- 이런 선택이 연쇄적으로 일어난다.
- 즉 반복된 구조로 일어나는 것이다. 이 문제에서 최적 부분 구조는 무엇일까?
- 어떤 트리의 최소매출액 값이 어떻게 결정되나?
- 아 잘못이해함. 부모 노드는 자식 노드인 팀에도 포함인 것으로 즉 한 명이 두 팀분으로 계산될 수 있다.
- 일단, 어떤 노드의 선택 여부가,
- 엣지케이스가 무엇이 있을까?
- 더이상 하위에 부모 노드가 없을때
- 딱 3층 트리에 대해 생각해보자
- 가운데 부모 노드가 어떤 위노드+아래노드 합보다도 작다면 그 부모 노드를 고르는 것이 이득이다.
- 그렇지 않다면 그렇지 않게 하는 두 노드를 위,아래트리에서 각각 고른다.
- 그러나, 다른 노드가 위에 더 있어서 위쪽 트리의 부모 노드를 결국 골라야 해서 달라질 수도 있다.
- 즉 가장 작은 케이스가 위 트리와 연관을 가진다.
- 어떤 함수에 대해, 부모 노드를 넣으면 각 하위 노드들의 선택여부에 따른 충족 팀과 매출액을 리턴? 부분 구조를 어떻게 설계?
- 일단 1단트리 말단밖에 없다고 가정하면,
- 무조건 모든 노드 중 최소를 고른다. 그런데, 이것도 그 위의 상황에 따라 부모를 골라야 할 수도 있다.
- 2단 트리가 되면…
- 아니 일단, 위랑 계속 연관이 되니까 다음과 같은 어떤 관계가 있다.
- f(p) = af(2p) @ bf(2p+1)…아니 모든 자식들 C에 대해
- f(p) = @ for c in C, f(c) …
- 일단, 한 팀에서 여러 말단 노드를 택할 일이 있나? 절대 없다.
- 그렇다면, 말단 노드들은 그냥 그 중 최소의 노드 하나만 택하면 된다.
- 그러면 트리는 자식이 많아야 두개 존재하는 이진 트리가 된다.
- dp로 해가지고, 말단 택하는 경우와 부모 택하는 경우들 두 가지를 재귀적으로 모두 고려하도록 탐색하면 될 듯한데.. 뭐라 표현을 못하겠다 정확히는.
- 참석 직원들의 매출액의 합을 최소로
- 모든 참여 원소들의 매출액 합을 최소로
결국 구현 실패. 내일 좀더 시도해보고 안되면 해설 따라구현해야할듯.
Comments