문제 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 재정의 트리가 구성되어 있을 때, leaf_node를 세리는 문제이다. 특정 노드 한 개를 삭제하였을 때, 남는 leaf_node의 수를 구하면 된다. leaf_node를 어떻게 다룰지가 핵심인 문제이다. 재귀적으로 leaf_node 조합하기 트리는 재귀적 구조로 구성되어 응용하기 좋다. 특정 노드에서, 자식들의 가진 leaf_node를 더하면 총 leaf를 구할 수 있다. 이렇게 구현하면 한 가지 문제가 생긴다. A라는 노드에서 자식 B 하나를 가진..
문제 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net DDR을 하는데, 에너지를 최소한으로 쓰고 게임을 끝내는 방법에 대한 단순한 문제이다. 재정의 greedy 한가? (탐욕적 선택 속성을 가지는가?) 앞선 선택이 뒤의 선택에 영향을 미치지 않는다면, greedy하게 풀 수 있을 것이다. 현재의 발을 옮겼다가, 뒤 이어 이전 발의 위치만 무한으로 나온다면 손해를 보게 된다. -> greedy하게 풀 수 없다. 완전 탐색 결국 모든 경우의 수를 확인해야 하므로, 완전 탐색을 사..
문제 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 www.acmicpc.net 재정의 두 가지 제약 조건이 존재한다. 정해진 투자액수만큼 투자 한다. 한 기업에는 한 번만 투자할 수 있다. 금액의 조합을 정해야 하고, 기업의 조합도 정해야 한다. 완전 탐색을 활용한다. 비 효율적인 상태공간 정의 완전 탐색을 해야하는 문제이다. 상태 공간을 기업의 개수, 남은 금액으로 단순하게 정의 했다. 그렇게 되면 다음과 같이 코드가 구성 된다. 다음 코드의 문제점이 무엇인지 생각 해 보자... def get_max_profit() -> List[int]:..
1. 기존 Python 코드 해야할 기능은 다음과 같다. 2차원 배열로 데이터 저장하기 2차원 배열 정렬하기 2차원 배열 순회하기 2. Java 변환 시도 3. 다른 사람의 Java 코드 빠른 입력 일반 Scanner가 아니라, InputStreamReader -> Bufferedreader로 해야 빠른 것 같다. readLine으로 한 줄 입력을 받고, 바로 parse하거나 또는 StringTokenizer로 문자열을 공백기준으로 split 하고 각각 parse한다. Comparable을 implements하는 클래스 그냥 무지성으로 2차원 배열을 만들었었다. [x, y] 좌표를 가지는 배열 하나, 이 배열들의 배열로 2차원으로 말이다. Java는 oop에 충실한 언어인 만큼, [x, y]를 배열로 하..
