본문 바로가기
728x90

알고리즘304

[python] 백준 2150 Strongly Connected Component https://www.acmicpc.net/problem/2150 문제 해결Kosaraju 알고리즘과 Tarjan 알고리즘 두가지 방법이 있다고 한다.하지만 하나 공부하기도 힘드므로 Kosaraju알고리즘을 공부하고 코드를 작성한다....Stack으로 DFS탐색을 하며 종료되는 노드를 append한 후 역방향 DFS를 통해 한번에 탐색되는 여러 정점을 SCC로 묶는 방법이 Kosaraju 알고리즘 방법이다. CODE import sysinput = sys.stdin.readlinesys.setrecursionlimit(10**6)def dfs(node, visited, stack): visited[node] = 1 for ne in graph[node]: if not visited.. 2024. 5. 9.
[python] 백준 2635 수 이어가기 https://www.acmicpc.net/problem/2635 2635번: 수 이어가기 첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다. www.acmicpc.net 문제 해결 첫 번째 수가 주어지고 두 번째수는 첫번째 수 이하인 부분들을 반복해나가면서 최적의 수를 찾아야한다. 사실 재귀를 사용해서 최대 길이를 찾는 것은 어렵지 않다. 하지만 문제를 잘 읽어야하는게 이후 나오는 수들은 0이여도 상관이 없다는 것이다.(음이 아닌 수이기 때문) 문제 난이도는 쉬운 편 CODE import sys input = sys.stdin.readline def dfs(A:list): global target, ans if A[-2] - A[-1] >= 0: A.append(A[-2] .. 2024. 4. 18.
[python] 백준 6986 절사평균 https://www.acmicpc.net/problem/6986 6986번: 절사평균 첫째 줄에 절사평균(N, K)를, 둘째 줄에 보정평균(N, K)를 각각 소수점이하 셋째 자리에서 반올림하여 둘째 자리까지 출력한다. 예를 들어 결과값이 9.667인 경우 9.67로, 5인 경우 5.00으로, 5.5인 경우 www.acmicpc.net 문제 해결 우선 풀의 과정 순서는 어렵지 않다. 리스트를 만들어서 절사평균은 앞에 k개, 뒤에 k개를 빼고 평균을 구하고, 보정평균은 앞에 k개, 뒤에 k개를 각각 k, -k-1 인덱스 값으로 변환시키고 평균을 구하면 된다. 하지만 93%쯤에서 계속 오답이 나오는데 이유가 파이썬 나누기를 하는 과정중에 소수점 일부 계산이 손실되어 잘못 답이 나올 수 있다고 한다. 그래서 .. 2024. 4. 17.
[python] 백준 2643 색종이 올려 놓기 https://www.acmicpc.net/problem/2643 2643번: 색종이 올려 놓기 첫 번째 줄에는 색종이의 장수가 주어진다. 다음 줄부터 각 줄에 색종이의 두 변의 길이가 주어진다. 두 변의 길이는 한 칸 띄어 주어진다. 색종이의 최대 장수는 100이고, 각 변의 길이는 1000보다 www.acmicpc.net 문제 해결 작은 것부터 쌓아 올려서 최대한 많이 쌓을 수 있도록 하면 된다. w, h가 구별되지 않으므로 두 변중 긴 변을 w, 작은 변을 h로 정렬한다. 각 색종이를 길이가 큰 것 부터 내림차순으로 정렬한다 하나씩 확인하면서 이전 것들 길이를 비교하면서 w, h 모두 더 길 때 dp[w][h] (가장 큰 색종이의 길이가 w, h일 때 쌓아올릴 수 있는 최대 개수) 를 dp[pw][.. 2024. 4. 8.
728x90