본문 바로가기
728x90

알고리즘/[python] 백준 BOJ316

[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] 백준 14582 오늘도 졌다 https://www.acmicpc.net/problem/14582 14582번: 오늘도 졌다 첫 번째 줄에는 9개의 정수가 주어지는데, 오늘 경기에서 울림 제미니스가 1회 초, 2회 초, ..., 9회 초에 낸 득점이 주어진다. 두 번째 줄에도 9개의 정수가 주어지는데, 스타트링크 걸리버스가 1회 www.acmicpc.net 문제 해결 제미나스가 초 공격이기 때문에 공격 시점에 이기고 있어도 역전패가 된다. 1회 초에 점수를 내게 된다면 무조건 역전패이다. accumulate 함수를 쓰면 간단하게 계산이 가능하다. CODE import sys input = sys.stdin.readline from itertools import accumulate if __name__ == "__main__": A =.. 2024. 4. 14.
728x90