알고리즘
-
[BOJ 23030, Python 3] 후다다닥을 이겨 츄르를 받자!알고리즘/BOJ 2021. 9. 24. 18:30
https://www.acmicpc.net/problem/23030 23030번: 후다다닥을 이겨 츄르를 받자! 쿠기는 평소 지하철 최단 경로를 탐색하여 소요 시간을 알려주는 '후다다닥' 어플을 사용 중이다. 그러나 쿠기는 걸음이 너무 느려서 '후다다닥'이 알려주는 경로를 따라가면 항상 지하철이 떠 www.acmicpc.net 풀이 지문이 좀 길지만 간단하게 정리해보면 노선 N개가 있고, 각 노선내에서 이동하는 경우는 시간이 1이 걸림 환승역에서 다른 노선으로 환승할 때는 T의 시간이 걸림(사람마다 T가 다름) 으로 정리할 수 있습니다. 이동하는데 걸리는 시간이 1 또는 T 총 2가지가 있으므로 BFS는 불가능하고, 다익스트라를 사용하여 최단거리 탐색을 할 수 있게 됩니다. 역을 저장할 때는 (노선 번호..
-
[BOJ 23061, Python 3] 백남이의 여행 준비알고리즘/BOJ 2021. 9. 23. 14:39
https://www.acmicpc.net/problem/23061 23061번: 백남이의 여행 준비 1번 배낭이 담을 수 있는 무게는 20이고, 담을 수 있는 최대 가치는 34이므로 효율성은 1.7이다. 2번 배낭이 담을 수 있는 무게는 21이고, 담을 수 있는 최대 가치는 37이므로 효율성은 약 1.76이다. 3 www.acmicpc.net 알고리즘 학회 beans3142님의 풀이를 들음 C++은 오버플로가 문제던데 어디서 오버플로가 나는지 모르겠어서 정신 나갈 뻔하다가 파이썬으로 제출해서 통과함 출력문이 있는지 모르고 무지성으로 제출하다가 계속 틀렸음 ㅋㅋ 풀이 문제를 보자마자 냅색문제인 것을 알 수 있습니다. 일반적인 냅색문제랑 살짝 다른 점은 가방에 1개가 아닌 M개라서 이중에서 효율이 좋은 가..
-
[BOJ 2447, Python 3] 별찍기 - 10알고리즘/BOJ 2021. 9. 21. 13:12
https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 풀이 예제를 보면 $3^n \times 3^n$으로 된 정사각형에서 가운데가 텅 비어있고, $3^{n-1} \times 3^{n-1}$이 텅 비어있고, .... 이렇게 모든 정사각형에서 가운데가 텅 비어있는 정사각형을 그리는 것이 목표입니다. 그래서 분할정복을 사용하여 가운데를 공백으로 만들어주고 -> 이전 정사각형보다 세 배 작은 정사각형들의 가운데를 공백으로 만들어주..
-
[BOJ 5719, Python 3] 거의 최단 경로알고리즘/BOJ 2021. 9. 17. 11:44
https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 클래스 6을 취득했으니 이제 단계별로 풀어보기도 공부해야겠네요 풀이 P의 값이 여러가지이므로 최단경로를 구하는 알고리즘은 다익스트라를 생각해볼 수 있습니다. 거의 최단 경로는 최단 경로에 포함되는 모든 도로들을 제외한 도로로 이루어진 최단경로입니다. 최단 경로에 속하는 모든 도로들을 제외하려면 일단 adj 배열은 2차원 리스트로 하면 도로를 찾는데 O(N), 삭제를 ..
-
[BOJ 16282, Python 3] Black Chain알고리즘/BOJ 2021. 9. 16. 13:07
https://www.acmicpc.net/problem/16282 16282번: Black Chain n개의 블랙 고리가 일렬로 연결된 체인이 있다. 블랙 고리 하나는 무게가 정확히 1g 이다. 이 고리들을 이용하여 1g 부터 ng 까지 가능한 모든 무게를 생성하려고 한다. 이를 위해 고리를 일부 풀어 www.acmicpc.net 풀이 고리를 끊어내서 1g부터 ng까지 모든 무게를 생성해야 한다고 합니다. 이 문제는 보자마자 저울이라는 그리디 문제가 생각났습니다. 블랙 체인 문제는 직접 고리를 끊어내서 1g부터 ng까지 모든 무게를 표현할 수 있어야하는 것이고, 위 그리디 문제는 주어진 추들이 있을 때 이 추들을 사용해서 표현하지 못하는 최소 그램수를 출력하는 문제라 두 문제의 아이디어는 똑같습니다. ..
-
[BOJ 6549, Python 3] 히스토그램에서 가장 큰 정사각형알고리즘/BOJ 2021. 9. 15. 23:56
https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 이 문제는 다양한 풀이가 있는데 저는 세그먼트 트리를 이용한 분할 정복 풀이를 사용하였습니다. 먼저 arr[0] ~ arr[n-1]의 모든 구간을 잡은 뒤, 세그먼트 트리를 이용하여 가장 낮은 높이의 최솟값을 찾습니다. 그래서 (구간 길이) * (제일 작은 높이)를 구하여 답을 갱신시켜준다음, 이 가장 낮은 높이를 가진 인덱스를 기준으..
-
[BOJ 13977, Python 3] 이항 계수와 쿼리알고리즘/BOJ 2021. 9. 14. 14:02
https://www.acmicpc.net/problem/13977 13977번: 이항 계수와 쿼리 \(M\)개의 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net 참조 다양한 방법의 이항계수 알고리즘 : https://koosaga.com/63 이항계수 (nCr) mod p 계산하기 nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n.. koosaga.com 페..
-
[BOJ 1019, Python 3] 책 페이지알고리즘/BOJ 2021. 9. 13. 12:57
https://www.acmicpc.net/problem/1019 1019번: 책 페이지 첫째 줄에 0이 총 몇 번 나오는지, 1이 총 몇 번 나오는지, ..., 9가 총 몇 번 나오는지를 공백으로 구분해 출력한다. www.acmicpc.net 풀이 1 2 3 4 5 6 7 n = int(input()) arr = [0] * 10 for i in range(1, n+1): x = str(i) for j in range(len(x)): arr[int(x[j])] += 1 print(n, '-', arr) cs 이 코드는 O(N^2)로 답을 구하는 경우인데, 첫번째 자리수의 값을 제외한 나머지 값들을 9로 설정하고 확인해보면 규칙성이 나옵니다. 9 - [0, 1, 1, 1, 1, 1, 1, 1, 1, 1] ..