| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | |||||
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 |
- 파이썬
- 객체지향
- stop the world
- 알고리즘
- 플랫폼 클래스 로더
- AWS SAA-C03 합격후기
- dfs
- 스프링 컨테이너
- 딕셔너리
- BFS
- python list method
- Spring
- 자바
- 컴포넌트 스캔
- 부트스트랩 클래스 로더
- 백준
- aws saa-c03
- 심볼릭 레퍼런스
- 스프링
- python
- 어플리케이션 클래스 로더
- 코딩테스트
- 자료구조
- 클래스 로더 계층
- java
- 다이렉트 레퍼런스
- getreference
- 파이썬 리스트 메서드
- 2026 AWS SAA-C03
- 파이썬 문자열 메서드
- Today
- Total
목록2023/12/20 (2)
클라우드 낚시꾼
시간 복잡도와 공간 복잡도 문제 조건에 따르면 최대 노드의 개수는 10000 개, 최대 간선의 개수는 100000 개였다. 최악의 시간 복잡도가 O(110000)이고 시간 제한이 5초라서 시간 복잡도는 여유롭다는 판단을 내렸다. 하지만, 노드랑 간선의 개수가 1000개를 넘어가기에 DFS로 구현하면 RecursionError가 발생하기에 BFS로 구현하기로 마음먹었다. 자연어 알고리즘과 코드 1. 방향 그래프를 만든다. 2. 시작 노드를 1~n 순차적으로 설정하여 BFS 탐색을 한다. 3. 시작 노드를 x으로 설정하여 BFS 탐색을 할 때, 탐색된 노드의 개수가 해킹할 수 있는 컴터의 개수이다. 4. 3번의 정보를 리스트 a에 담고 max를 찾는다. 5. 리스트a에서 max를 가진 요소의 인덱스 탐색하고..
시간 복잡도와 공간 복잡도(런타임 에러 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 함수 내부에 부모 노드..