알고리즘
-
[BOJ 22988, Python 3] 재활용 캠페인알고리즘/BOJ 2021. 9. 4. 23:01
https://www.acmicpc.net/problem/22988 22988번: 재활용 캠페인 첫 번째 용기와 두 번째 용기를 가져가서 용량이 $\left(0+1+\frac{13}{2}\right)$㎖ $=$ $7.5$㎖ 남은 용기를, 세 번째 용기와 네 번째 용기를 가져가서 용량이 $\left(2+3+\frac{13}{2}\right)$㎖ $=$ $11.5$㎖ 남은 용 www.acmicpc.net 풀이 X ml인 헤어 에센스를 최대한 많이 만들어야 하므로 일단 2개로 1개를 만드는 것을 생각할 수 있습니다. 이러면 투포인터를 사용해 a = 0, b = len(C) - 1로 설정하여 C[a] + C[b] >= 0.5 * X가 되면 답에 1을 추가해줍니다. 그리디적인 아이디어인데 [남은 용량이 제일 작은..
-
[BOJ 22981, Python 3] 휴먼 파이프라인알고리즘/BOJ 2021. 9. 4. 23:00
https://www.acmicpc.net/problem/22981 22981번: 휴먼 파이프라인 모든 상자를 최대한 빠르게 옮기는 경우의 작업 시간을 분 단위로 출력한다. www.acmicpc.net 풀이 문제를 읽어보면 제일 느린 사람의 속도로 맞추기 때문에 v를 정렬하면 팀 한 개는 속도가 v[0]으로 확정되어 있습니다. 그리고 i != 0인 다른 속도 v[i]를 나머지 팀의 속도로 정해둔다고 가정하면 최대한 빠르게 옮기는 경우는 v[i]보다 속도가 빠른 n - i명의 사람들을 전부 v[i]가 속한 팀에 들어가는 것입니다. v[0]
-
[BOJ 13334, Python 3] 철로알고리즘/BOJ 2021. 9. 3. 16:50
https://www.acmicpc.net/problem/13334 13334번: 철로 입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,0 www.acmicpc.net 풀이 일단 문제를 풀려면 정렬을 해야한다는 것을 아실 수 있는데, 그리디 알고리즘 문제를 좀 푸셨다면 큰 값을 기준으로 오름차순 정렬해야 한다는 것을 알 수 있습니다. 이런 아이디어를 사용하는 그리디 문제에서 가장 기초적인 문제는 이 문제(풀이)가 있습니다. 문제에서 구하는 것은 좀 다르지만 아이디어는 비슷하죠 이렇게 정렬을 한 뒤엔 이제 철로의..
-
[BOJ 10989, Python 3] 수 정렬하기 3알고리즘/BOJ 2021. 9. 3. 16:42
https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 메모리 제한이 많이 작습니다. 그런데 정렬할 수의 최댓값이 10,000이므로 크기가 10001인 배열을 만들고, 어떤 수 x가 있으면 arr[x] += 1을 해주어서 마지막에 출력할 때는 배열의 인덱스를 해당 위치의 리스트가 가지고 있는 값만큼 출력을 해주면 됩니다. 이런 정렬은 카운팅 소트(Counting sort)라고 부르며 자세한 내용은 https://00ad-8e71-00ff-055d.tistory.co..
-
[BOJ 4619, Python 3] 루트알고리즘/BOJ 2021. 9. 3. 16:35
https://www.acmicpc.net/problem/4619 4619번: 루트 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, B와 N이 주어진다. (1 ≤ B ≤ 1,000,000, 1 ≤ N ≤ 9) 입력의 마지막 줄에는 0이 2개 주어진다. www.acmicpc.net 풀이 B의 값도 작고, N의 값도 작아서 바로 브루트포스를 생각할 수 있습니다. 계산을 더 빠르게 하기 위하여 N = 1일 때는 B = A가 성립하므로 이 경우를 제외하고, N = 2일 때 B = 1,000,000인 경우는 A = 1,000이므로 N = 2이상부터는 1부터 1,000까지 브루트 포스를 통하여 확인해주시면 됩니다. 코드 1 2 3 4 5 6 7 8 9 while 1: b, ..
-
[BOJ 17489, Python 3] 보물 찾기알고리즘/BOJ 2021. 9. 1. 19:58
https://www.acmicpc.net/problem/17489 17489번: 보물 찾기 (1, 1) - (1, 2) - (1, 3) - (1, 4) - (2, 4) - (3, 4) 로 이동하며, (3, 4) 지점으로부터 “ABC”를 더 이상 찾아갈 수 없어 문자열 “ABC”를 2번 따라간 곳에 보물이 있다고 생각한다. www.acmicpc.net 풀이 문제에서 중복된 알파벳이 주어지지 않는다고 했으므로 사이클이 생기는 경우는 무조건 마지막 문자열 다음 첫번째 문자열이 오는 경우입니다. 이 부분을 만나면 -1을 출력해주고 종료해주시면 됩니다. 사이클을 확인하는 방법은 DFS를 하면서 visit[x][y] = 1을 해주다가 해당 노드보다 더 뒤로 돌아가게 될 경우엔 visit[x][y] = 0으로 바꿔..
-
[BOJ 17488, Python 3] 수강 바구니알고리즘/BOJ 2021. 9. 1. 19:00
https://www.acmicpc.net/problem/17488 17488번: 수강 바구니 첫째 줄부터 N개의 줄에 걸쳐 1번 학생이 수강등록에 성공한 과목, 2번 학생이 수강등록에 성공한 과목, …, N번 학생이 수강등록에 성공한 과목을 공백으로 구분해 오름차순으로 출력한다. 수강 www.acmicpc.net 풀이 먼저 각 수업마다 어떤 학생이 수강 신청에 성공하였는지 확인하는 success 리스트와 각 수업마다 업데이트를 해야하니 success리스트와 구조가 같은 새로운 new_success라는 리스트가 필요합니다. 이렇게 준비한다음 1차 수강 바구니를 전부 new_success라는 리스트에 저장해주고, 다 신청했다면 for문으로 각 수업마다 수강제한인원 이하로 신청하였는지 확인하여 조건에 만족하..
-
[BOJ 17487, Python 3] 타자 연습알고리즘/BOJ 2021. 9. 1. 18:55
https://www.acmicpc.net/problem/17487 17487번: 타자 연습 건덕이가 입력할 문장 S가 주어진다. S는 영어 대소문자와 공백으로 이루어져 있으며, 공백 포함 최대 100글자이다. 공백은 연속해서 나타나지 않으며, 문장의 시작과 끝은 공백이 아니다. www.acmicpc.net 풀이 l, r 변수를 잡아서 영어만 사용하는 경우는 모두 더해주고, shift와 space bar 사용횟수는 한 변수에 전부 저장해줍니다. 저는 이걸 etc라는 변수에 저장했습니다. 이렇게 했으면 이제 etc 변수를 적절히 나눠서 l과 r에 더해주면 됩니다. 여기서 경우의 수가 있는데요. 1) abs(l - r) >= etc일 경우 이런 경우에는 l이나 r중 작은 값에 etc을 전부 더해주면 됩니다...