알고리즘
-
[BOJ 11497, Python 3] 통나무 건너뛰기알고리즘/BOJ 2021. 8. 7. 20:38
https://www.acmicpc.net/problem/11497 11497번: 통나무 건너뛰기 남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 www.acmicpc.net 풀이 통나무 건너뛰기 난이도가 인접한 통나무 간의 높이의 차이의 최댓값으로 된다고 합니다. 그러면 일단 정렬을 해서 어떤 순서를 부여해야 한다는 것은 생각해보셨을 겁니다. 일단 단순 오름차순으로 해보면 마지막 통나무와 첫번째 통나무의 높이차가 매우 크기 때문에 답이 될 수는 없습니다. 그래서 처음에는 짝수 인덱스만을 사용하여 통나무를 배치하고, 홀수 인덱스만을 사용하여 뒤에 통나무를 이어서 연결..
-
[BOJ 9009, Python 3] 피보나치알고리즘/BOJ 2021. 8. 7. 20:25
https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net 풀이 N보다 작거나 같은 가장 큰 피보나치 수를 계속 빼주면 된다. N보다 작거나 같은 가장 큰 피보나치 수를 빼지 않는다고 해보자 만약 pibo[i]값을 빼야하는데 다른 값을 빼야한다면 pibo[i] = pibo[i-1]+pibo[i-2]이므로 피보나치 수 1개로 빼야할 것을 2개로 빼야해서 최소 개수를 구하라는 문제의 답이 될 수 없다. 그리고 만약 N = 21이라면 21 = 13 + 8로 구할 ..
-
[BOJ 1946, Python 3] 신입 사원알고리즘/BOJ 2021. 8. 6. 14:39
https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 풀이 N이 작으면 2중 for문으로 풀 수 있겠지만 N = 100,000이미 때문에 2중 for문을 사용하면 시간초과가 나오는 문제입니다. 2개를 동시에 비교할 수 있는 logN기법은 모르겠고, for문 하나로 풀 수 있나? 이렇게 생각해보시면 일단 점수중 하나는 순위 순서대로 정렬하는 방법을 떠올리실 겁니다. 이것만 떠올릴 수 있으면 문제는 다 푸신겁니다. 편의상 첫 번째 ..
-
[BOJ 1041, Python 3] 주사위알고리즘/BOJ 2021. 8. 6. 14:22
https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 제출할 떄마다 코드를 하나씩 빼먹어서 엄청 나게 틀린 문제... 풀이 면 3개가 보이는 곳은 4개 면 2개가 보이는 곳은 4 * (N - 2) + 4 * (N - 1)개 면 1개가 보이는 곳은 (N - 2) * (N - 2) + 4 * (N - 1) * (N - 2)개 여기까지는 바로 구하실 수 있습니다. 이제 면을 선택해야하는데 면 2개의 경우에는 인접한 두 면을 선택하면..
-
[BOJ 15903, Python 3] 카드 합체 놀이알고리즘/BOJ 2021. 8. 6. 14:13
https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 풀이 두 카드를 선택하고 점수를 합친 값을 선택한 두 카드의 값으로 재설정한다고 합니다. 이렇게 M번 반복하고, 카드들의 합이 최소화가 되는 것을 원한다고 합니다. 최소화를 하려면 가장 작은 2개를 선택하면 된다는 것을 알 수 있습니다. 코드는 heapq를 사용하였는데, for문 돌릴때마다 sort를 사용해도 상관 없습니다. 코드 1 2 3 4 5 6 7 8 ..
-
[BOJ 11047, Python 3] 동전 0알고리즘/BOJ 2021. 8. 5. 10:30
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 풀이 동전의 개수를 최소로 해서 합 K를 만들어야하므로 내림차순으로 정렬해서 몫을 이용해 몇 개의 동전을 사용할 수 있는지 확인하여 그만큼 값을 K에 빼주면 된다. 코드 1 2 3 4 5 6 7 8 n, k = map(int, input().split()) arr = sorted([int(input()) for i in range(n..
-
[BOJ 1931, Python 3] 회의실 배정알고리즘/BOJ 2021. 8. 5. 10:20
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 풀이 끝나는 시간을 1순위, 시작하는 시간을 2순위로 정렬하빈다. 이러면 먼저 끝나는 회의를 먼저 시작하고, 끝나는 시간이 같으면 가장 빨리 시작하는 회의부터 처리하게 됩니다. 이 이유는 회의가 끝나자마자 동시에 시작될 수 있기 때문이며 만약 (1, 2), (2, 2)이 입력된다면 (2, 2)부터 처리하는 경우도 생기기 때문에 무조건 2순위로 해줘야합니다. 2순위 정렬을 선택하지 않으면 인덱스 번호대로 정렬해서 순서가 뒤죽박죽이 될 수 있습니다. 정렬 2순위를 왜 해야하는지 생각하는데 오래 걸렸네요. 코드 1 2..