개발하지연

문제 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다. 각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 기록 (greedy 1일차) 내가 세운 규칙이 백퍼센트 맞다고 생각하고 의심..

문제 춘향이는 편의점 카운터에서 일한다. 손님이 2원짜리와 5원짜리로만 거스름돈을 달라고 한다. 2원짜리 동전과 5원짜리 동전은 무한정 많이 가지고 있다. 동전의 개수가 최소가 되도록 거슬러 주어야 한다. 거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지 알려주는 프로그램을 작성하시오. 예를 들어, 거스름돈이 15원이면 5원짜리 3개를, 거스름돈이 14원이면 5원짜리 2개와 2원짜리 2개로 총 4개를, 거스름돈이 13원이면 5원짜리 1개와 2원짜리 4개로 총 5개를 주어야 동전의 개수가 최소가 된다. 기록 (greedy 1일차) 트리 끝내고 그리디 알고리즘 시작했다. 아직 어떤 알고리즘인지 감은 잘 안오지만 그 상황에서 최적의 선택을 하는 알고리즘? 이라는 것만 알고 무작정 문제 풀어보려고한다. 내맘..

문제 시청 공무원 마이크로는 과장으로부터 시에 있는 나무의 기둥의 길이와 가장 긴 가지의 길이를 파악하라는 업무 지시를 받았다. 마이크로는 ICPC Sinchon Winter Algorithm Camp에서 배운 트리 자료 구조를 이용하면 이 작업을 좀 더 수월하게 할 수 있으리라 판단했다. 마이크로는 트리의 기둥과 가지를 분류하기 위해 기가 노드를 추가로 정의하였다. 기가 노드는 루트 노드에서 순회를 시작했을 때, 처음으로 자식 노드가 2개 이상인 노드다. 기둥-가지를 줄여 기가 노드라 이름 붙였다. 위 그림에서 기가 노드는 4번 노드다. 단, 위 그림과 같이 리프 노드가 단 1개인 경우 리프 노드가 동시에 기가 노드가 된다. 또한, 위 그림과 같이 루트 노드가 동시에 기가 노드인 경우도 가능하다. 트리..

문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 기록 (트리 5일차) 시간초과는 진짜 언제봐도 적응이 안된다. 아무리봐도 시간 줄일데가 없다고 생각했는데!! 그전에 비슷한 문제 풀어서 진짜 똑같이 풀었는데 시간초과나서 당황했다. 찾아보니까 inorder배열에서 root 인덱스 찾아내는 부분이 문제였다. 그래서 처음에 인덱스 미리 저장해놓고 바로바로 인덱스 찾을 수 있도록 변경했다. 내가 생각한 키포인트는 입력으로 주어진 inorder, postorder에서 각 순서의 특징을 이용하여 왼쪽/오른쪽/루트 분리하여 postorder순서로 출력될 수 있게 하는 것! 시..