윤성우의 열혈 자료구조 자료구조에 대한 기본적 이해 프로그램 = 자료구조(데이터 표현) + 알고리즘(데이터 처리) 자료구조가 결정되어야 그에 따른 효율적인 알고리즘 설계 가능하다. 알고리즘은 자료구조에 의존적이다. 알고리즘의 성능분석 방법 시간 복잡도(Time Complexity) - 속도 연산의 횟수를 통해 알고리즘의 빠르기 판단 데이터 수의 증가에 따른 연산횟수의 변화 정도 판단 탐색 알고리즘에서 시간 복잡도를 결정하는 핵심 연산자는 동등비교(==)이다. 공간 복잡도(Space Complexity) - 메모리 사용량 일반적으로 알고리즘 성능 평가할 때 메모리 사용량보다 실행속도에 초점을 둔다. 일반적인 알고리즘의 평가에는 논란의 소지가 거의 없는 '최악의 경우(worst case)가 선택된다. Big-Oh Notation은 '데이터 수의 증가에 따른 연산횟수의 증가패턴을 나타내는 표기법이다.' 또는 '데이터 수의 증가에 따른 연산횟수 증가율의 상한선을 표현한 것'이다. Recursive 하노이 타워 가장 작은 단위 패턴을 코딩하고 이를 일반화시키면 된다. 리스트 (List) 순차 리스트 (배열 기반) 배열 자료구조 특징인 Index를 통해서 어느 곳이든 바로 이동이 가능하다. 하지만, 프로그램 실행 전에 크기가 결정되어야 한다. 그리고 배열은 메모리의 특성이 정적이므로 메모리 길이 변경이 불가능하다. 정적인 배열은 필요로 하는 메모리의 크기에 유연하게 대처하지 못한다. 연결 리스트 (메모리 동적 할당 기반) 프로그램 실행 중에도 필요할때 마다 필요한 크기만큼 할당, 해제 할 수 있다. head, tail, cur의 구조체 node가 필요하므로 추가적인 메모리 할당이 필요하다. 자료구조 특성상 항상 처음부터 순차적으로 탐색 할 수