알고리즘
-
[BOJ 22871, C++] 징검다리 건너기(large)알고리즘/BOJ 2021. 8. 9. 22:21
https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 풀이 항상 오른쪽으로만 갈 수 있다고 했으므로 바로 DP문제라는 것을 알 수 있습니다. 돌로 건너갈 수 있는 모든 경우 중 K의 최솟값을 구하라고 했으므로 왼쪽 -> 오른쪽으로 가는 동안 쓰는 힘의 최대값들중에서 최솟값을 출력하면 됩니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2..
-
[BOJ 11000, Python 3] 강의실 배정알고리즘/BOJ 2021. 8. 9. 15:20
https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀이 강의실이 끝나는 시간을 우선순위 큐에 저장하여 새로운 수업이 들어오기 전에 while문이나 if문으로 해당 수업 시작 시간 이전에 끝날 수 있는 강의실을 비우게 하면 됩니다. while문은 해당 수업 시작 전에 끝나는 모든 강의실을 비워두니까 쉽게 이해할 수 있습니다. if문을 사용하는 것은 만약 현재 사용하는 강의실 수가 x개일 때, 강의실을 비울 수 있으면 강의실은 x-1개가 되고 현재 수업이 강의실을 사용해서 x개가 유지가 됩니다. ..
-
[BOJ 2812, Python 3] 크게 만들기알고리즘/BOJ 2021. 8. 9. 15:10
https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 일단 반폐구간 [0, k)에서 얻을 수 있는 최댓값과 해당 인덱스를 구합니다. 그 인덱스를 x라고 하면 이후 (x, x+k]에서도 최댓값과 해당 인덱스를 구하는 과정을 반복합니다. 이게 가장 주먹구구식 방법인데 해당 방법을 사용하면 N = 500000, K = N-1일 때 생각하면 시간초과가 나옵니다. 해당 방법과 결과가 똑같은데 시간이 좀 더 빠른 방법을 생각해보면 원소를 스택에 넣어주는데, 넣어주기 전에 while문을 이용해 해당 원소의 값보다 스택 맨 위에 있는 ..
-
[BOJ 2212, Python 3] 센서알고리즘/BOJ 2021. 8. 9. 14:53
https://www.acmicpc.net/problem/2212 2212번: 센서 첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있 www.acmicpc.net 풀이 구간을 구하는 것이므로 가능한 짧은 기지국과 기지국 사이의 거리만 더해주면 되기 때문입니다. 센서 사이의 길이들을 구하고 내림차순하여 n - (k - 1)개의 길이를 더해주면 됩니다. 증명 문제를 다른 관점으로 살펴보면 전체 센서 사이의 거리는 전체 길이는 다음 그림과 같이 구할 수 있습니다. 이 길이는 한 기지국만을 사용했을 때의길이 입니다. 여기서 기지국을 하나 ..
-
[BOJ 1461, Python 3] 도서관알고리즘/BOJ 2021. 8. 8. 15:33
https://www.acmicpc.net/problem/1461 1461번: 도서관 첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N은 10,000보다 작거나 같은 자연수이고, M은 10,000보다 작거나 같다. 책의 위치 www.acmicpc.net 풀이 예제가 단순한 예제였으면 풀기 엄청 힘들었을 것 같은 문제인데, 다행히도 예제가 문제를 푸는 아이디어를 이용해서 풀 수 있기 때문에 예제만 풀 수 있으면 쉽게 풀 수 있었던 문제입니다. 절댓값이 가장 큰 부호를 찾고, 그 큰 값부터 부호별로 내림차순으로 최대 m개씩 가져가면 됩니다. 절대값이 가장 큰 부호에서 처음 m개는 한 번만 더해주고, 나머지는 2를 곱해서 더해주면 됩니..
-
[BOJ 1092, Pypy3] 배알고리즘/BOJ 2021. 8. 8. 15:14
https://www.acmicpc.net/problem/1092 1092번: 배 첫째 줄에 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 각 크레인의 무게 제한이 주어진다. 이 값은 1,000,000보다 작거나 같다. 셋째 줄에는 박스의 수 M이 주어진다. M은 10,000보 www.acmicpc.net 풀이 크레인, 박스를 전부 내림차순을 하여 각자 크레인 기준으로 자신이 들 수 있는 가장 큰 무게를 들면 됩니다. 내림차순을 하여 첫 번째 크레인보다 첫 번째 박스의 무게가 크면 -1을 출력하면 됩니다. del을 사용하기 때문에 pypy3으로 제출해야 통과합니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 input = __import__('s..
-
[BOJ 17609, Python 3] 회문알고리즘/BOJ 2021. 8. 8. 15:08
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 풀이 회문에서 삭제할 곳을 찾는 방법은 양끝부터 확인하는 for문을 만들어서 확인해보면 삭제해야할 부분에서 에러가 나올겁니다. 만약 나오지 않으면 0을 출력하면 됩니다. 삭제해야하는 글자는 왼쪽에서 시작하는 글자, 오른쪽에서 시작하는 글자 둘 중 하나이기 때문에 왼쪽 인덱스의 글자를 삭제해보고 돌려보고, 오른쪽 인덱스의 글자를 삭제해서 돌려보고 확인해보고 둘 중 하나라도 회문이 만들어지면 1을 출력, 아니면 2를 출력하면 됩니..
-
[BOJ 16953, Python 3] A → B알고리즘/BOJ 2021. 8. 7. 20:40
https://www.acmicpc.net/problem/16953 16953번: A → B 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다. www.acmicpc.net 풀이 log2(10^9)를 해보면 그렇게 큰 수가 나오지 않는 것을 알 수 있습니다. 그래서 걍 큐에 현재 숫자에 2배를 한 수, 현재 숫자의 뒤에 1을 붙인 수를 넣어주고, B값이 나오면 출력을 해주면 됩니다. 그러나 큐에 있는 원소가 다 빠져나갈 때까지 B를 찾지 못하였으면 -1을 출력해주면 됩니다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 A, B = map(int, input().split()) q = __import__('collections').deque([[A, 0]]) while q: x,..