알고리즘 세션1

알고리즘

알고리즘의 요건

완정성과 명확성
입력과 출력
유한성: 유한한 단계 뒤에는 반드시 종료

배열

1차원 배열

2차원 배열

행과 열로 구별

int[3][3] a = new int
{
    { 1, 2, 3 },
    { 4, 5, 6 },
    { 7, 8, 9 }

}

Unity transform에 x좌표 y좌표,Z좌표 한번에 저장하는 배열로 이해하면 편할듯

가변배열

배열의 행마다 길이가 각 각 다름.

리스트

단일 연결 리스트

이중 연결 리스트
ex)LinkdList

배열과 리스트의 차이

배열

• 접근이 빠름
• 참조를 위한 추가 메모리 할당이 필요 없음
• 삽입 / 삭제 시 뒤에 요소들을 이동해야 해서 비효율적
• 크기 변경 불가
• 메모리 재할당 불가능

리스트

• 삽입 / 삭제 시 참조 관계만 수정하면됨(비교적 효율적)
• 메모리 재사용 가능
• 참조를 위한 메모리가 필요
• 배열보다 실행속도가 느리다

알고리즘 세션2

스택

후입 선출

큐

선입선출

프로그램 평가 기준

공간 복잡도
시간 복잡도

O(N)과 O(log N)의 구별

시간 복잡도 순서
O(1) < O(logN) < O(N) < O(NLogN) < O(N^2) < O(2^N) < O(N!)

정렬

버블 정렬
선택 정렬
퀵정렬