알고리즘
-
[BOJ 2109, Python 3] 순회강연알고리즘/BOJ 2021. 8. 13. 23:57
https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 두 가지 풀이가 존재 합니다. 풀이1 4516ms 풀이2 632ms 풀이 1 내림차순으로 정렬하고, 입력값에 나온 가장 큰 일수를 찾아 visit 배열의 크기로 설정해둔다음 내림차순한 배열을 for문으로 돌리면서 1일~x일에 예약을 할 수 있는지 for문으로 확인해봅시다. 예약할 수 있으면 하고, 아니면 넘어갑니다. 이러면 2중for문 코드가 되는데 이게 통과하..
-
[BOJ 1744, Python 3] 수 묶기알고리즘/BOJ 2021. 8. 11. 21:40
https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 풀이 간단한 그리디 + case work 문제 같습니다. 1. 1을 제외한 양수 양수에서 큰 값 2개를 계속 곱하다가 나중에 1개만 남으면 남은 한 개는 더해주면 됩니다. 2. 1일 때 1 * 7 보다 1 + 7이 더 크기 때문에 1은 전부 더해주기만 합니다. 3. 음수의 개수가 짝수일 때 제일 작은 수 2개끼리 계속 곱해주면 됩니다. 4. 음수의 개수가 홀수일 때 3번처럼 제일 작은 수 2개끼..
-
[BOJ 1715, Python 3] 카드 정렬하기알고리즘/BOJ 2021. 8. 11. 21:32
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 카드묶음이 한 개가 남을 때까지 더하기 때문에 일단 모든 카드의 값은 최소 1번씩은 더해야합니다. 여기서 이제 어떻게 더해야할지가 문제인데, 우리는 최솟값을 구해야하므로 더할 때 과정이 항상 최솟값을 보장 받으려면 최소힙을 이용하여 가장 작은 값을 가진 카드 묶음 2개를 계속 더해주면 됩니다. 증명? 만약 카드 묶음이 A, B, C 3개 있는데 A >= B >= C라고 해봅시다..
-
[BOJ 1339, Python 3] 단어 수학알고리즘/BOJ 2021. 8. 11. 20:07
https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 일단 이 문제는 알파벳의 개수가 최대 10개라서 10!으로 모든 경우의 수를 확인하면서 풀 수도 있습니다. 하지만 그리디로 풀려면 어떻게 풀어야할까요? 일단 자리수가 큰 숫자별로 9, 8, .. 숫자를 부여하는 방식을 떠올릴 수 있습니다. 하지만 이 방법은 아래와 같은 입력값이 주어지면 윗 논리대로라면 A = 9, B = 8을 넣으면 178로 최댓값이겠지만, 실제로는 A = 8, B =..
-
[BOJ 16678, Python 3] 모독알고리즘/BOJ 2021. 8. 10. 11:55
https://www.acmicpc.net/problem/16678 16678번: 모독 명예에 죽고 명예에 사는 나라 얼라이언스에는 1명의 왕과 N명의 국회의원이 있다. 각 N 명의 국회의원은 a1, a2, ..., aN 의 명예 점수를 갖고 있으며, 명예 점수가 양수인 한 그들은 국회의원을 www.acmicpc.net 풀이 오름차순으로 정렬하고, for문을 돌려서 1부터 시작하는 연속적인 단조증가수열이 나오도록 만들어주면 됩니다. 왜 이렇게 해야하는지 증명은 못하겠네요 ㅠㅠ 코드 1 2 3 4 5 6 7 8 9 n = int(input()) arr = sorted([int(input()) for _ in range(n)]) ans = 0 modok = 1 for i in range(n): if arr[..
-
[BOJ 12904, Python 3] A와 B알고리즘/BOJ 2021. 8. 10. 11:27
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net 풀이 관점을 바꿔서 T를 S로 만들면 됩니다. 왜냐하면 S에서 T로 만드는 경우에는 오른쪽에는 A를, 왼쪽에는 B를 추가해야하고, 어떤 기준으로 A와 B를 추가해야하는지 알 길이 없습니다. 그렇다고 모든 경우의 수를 하기에는 S = 1, T = 1000이면 실제로는 이것보다 적겠지만 대충 2^999가지의 경우의 수를 확인해야해서 시간내에 풀 수 없습니다. 하지..
-
[BOJ 22869, C++] 징검다리 건너기 (small)알고리즘/BOJ 2021. 8. 9. 22:24
https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 풀이 항상 오른쪽으로 이동한다는 내용을 통해 DP문제임을 알 수 있습니다. 왼쪽에서 오른쪽으로 갈 수 있는지 여부를 확인한다는 것은 힘을 K이하로 쓰고 건널 수 있냐는 뜻이므로 왼쪽에서 오른쪽으로 가는동안 필요한 힘의 최댓값을 구하고, 이 힘들중에서 최솟값을 구하여 K이하이면 YES, K 초과이면 NO를 출력하면 됩니다. 코드 1 2 3..