목록2023/12/20 (2)

클라우드 낚시꾼

[백준] 1325번 효율적인 해킹 BFS/DFS Python - pypy3

시간 복잡도와 공간 복잡도 문제 조건에 따르면 최대 노드의 개수는 10000 개, 최대 간선의 개수는 100000 개였다. 최악의 시간 복잡도가 O(110000)이고 시간 제한이 5초라서 시간 복잡도는 여유롭다는 판단을 내렸다. 하지만, 노드랑 간선의 개수가 1000개를 넘어가기에 DFS로 구현하면 RecursionError가 발생하기에 BFS로 구현하기로 마음먹었다. 자연어 알고리즘과 코드 1. 방향 그래프를 만든다. 2. 시작 노드를 1~n 순차적으로 설정하여 BFS 탐색을 한다. 3. 시작 노드를 x으로 설정하여 BFS 탐색을 할 때, 탐색된 노드의 개수가 해킹할 수 있는 컴터의 개수이다. 4. 3번의 정보를 리스트 a에 담고 max를 찾는다. 5. 리스트a에서 max를 가진 요소의 인덱스 탐색하고..
CodingTest/문제풀이 2023. 12. 20. 21:57
[백준] 11725번 트리의 부모 찾기 (Python) - RecursionError 발생

시간 복잡도와 공간 복잡도(런타임 에러 RecursionError) BFS, DFS의 시간 복잡도는 O(V+E)이다. 노드의 개수는 최대 100000개이고 간선의 개수는 99999개이기에 O(199999)가 최악의 시간 복잡도이다. Python3는 1초에 2000만번 연산이 가능하기에 O(199999)가 문제가 되지 않아 보이지만, Python3 기준 최대 재귀 깊이는 1000이기에 199999번 재귀호출 할 경우 RecursionError가 발생한다. 그래서 재귀 호출을 이용하는 DFS보다는 반복문 베이스인 BFS를 이용해서 이 문제를 해결해야 한다. 자연어 알고리즘과 코드 1. 입력을 받고 조건대로 Graph와 방문 테이블을 생성한다. 2. bfs 함수를 정의한다. 3. bfs 함수 내부에 부모 노드..
CodingTest/문제풀이 2023. 12. 20. 17:19
이전 Prev 1 Next 다음