Jonyo Programming

[BOJ1946 리뷰] 오랜만에 푼 그리디 문제이다. 문제 조건을 잘 풀어보면 다음과 같다. 신입사원으로 선발 되려면 다른 지원자보다 최소한 점수 하나가 더 높아야 한다. 즉, 점수가 둘다 낮으면 선발될 수 없다. 문제를 해결하기 위해서 먼저 첫번째 기준으로 정렬을 하자. (두번째 기준으로 정렬을 해도 상관이 없다.) 정렬이 되면 서류성적순으로 1등부터 꼴등까지 쭉 정렬이 될 것이다. 이제 여기서 문제의 핵심을 잘 생각해보면 된다. 신입사원으로 선발이 되기 위해서는 최소한 점수 하나가 더 높아야 한다. 지금은 서류성적 순으로 정렬이 되어있기 때문에, 그 밑에 있는 사원들은 일단 서류성적은 첫번째 지원자보다 무조건 낮을 수 밖에 없다. 그렇기에 이 사람이 선발이 되기 위해서는 면접 점수가 무조건 높아야 한..

[BOJ 1202(G2) 리뷰] 상덕이에게는 가방이 K개가 있고 가방마다 담을 수 있는 무게가 다르다. 보석점에는 보석이 N개가 있고, 보석의 무게와 가격이 주어진다. 상덕이가 최대한 가격이 높은 보석들을 훔치려면 어떻게 해야 할까? 보석가격의 합이 최대가 되게하려면 다음과 같은 조건을 만족해야 한다. 가지고 있는 가방 K개를 다 사용해야 한다. 가방에 담을 수 있는 보석의 무게 중 가장 가격이 높은것을 훔쳐야 한다. 위와 같은 조건을 만족하며 보석을 훔치기 위해서는 먼저 가방의 무게를 오름차순으로 정렬해야 한다. 왜냐하면 가방에 담을 수 있는 무게가 높음에도 낮은 무게의 보석을 훔치게되면 낮은 무게를 담을 수 있는 가방이 가격이 높은 보석을 훔칠 수 없는 가능성이 생기기 때문이다. 예를들어 가방에 담을..

[BOJ 1700(G2) 리뷰] 처음에 문제를 보고 '골드2 문제치고는 쉽네..?' 했지만 실제 구현하는 부분에서 엄청나게 애를 먹었다. 머리론 어떻게 하면 답이 나올지 알겠는데 그걸 코드로 옮기는 과정이 조금 복잡했다. 알고리즘은 그리디 알고리즘이다. 항상 최선의 선택을 해야 한다. 멀티탭이 비어있다면 비어있는 공간에 먼저 꼽아야 한다. 이미 해당 작업이 멀티탭에 꼽혀 있다면 그냥 사용하면 된다. 멀티탭은 꽉차있고 새로운 작업을 해야 할때는 가장 나중에 사용되는 작업의 코드를 뽑아야 한다. 위 세가지의 규칙을 만족하며 진행시키면 코드를 빼는 작업을 가장 최소로 만들 수 있다. 내가 애를 먹었던 부분은 가장 나중에 사용되는 작업을 고르는 과정이였다. set도 사용해보고, 배열하나 더 만들어서 해보고 별의..

[BOJ 1744(G4) 리뷰] 이 문제도 조건을 살펴보면 그리디 문제임을 알 수 있다. 엄밀한 증명은 못하겠지만, 우리는 수의 합이 최대가 나오도록 묶어야 한다는 점을 기억하자. 따라서 우리는 다음과 같은 조건을 항상 만족하게 해야 한다. 양수는 양수끼리 곱해야 한다. 음수는 음수끼리 곱해야 한다. 양수 중 최대한 큰 값 끼리 묶어야 한다. 음수 중 최대한 작은 값 끼리 묶어야 한다. 0은 음수랑만 곱해야 한다. -1,2,1,3 이라는 값이 존재할때 어떻게 묶어야 합이 최대가 나오게 할 수 있을까? 위 조건을 만족시킨다면 -1 + 1 + (2*3) 일때 최대값이 된다. 따라서 나는 입력을 받을때 음수의 값과 양수의 값을 구별하여 우선순위 큐를 통하여 정렬하여 저장했다. 그후 음수의 값은 가장 작은 값끼..

[BOJ 2457(G4) 리뷰] 전형적인 그리디 문제라지만 나에겐 너무 어려웠다 ㅠ.. 날짜를 저장하는 방식과 꽃을 선택하는 방식에 대해 이해는 했지만 막상 코드로 짜려니 막막했다. 알고리즘은 다음과 같다. 현재 날짜를 기준으로 현재 일보다 이전에 핀 꽃들중 가장 오랫동안 피는 꽃을 선택해야 한다. 공주는 3월1일부터 꽃이 피어있어야 한다 했으므로 3월1일을 기준으로 3월1일 이전에 핀 꽃들 중 가장 오랫동안 피는 꽃을 선택하면 된다. 예를들어 3월1일부터 6월3일까지 핀다면 다음 꽃은 6월3일 이전에 피는 꽃 중 가장 오랫동안 피는 꽃을 선택해야 한다. 위 알고리즘으로 11월 30일까지 꽃이 피어있도록 하고, 11월 30일이 지나면 반복문을 종료하고 정답을 출력하면 된다. 말로 설명하면 쉽지만 경계조건..

[BOJ 1138(S2) 리뷰] 아 그리디 너무 어렵다 .. 그리디인걸 알고 풀어도 잘 안풀리는데 코테에서 그리디임을 발견하고 풀 수 있을지 모르겠다. 키가 1부터N까지인 사람들이 있다. 이 사람들은 각각 왼쪽에 자기보다 키 큰 사람이 몇명있었는지 기억한다. 우리는 그 정보를 토대로 줄을 세워야 한다. 입력이 2 1 1 0 으로 주어지면 1보다 키 큰사람이 왼쪽에 2명, 2보다 키 큰사람이 왼쪽에 1명, 3보다 키 큰사람이 왼쪽에 1명, 4보다 키 큰사람이 왼쪽에 0명 이고 이때 올바르게 줄을세우면 4 2 1 3이 된다. 이제 이걸 어떻게 푸느냐가 문제다. 물론 완전탐색으로도 풀 수있으나 문제의 본질은 아니라 생각한다. 이 문제는 키가 가장 작은 1부터 시작한다. 1보다 키가 작은 사람은 없으므로 1의 ..

[BOJ 1339(G4) 리뷰] 쉬운듯 어려운 문제이다. 자리수가 가장 높은 알파벳에 최대한 높은 값을 주어야하는 그리디 문제이다. 그리디 문제이지만 이 문제는 백트래킹으로도 풀수가 있다. 알파벳의 갯수가 최대 10개 등장하니 각각의 알파벳을 9부터 0까지의 값으로 변경하여 계산하면 10!에 문제를 풀 수 있다. 그러나 나는 백트래킹말고 그리디+시뮬레이션으로 풀고싶었다. 그래서 일단 머리속에 떠오르는대로 구현을 하고 예제TC가 다 잘 나오길래 제출을 했더니 오답처리가 되었다. 예제에서 놓친 예외사항이 있었다. 처음에 구현했을땐 문자열을 입력받아 check배열을 통해 각각의 문자열의 INDEX에 자리수를 저장하고, 저장된 자리수를 우선순위큐에 담아 자리수 큰 숫자부터 높은숫자를 부여할 생각이였다. 그러나 ..