알고리즘
-
[BOJ 20047, C++] 동전 옮기기알고리즘/BOJ 2021. 9. 10. 10:45
https://www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 알고리즘학회 soo7652, kimtaehyun98님의 풀이를 들었음 투포인터로 접근 했었는데, N의 값이 작으면 걍 DP부터 생각해보는게 나은 것 같음. 참고로 투포인터를 사용하면 S[idx1] == T[idx2]일 때, idx1 += 1, idx2 += 1이 아닌 선택한 동전을 S에 넣고 idx2+=1을 하는 방법을 구현하기가 매우 어렵게 됩니다. 풀이 간단한 문제..
-
[BOJ 20041, Python 3] Escaping알고리즘/BOJ 2021. 9. 9. 11:40
https://www.acmicpc.net/problem/20041 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 풀이 문제에서 예시 그림을 제공하여 쉽게 이해할 수 있던 문제입니다. 잘 생각해보면 도둑은 상하좌우 네 방향중 한 곳으로 쭉 도망치는 것이 제일 효율적으로 도망치는 것을 알 수 있습니다. 왜냐하면 만약 도둑이 원래 가던 방향이 아닌 90도 직각으로 꺾어서 한 칸 이동하면 경찰도 그만큼 한 칸 더 이동하여 방어적으로 펼칠 수 있기 때문입니다. 경찰의 위치는 (x, ..
-
[BOJ 20046, Python 3] Road Reconstruction알고리즘/BOJ 2021. 9. 8. 18:31
https://www.acmicpc.net/problem/20046 20046번: Road Reconstruction 입력은 표준입력을 사용한다. 첫 번째 줄에 도시를 표현하는 격자의 행과 열의 크기를 각각 나타내는 두 개의 양의 정수 m, n (1 ≤ m, n ≤ 1,000, 1 < m×n)이 주어진다. 다음 m개의 각 줄에 격자의 각 www.acmicpc.net 풀이 일단 BFS를 생각해볼 수 있는데 도로의 비용이 0 또는 1뿐이라면 덱을 활용한 0-1 BFS를 생각해볼 수 있지만, 비용이 0, 1, 2로 총 세가지이기 때문에 BFS로는 풀기 힘들 것 같고, 다익스트라 알고리즘을 사용하면 됩니다. 참고로 문제에 (0, 0)의 값이 -1일 수도 있다는 점을 주의해주시면 됩니다. 코드 1 2 3 4 5 ..
-
[BOJ 20040, C++] 싸이클 게임알고리즘/BOJ 2021. 9. 8. 18:21
https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 문제만 읽으면 어떤 알고리즘을 써야하는지 이해가 잘 안되지만, 예제를 직접 그림으로 그려보면서 파악해보면 바로 유니온파인드(분리집합) 알고리즘을 사용해야 한다는 것을 알 수 있습니다. 사이클을 만들어지는 조건이 두 점의 번호가 같은 선으로 이어져 있을 경우니까요. n의 값이 500,000이기 때문에 파이썬은 sys.setrecursionlimit(500000)을 사용해야 아마 통과할 것..
-
[BOJ 20044, Python 3] Project Teams알고리즘/BOJ 2021. 9. 8. 18:17
https://www.acmicpc.net/problem/20044 20044번: Project Teams 입력은 표준입력을 사용한다. 입력의 첫 번째 행에는 팀 수를 나타내는 양의 정수 n(1 ≤ n ≤ 5,000)이 주어진다. 그 다음 행에 학생 si 의 코딩 역량 w(si)를 나타내는 2n개의 양의 정수가 공백으로 www.acmicpc.net 풀이 두 명씩 짝지어서 팀을 이루는데 이 팀들의 최솟값이 최대화가 되는게 목적입니다. 유명한 그리디 유형인데, 정렬을 하고 왼쪽에서 i번째 값과 오른쪽에서 i번째 값을 더해주면 최솟값의 합이 최대화가 됩니다. 코드 1 2 3 4 5 6 n = int(input()) w = sorted([*map(int, input().split())]) ans = 987654..
-
[BOJ 15906, Python 3] 변신 이동 게임알고리즘/BOJ 2021. 9. 8. 15:07
https://www.acmicpc.net/problem/15906 15906번: 변신 이동 게임 첫 줄에 2차원 격자의 크기 N(1≤ N ≤ 500), 일반 모드에서 변신 모드로 변신하는 데 소모되는 턴의 수 t(0 ≤ t ≤ 500), 목표 지점의 행과 열의 번호 r(1 ≤ r ≤ N), c(1 ≤ c ≤ N)가 주어진다. 다음 줄에 www.acmicpc.net 풀이 처음엔 BFS를 생각해볼 수 있는데 일반 이동은 (이동 횟수) + 1이지만, 변신모드로 변할 때는 (이동 횟수) + t가 되기 때문에 이걸 단순 큐에 넣어서 풀어보면 이미 방문한 경로가 다시 업데이트될 수도 있기 때문에 시간이 오래 걸리므로 다익스트라 알고리즘을 생각해볼 수 있습니다. 방문 방법은 visit 배열 2개로 나눠 각각 변신모..
-
[BOJ 22984, Python 3] 반짝반짝 2알고리즘/BOJ 2021. 9. 6. 11:43
https://www.acmicpc.net/problem/22984 22984번: 반짝반짝 2 국렬이는 지난 겨울에 수현이가 크리스마스 트리를 장식하고 남은 전구 스트립을 훔쳐서 자신의 방을 장식하려고 한다. 전구 스트립에는 전구 $N$개가 일(一)자로 설치되어 있다. 전구들은 전원 www.acmicpc.net 알고리즘학회에서 gojib2002님의 풀이를 들었음 풀이 일단 일반 전구가 켜질 확률을 p[i]라고 둘 때, p[i] 확률로 불이 들어오는 i번째 전구의 기댓값은 p[i]인 것을 알 수 있습니다. 전구가 켜진다면 1개가 켜지고, 켜질 확률이 p[i]이므로 1 * p[i] = p[i]인 것입니다. 그래서 일반 전구가 켜지는 모든 기댓값은 p[1] + p[2] + p[3] + .... + p[n]입니..
-
[BOJ 11689, Python 3] GCD(n, k) = 1알고리즘/BOJ 2021. 9. 6. 11:35
https://www.acmicpc.net/problem/11689 11689번: GCD(n, k) = 1 자연수 n이 주어졌을 때, GCD(n, k) = 1을 만족하는 자연수 1 ≤ k ≤ n 의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 GCD(n, k) = 1을 만족하는 자연수란 n과 k가 서로소 관계에 있다는 뜻입니다. 그래서 1부터 n사이에 n과 서로소인 개수를 구하는 공식은 오일러 피 함수가 있으므로 이 공식을 이용하여 개수를 찾아주면 되는 문제입니다. 자세한 설명은 https://ohgym.tistory.com/14 나 https://blog.chodaeho.com/posts/2021/eulers-totient-function/ 블로그를 참조하면 됩니다. 코드 1..