알고리즘/BOJ (19) 썸네일형 리스트형 [백준] 1700번 멀티탭 스케줄링 [문제] 사용할 전자 기기의 순번이 정해져있고 멀티탭에서 가장 적게 콘센트를 뽑으면서 모든 전자기기를 사용하고 싶을 때, 콘센트 뽑는 횟수의 최소값은? [풀이] 크게 3가지 정도로 나눠서 풀이할 수 있습니다. 1. 멀티탭이 비어있을 경우 2. 다음 순번의 기기가 이미 멀티탭에 꽂혀있는 경우 3. 다음 순번의 기기가 멀티탭에 없을 경우 -> 제일 마지막에 다시 사용되거나 사용될 일 없는 기기 찾기 처음에는 너무 복잡하게 생각해서 정답은 맞췄지만 코드가 100줄이 넘어갔는데 풀이를 정리해서 큰 틀부터 정리해 나가니 코드가 반토막이 났습니다... 이미 멀티탭에 꽂혀있는 전자기기의 경우는 따로 boolean array를 통해 구분하여 추가적인 서치가 필요 없도록 했습니다. 아래는 해당 코드입니다! 1 2 3 4.. [백준] 1946번 신입 사원 [문제] 신입 사원을 뽑는데, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 이 조건을 만족시키면서 선발할 수 있는 최대 인원수는?? [풀이] 우선, 서류 성적을 기준으로 정렬을 하면, 어짜피 서류성적은 이미 정렬해놔서 고려할 필요가 없고 본인보다 서류 성적이 높은 사람들의 최고 면접 점수보다 본인의 면접 점수가 높으면 합격할 수 있습니다. 1 5 3 2 -> 1 4 1 4 2 3 4 1 3 2 2 3 4 1 5 5 5 5 예제를 바탕으로 위의 값(왼쪽)을 입력했다고 했을 경우, 1등은 다른 지원자보다 떨어질 수가 없기에 기준점으로 잡고자 우선 오름차순 정렬(오른쪽)을 해줍니다. 그 후, 면접성적이 본인보다 서류 성적이 높은.. [백준] 2437번 저울 [문제] 무게가 양의 정수인 N개의 저울 추가 주어졌을 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값 구하기. [풀이] Greedy 방식으로 해결할 수 있는 문제로, 각 추를 정렬 후 누적합을 구하면서 해결해 나갈 수 있습니다. 우선, 추의 배열을 w, 누적합의 배열을 acc라고 정의하겠습니다. 무게가 1인 추가 있을 때, acc[i-1] + 1 >= w[i] 일 경우 acc[i-1] ~ acc[i] 사이의 모든 수를 만들 수 있습니다. 만약 저 조건에 해당하지 않는다면 acc[i-1] + 1이 만들수 없는 수 입니다. 그리고 무게가 1인 추가 없다면 당연히 답은 1이겠죠? 문제에 제시된 예제를 통해 설명하도록 하겠습니다. i 0 1 2 3 4 5 6 추(w) 1 1 2 3 6 7 .. 이전 1 2 3 다음