자료구조와 알고리즘

Section 0. 개론

 

Big-O 표기법

• 알고리즘 효율성 판단: 객관적, 환경에 의존적이지 않음
• 1단계: 대략적인 계산 - 수행되는 연산의 갯수를 대략적으로 판단
• 2단계: 대장만 남긴다 - 영향력에 가장 큰 대표 항목만 남기고 삭제. 상수는 무시한다 (2N -> N)
• 읽는 법: O : Order of

 

Section 1 : 선형 자료 기초

 

배열, 동적 배열, 연결 리스트 비교

•  선형 자료구조: 순차적인 자료
  • 배열
  • 연결리스트
  • 스택, 큐
• 비선형
  • 트리
  • 그래프

 

• 배열 ( public int[] _data = new int[25]; ) 
  • 고정된 크기, 연속된 방
  • 장점: 연속성
  • 단점: 크기 변형 불가
• 동적 배열 ( public List<int> _data2 = new List<int>(); )
  • 유동적 크기, 연속된 방
  • 단점: 이사 비용, 중간 삽입/삭제
  • 동적 배열 할당 정책: 실제로 사용할 방보다 많이 여유분을 두고 (대략 1.5 ~ 2배 예약) 이사횟수를 최소화 가능 
  • 장점: 유동적인 계약 (방 추가 예약으로 이사 횟수 최소화 )
  • some methods and their big Os
    • Add : O(1) - 예외 케이스이다 (이사 비용을 무시하기 때문)
    • Index : O(1)
    • RemoveAt: O(N) - 최악의 경우를 고려한다
• 연결 리스트 ( public LinkedList<int> _data3 = new LinkedList<int>(); ) 
  • 연속되지 않은 방을 사용
  • 장점: 중간 추가/삭제 이점
  • 단점: N번째 방을 바로 찾을 수 없다. (임의 접근 (Random Access) 불가)
  • some methods and their big Os
    • Add: O(1)
    • Remove: O(1)
    • 중간/임의 index 접근하지 않는다: O(n)