본문 바로가기
반응형

정렬6

[C/C++] #1931 회의실 배정(탐욕) 최대한 많은 회의를 겹치는 시간 없이 하고자 합니다. 이 경우에는 빨리 끝나는 회의를 우선 배정하면 다음에 배정할 수 있는 회의가 많아질 수 있습니다. 선택의 폭을 넓히기 위해서는 회의가 끝나는 시간순으로 정렬합니다. 그런 후에 현재 끝난 회의의 시간을 기록하고, 시작시간이 그 시간보다 앞이라면 해당 회의는 할 수 없습니다. 제가 작성한 소스입니다. 소스는 참고용으로 봐주세요. //------------------------------------------ // baekjoon #1931 // - by Aubrey Choi // - created at 2019-09-07 //------------------------------------------ #include #include struct Lesso.. 2022. 11. 13.
[C/C++] 백준 #1758 알바생 강호(탐욕) 이번 문제는 팁을 최대로 받기 위해서 적절한 전략을 세울 필요가 있습니다. 사실 모두 꽤 많은 팁을 생각했다면, 어떤 순으로 커피를 전달해도 결과는 같습니다. 예를 들어서 3명의 손님이 10원, 20원, 30원을 생각했다면, 순서와 관계가 없이 받는 팁은 같습니다. 알바생 강호는 10원, 19원, 28원을 받게 되겠죠. 순서가 바뀌어도 (10원 29원, 18원), (20원, 9원, 28원), (20원, 29원, 8원) 형태가 되어서 일정한 금액을 받습니다. 문제의 핵심은 음수를 많이 만들어서 등수에 의해서 빠지는 수를 적게 하는 것입니다. 그러면, 정렬을 해서, 적은 금액의 팁을 생각한 것들의 등수를 뒤로 밀어놓음으로써, 가능한 많은 음수를 만드는 것입니다. 예를 들어서 3명의 손님이 1원, 2원, 3원.. 2022. 10. 11.
[C/C++] 백준 #1755 숫자놀이(정렬) 이번 문제는 숫자를 단어로 바꾸었을 때, 사전순서로 정렬하는 문제죠. 제 경우에는 ord란 배열을 이용해서 순서를 정했습니다. 최대 숫자가 99이므로 두자리 숫자가 최대가 됩니다. 0은 zero로 가장 순서가 늦게 되겠죠. 그 순서대로 하면 아래의 표대로 됩니다. 다른 숫자에 같은 단어가 있을 수 없으므로 1이 가장 앞에 수이고, 10이 가장 뒤의 수로 놓았습니다. 가장 앞의 수는 8(eight)가 됩니다. 0 1 2 3 4 5 6 7 8 9 10 5 9 8 3 2 7 6 1 4 위의 표를 이용해서 cmp함수를 만들었습니다. 위의 표에서 제가 순서를 나타낼 때 0을 사용치 않은 것은 3과 38을 비교하기 위해서입니다. 0부터 시작했다면, 3과 38은 같은 값을 가지게 되었을겁니다. 수는 두자리 숫자인 경.. 2022. 10. 10.
[C/C++] 백준 #1715 카드 정렬하기(탐욕 알고리즘) 이번 문제는 카드 정렬하기이고요. 이 문제는 정렬된 여러개의 카드 더미가 있을 때, 모두 다 정렬하기 위해서 어떤 순으로 혼합(Merge)를 하는 것이 좋을까입니다. 각각 n과 m개의 카드를 가지고 있는 두 더미를 혼합을 하기 위해서는 \(O(n+m)\)의 비교횟수와 이동횟수를 가지고 있다는 것은 잘 알려져 있습니다. 실제 이동 횟수는 \(n+m\)번이 됩니다. 이 문제에서는 혼합을 하는 과정을 구현하는 것은 아닙니다. 정렬을 하기 위해서는 우리는 두 더미를 혼합하게 되는데, 혼합하는 순서에 따라서 전체적인 이동 횟수가 달라지게 됩니다. 더하기 연산을 할 때, 그 결과값을 모두 더하는 것과 같습니다. 3, 5, 7, 9 개의 카드가 있는 더미를 생각한다면, 1) 3 + 5 = 8 --> 총 이동횟수 : .. 2022. 10. 1.
#1521 랜덤 소트(dynamic programming) 이번 문제는 꽤 재미있는 주제입니다. 인공지능 마르코프 체인을 이야기하다보면, 기대값을 계산하는 부분이 있습니다. 이 부분을 잘 활용하고, 그리고 잦은 중복 호출이 발생하니 동적 계획법도 이용해야 합니다. 문제는 아래와 같습니다. https://www.acmicpc.net/problem/1521 1521번: 랜덤 소트 첫째 줄에 순열의 크기 N이 주어진다. 둘째 줄에 순열에 들어있는 수 N개가 주어진다. 이 수는 모두 1보다 크거나 같고, N보나 작거나 같으며, 같은 수는 2번 이상 주어지지 않는다. 또, N은 8보다 www.acmicpc.net 마르코프 프로세스에 의하면 우리가 현재 상태(\(S_c\))의 기대값은 다음과 같이 구할 수 있습니다. \[ E(S_c) = \sum_{p} P_{c, p} \.. 2022. 8. 31.
백준 #1083 소트(정렬) 이번 문제는 버블 정렬을 잘 이해하고 있다면, 쉽게 풀 수 있는 문제입니다. 난이도가 Gold IV이긴 하지만 더 낮아져도 상관 없을 문제라고 봅니다. 정답비율은 30.5% 정도로 높지가 않습니다. 정답자 184명. https://www.acmicpc.net/problem/1083 1083번: 소트 크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다. www.acmicpc.net 버블 정렬은 이해하기 아주 쉬운 정렬이고, 구현도 쉽게 할 수 있죠. 버블정렬은 이웃한 것끼리 위치를 바꾼다는 개념입니다. 키 순으로 줄을 설 때.. 2019. 12. 31.
728x90

티스토리툴바