그래프 초기화
안녕하세요. 선생님 덕분에 멋진 강의를 듣고 있는 학생입니다.이제 유형 1을 다 수강했는데, graph를 초기화할 때 보통 N의 개수가 적으면 불리언 2차원 배열로 선언하고, N의 개수가 많으면 빈리스트로 구성된 2차원 리스트로 선언하는데요.그냥 모든 문제에 빈리스트로 구성된 2차원 배열을 선언하지 않는 이유가 N의 개수가 적으면 배열로 선언하고 조회하는 게 더 빠르기 때문인지 여쭤봐도 될까요?
Answer 1
1
kyg8821님 안녕하세요 🙂
말씀하신 게 모두 맞습니다! 정리를 하자면 전부 빈 리스트에 append할 수 있습니다. 그래서 풀이를 통일하고 싶다면 이렇게 하는 게 제일 좋습니다!
물론 배열을 접근하는 게 성능이 좋지만, 그만큼 메모리 낭비도 발생하기 때문에 장/단점이 뚜렷합니다. 코딩테스트의 특성상 그 정도 메모리 낭비는 용납되기 때문에 더 빠른 솔루션이 더 좋다고 할 수 있지만, 제 경험 상 빈 리스트를 쓴다고 해서 timeout이 발생했던 적은 없어서 큰 차이는 없다고 봐도 될 것 같아요!
저는 강의를 하는 입장에서 여러 방식을 알려드리는 게 더 유익하다고 판단해서 여러가지 보여드렸는데, 솔루션을 통일하는 게 코딩 테스트 준비에 더 유리하기 떄문에 전부 빈 리스트에 append하는 방식을 쓰는 것도 좋을 것 같아요.
혹시 더 궁금하신 점이나 제 답변 중에 부족한 부분이 있으면 편하게 또 질문 주세요! 오늘도 공부하느라 고생 많으셨습니다 :)
itertools, sys같은 STL을 사용할 수 없는 경우 질문드립니다.(백준 11724)
1
26
1
백준 13565 침투 질문
1
88
2
침투/섬개수 질문
1
137
2
재귀함수 질문
1
142
1
백준 1260 (DFS 와 BFS) 프린트 위치 질문
1
120
1
촌수계산(백준 2644) 질문
1
183
2
다른 주제 강의
1
135
2
graph
1
194
1
재귀 함수 Depth
1
178
1
백준 DFS
1
213
1
[바닥장식][런타임에러] 질문 있습니다.
1
289
3
그래프 짤 때 adjacency matrix vs adjacency list
1
390
2
2644문제(촌수 구하기) 질문입니다.
1
249
2
DFS 문제 하나 여쭤봅니다!..
1
293
1
다음강의
1
241
1
알고리즘 수업 - 깊이 우선 탐색 2( 백준 24480) 번 질문
1
282
1
1260 문제 풀이에서는 함수 global로 변수 선언
2
209
1
PyPy3와 Python3
1
330
1
백준 2606
1
214
1
22479번 문제 런타임 에러 도와주세요 ㅠㅠ
1
437
1
11724 문제 질문
1
302
2
선생님! 바이러스 문제 코드 질문있어요오
1
271
2
질문있습니다!
1
329
1
2644 촌수계산 문제에 관한 질문
1
233
1