정의 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 링크드 리스트는 필요할 때마다 데이터를 추가할 수 있는 구조 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 구조 노드: 데이터 저장 단위(데이터 값, 포인터)로 구성 포인터: 각 노드 안에서 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 데이터 + 다음 데이터를 가리키는 주소로 구성 장점 미리 데이터 공간을 할당하지 않아도 됨 단점 연결을 위한 별도 데이터 공간이 필요하므로 저장 공간 효율이 높지 않음 연결 정보를 찾는 시간이 필요하므로 접근 속도가 느림 중간 데이터 삭제 시 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요 이중 연결 리스트 양방향으로 연결되어 노드 탐색이 양쪽으로 모두 가능 한 노드에 데이터와 함께 이전 데이터 주소와 이후 데이터 주소를 가짐

정의 알고리즘의 실행 속도 반복문이 지배함 알고리즘 성능 표기법 빅 오 표기법 알고리즘 최악의 실행 시간을 표기 가장 많이/일반적으로 사용함 아무리 최악의 상황이라도 이 정도 성능은 보장한다는 의미이기 때문 오메가 표기법 최상의 실행 시간 세타 표기법 평균 실행 시간 Big-O 표기법 O(입력) 입력 n에 따라 결정되는 시간 복잡도 함수 O(1), O(logn), O(n), O(nlogn), O(n^2), O(2^n), O(n!) 등으로 표기함 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) 단순하게 입력 n에 따라 몇 번 실행이 되는지 계산하면 됨 n이 1이든, 100이든, 1000이든, 10000이든 실행을 O(1) 무조건 2회(상수회) 실행한다 O(n) n에 따라 n + 10번, 3n + 10번 등 실행한다 O(n^2) n에 따라 n^2번, n^2 + …

목적 같은 종류의 데이터를 효율적으로 관리하기 위해 사용 같은 종류의 데이터를 순차적으로 저장 index를 가짐 장점 빠른 접근 가능 단점 추가/삭제가 쉽지 않음 미리 최대 길이를 지정해야 함

정의 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 FIFO 방식으로 스택과 꺼내는 순서가 반대 enqueue: 큐에 데이터를 넣는 기능(데이터 추가) dequeue: 큐에서 데이터를 꺼내는 기능(데이터 삭제) 사용 멀티 태스킹을 위한 프로세스 스케줄링 방식을 구현하기 위해 많이 사용됨 큐의 경우에는 장단점보다는, 큐의 활용 예로 프로세스 스케줄링 방식을 함께 이해해 두는 것이 좋음

정의 데이터를 제한적으로 접근할 수 있는 구조 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조(LIFO) 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 push: 데이터를 스택에 넣기 pop: 데이터를 스택에서 꺼내기 장점 구조가 단순해서 구현이 쉽다 데이터 저장/읽기 속도가 빠르다 단점(일반적인 스택 구현 시) 데이터의 최대 개수를 미리 정해야 한다 저장 공간의 낭비가 발생할 수 있다