알고리즘
-
[BOJ 20949, Python 3] 효정과 새 모니터알고리즘/BOJ 2021. 8. 25. 15:28
https://www.acmicpc.net/problem/20949 20949번: 효정과 새 모니터 효정은 새해를 맞이하여 새 모니터를 구매하고자 한다. 효정은 돈이 많기 때문에 77인치 모니터를 구매할 것이다. 모니터를 구경하던 효정은 놀라 자빠질 수밖에 없었다. 모니터가 너무 많아 고 www.acmicpc.net 풀이 간단한 정렬 문제 입니다. sort안에 key와 lambda를 사용하여 정렬을 해주면 됩니다. 문제에서 가로 픽셀과 세로 픽셀만 주어졌으므로 (가로 픽셀)^2 + (세로 픽셀)^2 기준으로 정렬해도 무방합니다. 코드 1 2 3 n = int(input()) arr = sorted([[*map(int, input().split())] + [_+1] for _ in range(n)], ke..
-
[BOJ 1422, Python 3] 숫자의 신알고리즘/BOJ 2021. 8. 18. 20:43
https://www.acmicpc.net/problem/1422 1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 풀이 모든 숫자를 최소 한 번씩 사용하고, 나머지 N - K는 아무거나 사용해서 최댓값을 만들어야 합니다. 일단 먼저 모든 숫자를 딱 한 번씩 사용하여 큰 수를 만드는 방법을 생각해보면 최대한 맨 앞에 9가 많이 나오게 해주면 됩니다. 9가 없으면 8, 8이 없으면 7, ...이렇게요 그러면 이제 정렬을 해야 하는데, 정렬하는 방법은 의외로 매우 간단합니다. 숫자 문자열..
-
[BOJ 16496, Python 3] 큰 수 만들기알고리즘/BOJ 2021. 8. 18. 20:31
https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net 풀이 정렬 방법은 의외로 간단합니다. 숫자로 이루어진 문자열 a, b 두 개가 있을 때 int(a+b), int(b+a)를 하여 비교를 해주면 됩니다. 이 문제에서는 큰 수를 만드는 것이므로 큰 수가 앞으로 오게하면 되겠네요. C++에서 compare로 비교하는 경우가 많지만, 파이썬에서는 key= lambda x: blah blah로 하면 많은 정렬 문제를 해결..
-
[BOJ 4716, Python 3] 풍선알고리즘/BOJ 2021. 8. 18. 17:11
https://www.acmicpc.net/problem/4716 4716번: 풍선 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000) 다음 N개 www.acmicpc.net 풀이 이 문제는 입력된 순서대로 풍선을 주는 것이 아니니 정렬해볼 수 있다는 것을 생각해볼 수 있습니다. 거기다가 매 선택마다 최적해를 선택해야하니 각 팀마다 A와 B중 하나에 몰아넣을 수 있을 수 있겠네요. 그러면 경우의 수가 3가지로 나옵니다. 1. A와 B중 최솟값을 기준으로 오름차순하여 값이 작은 풍선부터 줌 2. A와 B중 최댓값을 기준으로 내림차순하여 값이 ..
-
[BOJ 9576, Python 3] 책 나눠주기알고리즘/BOJ 2021. 8. 17. 22:11
https://www.acmicpc.net/problem/9576 9576번: 책 나눠주기 백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 www.acmicpc.net 풀이 일단 정렬해야 하는 것은 아실겁니다. 다행히도 정렬할 수 있는 경우의 수가 5가지 밖에 없어서 모두 확인해볼 수 있습니다. 오름차순은 번호를 작은 것부터 주는 것이 최적해이니 그렇게 주고, 내림차순은 반대로 번호가 큰 것부터 주는 것이 최적해이므로 그렇게 준다고 가정해봅시다. 1) a기준으로 오름차순 1 2 1 3 2 2 이렇게 하면 답은 2로 나오지만 실제 답은 3임 2) a기준으로 내림차순 ..
-
[BOJ 1135, Python 3] 뉴스 전하기알고리즘/BOJ 2021. 8. 17. 21:48
https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net N이 작아서 풀이가 여러가지 풀이가 가능합니다. 제 풀이는 그리디 + 위상정렬입니다. 풀이 상사가 직속 부하한테 전화를 한다고 하니까 루트 노드(민식이)부터 시작하여 리프노드까지 전화를 돌린다고 합니다. 만약 직속 부하가 여러명이면 리프 노드까지 가는데 가장 오래 걸리는 순서대로 전화를 먼저하면 되겠습니다. 왜냐하면 만약 직속 부하가 3명이고 각각 직속 부하에서 리프 노드까지 가는데 [3분, 4분, 1..
-
[BOJ 17619, Python 3] 개구리 점프알고리즘/BOJ 2021. 8. 17. 21:25
https://www.acmicpc.net/problem/17619 17619번: 개구리 점프 첫 번째 줄에 통나무 개수 N과 질문의 개수 Q가 주어진다. 다음 N개의 줄에 각 통나무에 x1, x2, y의 세 정수 좌표가 주어진다. 주어진 통나무는 두 점 (x1, y)와 (x2, y)를 잇는 형태이다. (x1 통나무 -> 통나무로 이동하면 되는 것이라서 통나무와 통나무 사이에 통나무가 있어도 상관이 없다는 것을 캐치했으면 문제가 매우 쉬워집니다. 어떻게 되든 x값의 범위만 겹치면 어떻게든 이동할 수 있어서 사실상 y축..
-
[BOJ 3109, Python 3] 빵집알고리즘/BOJ 2021. 8. 16. 16:29
https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 골드2부터는 본격적으로 다른 스킬을 같이 쓰이는 문제들이 많이보이네요 이 문제는 그리디보다는 DFS에 치중된 문제 같습니다. 풀이 그리디 생각은 아주 간단합니다. 맨 위 좌표부터 확인하여 파이프들의 방향을 맨 위로 가게 우선순위를 설정하거나, 맨 아래 좌표부터 확인하여 맨 아래로 가게 우선순위를 설정하거나 둘 중 하나로 하면 됩니다. 일직선을 우선순위로 하면 안되는 이유, 맨 아래에서는 맨 아래 좌표부터 확인하고..