정리

백준 1461번: 도서관 - 정렬과 그리디 알고리즘을 활용한다. - 예제로 나온 7 2 -37 2 -6 -39 -29 11 -28 를 살펴보자. 좌표를 음수와 양수로 나누어 서로 다른 LinkedList에 저장한다. LinkedList를 내림차순으로 정렬하면 위의 사진처럼 될 것이다. (-39) 좌표는 원점으로부터 제일 먼 곳이므로 제일 마지막에 가야 된다. 왜냐하면 마지막에는 책을 가져다 놓고 다시 원점으로 돌아올 필요가 없기 때문이다. 따라서 두 LinkedList의 0번째 인덱스의 값을 비교하여 절댓값이 더 큰 좌표는 편도 거리만 계산한다. 이 때 -39에 가면서 -37에 들렸다가 가야 된다. 따라서 해당 LinkedList(여기서는 A LinkedList)를 m-1번 poll() 해 준다. 그러면..

백준 2473번: 세 용액 - 정렬과 투 포인터를 활용한 문제입니다. 용액의 값을 저장한 리스트를 오름차순으로 정렬합니다. tmp를 inf로 선언하고 세 용액의 합이 0에 더 가까우면 세 용액의 합을 tmp에 저장합니다. 기준점 i 를 잡습니다. left = i + 1, right = n - 1 로 투포인터를 잡습니다. liquid[i] + liquid[left] + liquid[right], 세 용액을 더한 값을 sum으로 합니다. sum의 절댓값이 tmp의 절댓값보다 작으면 현재의 세 용액의 합이 0에 더 가까운 것이므로 tmp의 값을 sum으로 해줍니다. i) sum 0 - sum이 0보다 크..

백준 2470번: 두 용액 - 리스트에 용액들의 특성값을 입력합니다. - 리스트를 오름차순으로 정렬합니다. - left = 0, right = N - 1로 설정하고 이분탐색을 위해 left < right 일 때까지 while문을 반복합니다. i ) 두 용액의 특성값의 합이 0인 경우 - while문을 break하고 결과를 출력합니다. ii) 두 용액의 특성값의 합이 음수인 경우 - 음의 특성값의 절댓값이 양의 특성값의 절댓값보다 크기 때문에 left += 1 을 통해 두 용액의 특성값의 합이 0에 가까워 질 수 있도록 합니다. iii) 두 용액의 특성값의 합이 양수인 경우 - 양의 특성값의 절댓값이 음의 특성값의 절댓값보다 크기 때문에 right -= 1를 통해 두 용액의 특성값의 합이 0에 가까워질 수..

백준 1946번: 신입 사원 - 정렬을 사용하는 문제입니다. - 지원자들의 점수를 입력 받은 뒤 서류심사 성적 순위를 오름차순으로 정렬합니다. - 서류심사 성적을 1등 한 지원자의 면접 성적 순위를 기준(pivot)으로 삼습니다. - for문을 통해 나머지 지원자들의 면접 성적 순위와 비교합니다. 만약 i번째 지원자의 면접 성적 순위가 pivot보다 작다면(등수가 높다면) 합격자의 인원을 추가하고 pivot을 i번째 지원자의 면접 성적 순위로 바꿉니다.

백준 2217번: 로프 - 입력받은 로프 값을 visit[로프 값] += 1 을 통해 저장합니다. - for문을 통해 계산을 합니다. - N = 2, 10과 15를 입력받을 때를 예로 들겠습니다. visit[10] = 1, visit[15] = 1입니다. for문을 통해 10000부터 1까지 돌겠습니다. i = 15 일 때, s = 1이고 이 때 들 수 있는 최대 무게는 i * s 입니다. max(answer, i *s) 로 들 수 있는 최대 무게를 구합니다. i = 10일 때, s = 2이고 이 때 들 수 있는 최대 무게 역시 i * s 입니다. max(answer, i * s) 를 통해 들 수 있는 최대 무게를 구해서 answer에 저장하면 됩니다.

백준 3079번: 입국심사 - 이분탐색 알고리즘을 활용해야하는 문제입니다. - 이분탐색의 경계값은 left = 최단 시간 심사대, right = 최장 시간 심사대 * 인원수 입니다. - total 은 mid시간 동안 검사할 수 있는 총 사람의 수 입니다. total 은 mid시간 // 각 심사대의 소요 시간 의 총합을 구하면 됩니다. mid시간동안 M보다 더 많은 인원을 심사하는 것은 답이 될 수 있지만 M보다 적은 인원을 심사하는 것은 안되므로 total >= M 인 경우와 아닌 경우로 나누어 생각했습니다. - 파이썬 같은 경우에는 sys를 꼭 import하여 풀어야합니다. sys.stdin.readline()를 활용하여 입력값을 받아야지 시간초과에 안 걸립니다. N이 작을 때에는 문제가 없지만 100..

백준 2839번: 설탕배달 - N보다 작은 가장 큰 5의 배수를 구합니다. 봉지의 최소 개수를 구해야 하므로 5킬로그램을 우선적으로 고려하기 위함입니다. - (N - 5킬로그램으로 담은 무게) 가 3의 배수라면 3킬로그램 봉지에 담아 총 봉지의 개수를 구하면 됩니다. - (N - 5킬로그램으로 담은 무게) 가 3의 배수가 아니라면 5킬로그램 봉지의 수를 하나 줄입니다. (N - 5킬로그램으로 담은 무게) 가 3의 배수가 될 때까지 이 과정을 반복합니다. - 5킬로그램 봉지가 0개 일 때에도 (N - 5킬로그램으로 담은 무게) 가 3의 배수가 아니라면 정확하게 N킬로그램을 만들 수 없는 경우이므로 -1을 출력합니다.

백준 1931번: 회의실배정 - 최대한 많은 회의를 배정하기 위해서는 빨리 끝나는 회의를 우선배치해야 됩니다. - 왜 빨리 끝나는 회의 순서로 배치해야 되는지 증명을 여기서 하면 좋겠지만 이미 깔끔하게 설명한 유튜브 동영상이 있어서 첨부합니다. (강의실 배정 알고리즘 증명 유튜브 동영상) - Comparator 를 통해 회의가 빨리 끝나는 순서대로 정렬합니다. - 앞의 회의가 끝나는 시간보다 회의를 시작하려는 시간이 크거나 같으면 회의를 하고 ANSWER++ 를 합니다. 이 작업을 a[1]부터 a[N-1]까지 반복합니다. - 최소 한 개의 회의는 항상 할 수 있으므로 ANSWER은 1로 초기화합니다.

백준 17609번: 회문

백준 2212번: 센서 - 그리디 알고리즘과 정렬을 이용하는 문제입니다. - 예를 들어 N = 6, K = 2 일 경우, 좌표 3과 6에 센서를 설치하면 2 + 3 = 5로 최솟값이 됩니다. 5 = 0 + 1 + 2 + 2 입니다. 이를 일반화 해보면 다음과 같습니다. 센서의 좌표를 입력 받은 뒤, 오름차순으로 정렬합니다. 각 센서 간의 거리를 구합니다. 센서 간의 거리를 오름차순으로 정렬합니다. 0번 index부터 n-k-1번 index까지의 총합을 구합니다.