알고리즘
-
[BOJ 10775, Python 3] 공항알고리즘/BOJ 2021. 8. 16. 16:12
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 풀이 그리디도 비슷한 유형의 문제들이 많이 보이네요. 일단 1번부터 g[i]번 게이트까지 영구적으로 도킹하려고 하면, 도킹할 수 있는 게이트의 최댓값을 찾아서 도킹해주는 것이 최적임을 알 수 있습니다. g[i]번부터 시작하여 1번까지 확인해보면서 도킹할 수 있는 곳에 도킹한다는 말입니다. 왜냐하면 만약 1~4번 게이트까지 도킹하는 비행기를 1번에 도킹하고, 1번 ..
-
[BOJ 1781, Python 3] 컵라면알고리즘/BOJ 2021. 8. 16. 15:19
https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 풀이 순회 강연, 과제 문제와 과정은 똑같고 범위만 다릅니다. 이 문제에서는 N = 100,000이라서 x일 이내에 풀 수 있으면 반복문을 이용해 1~x일을 확인하여 매칭해주면 시간초과가 나옵니다. 그래서 데드라인을 기준으로 오름차순으로 정리하고, 반복문을 통해 우선순위 큐에 넣어주다가 우선순위 큐의 길이가 현재 보고 있는 과제의 데드라인보다 크면 가장 작은 값 하나를 빼주면 됩니다. 이게 왜 가능하냐면 ..
-
[BOJ 1202, Python 3] 보석 도둑알고리즘/BOJ 2021. 8. 15. 15:44
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 가방은 용량을 기준으로 내림차순으로 정렬하고, 보석은 무게 순으로 내림차순 정렬을 합니다. 그리고 (보석의 무게) use_bag: heappop(ans) print(sum(ans)) Colored by Color Scripter cs
-
[BOJ 13904, Python 3] 과제알고리즘/BOJ 2021. 8. 15. 15:30
https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 순회강연 문제랑 범위만 다르고 똑같습니다. 순회강연보다 N범위가 작아서 아무거나 해도 시간 차이가 별로 나지 않습니다. 풀이 1 점수를 기준으로 내림차순으로 정렬하고, 1일부터 x일까지 예약을 확인할 수 있을지 확인해볼 것이니 최대 1000일까지 확인할 수 있으므로 visit 배열의 크기를 1001로 해줍니다. 내림차순한 배열을 for문으로 돌리면서 1일~x일에 예약을 할 수 있는지 for문으로 확인해봅시다. 예약할 수 있으면 하고, 아니면..
-
[BOJ 8980, Python 3] 택배알고리즘/BOJ 2021. 8. 15. 15:16
https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 조건 3을 다르게 해석해서 뻘짓하다가 겨우 풀었네요 풀이 문제를 읽어보면 트럭에 박스를 최대한 꽉 채워서 가는 것이 제일 좋을 거라고 바로 생각할 수 있을 겁니다. 그리고 박스를 최대한 꽉 채워서 가면서 배송할 수 있는 박스 수를 최대화하려면 늦게 도착하는 박스보다 일찍 도착하는 박스를 우선으로 배송하는 것이 좋겠네요. 그러면 정렬을 할 때 도착마을을 기준으로 오름차순 정렬을 ..
-
[BOJ 2437, Python 3] 저울알고리즘/BOJ 2021. 8. 15. 14:57
https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀이 정석 풀이는 아니지만 무게를 측정할 수 있다 = 더하기를 적절히 이용해서 무게를 만들어야 한다. 여기서 키워드를 얻어서 추를 오름차순으로 정렬한 뒤 첫 번째 추를 리스트에 넣어주고, 두 번째 추부터는 리스트에 있는 추에 전부 현재 인덱스의 추를 모두 더해준다음 현재 추를 리스트에 넣어주고, 리스트를 오름차순으로 정렬하는 과정을 반복하였습니다. 저러고 출력을 해보면 신기하게 (1번째 추부터 i-1번째 추..
-
[BOJ 2457, Python 3] 공주님의 정원알고리즘/BOJ 2021. 8. 14. 00:21
https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 풀이 회의실 배정 문제랑 비슷한데, 날짜 처리도 그렇고 꽃이 지기 전에 꽃을 미리 구해놔야해서 생각하기가 좀 까다로웠던 문제였습니다. 일단 값을 받을 때 날짜를 1월 1일이면 101, 12월 31일이면 1231처럼 월에 100을 곱해줘서 일이랑 더해줍니다. 다 했으면 이제 날짜순으로 오름차순 정렬을 해주면 됩니다. 그리고 먼저 3월 1일 이전에 꽃이 피면서 제일 늦게 지는 꽃을..
-
[BOJ 16120, Python 3] PPAP알고리즘/BOJ 2021. 8. 14. 00:11
https://www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 풀이 문제를 잘 읽어보면 알파벳 P에서부터 시작하는 것이라서 PP, PPPP이런 것은 PPAP 문자열이 될 수 없습니다. 그리고 문제에서는 P를 PPAP로 변경하는 것이지만, 이걸 거꾸로 뒤집으면 PPAP를 P로 만들 수 있습니다. 따라서 스택에 문자열을 하나씩 저장하다가 마지막 4글자가 PPAP이면 원소를 4개를 빼고 P를 넣어주면 됩니다. → 방향으로 문자열을 저장해 나가는 것이 틀릴 수도 있는 것이 아니냐 생각하실 수도 있는데, P에서부터 시..