[Algorithm] 공간 복잡도
1. 공간 복잡도란? 프로그램을 실행시킨 후 완료하는데 필요로 하는 자원 공간의 양을 말한다. 공간의 복잡도를 결정하는 것으로 보통 배열의 크기가 몇인지, 얼마 만큼의 동적 할당인지, 몇 번의 호출을 하는 재귀함수 인지 등이 있다. 총 공간요구 = 고정 공간 요구 + 가변 공간 요구로 나타낼 수 있다. 2. 고정 공간, 가변 공간 고정 공간은 입력과 출력의 횟수나 크기에 관계없는 공간의 요구를 말한다. ex) 코드 저장 공간, 단순 변수, 변수, 상수 저장 가변 공간은 프로그램 실행 중에 요구되는 요소이다. ex) 배열 전달, 재귀 호출, 회귀 주소 함수 호출시에 할당되는 지역 변수들이나 동적 할당되는 객체들도 모두 공간이 필요한데, 특히 재귀함수의 경우 매 함수 호출마다 매개변수, 지역변수, 함수의 복..
[자료구조] DFS & BFS
0. DFS, DFS 학습 전 알아야 할 것 인접 행렬: 2차원 배열로 그래프의 연결 관계를 표현하는 방식 파이썬에서도 2차원 리스트로 구현한다. 연결이 되어 있지 않은 경우에는 논리적으로 정답이 될 수 없는 큰 값 중 999999999 등의 값으로 초기화해서 사용한다. INF = 999999999 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0,7,5], [7,0,INF], [5,INF,0] ] 인접 리스트: 리스트로 그래프의 연결 관계를 표현하는 방식, 모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. 인접 리스트는 연결 리스트를 사용하면 되는데, 연결 리스트의 경우 파이썬은 기본 자료형인 리스트 자료형이 append 등 메소드를 제공하기 때문에 단순히 2차원 리스..
