정보처리기사 필기
시험 직전 요약장
판단 기준과 헷갈리는 개념, 대표 예제를 짧게 확인하세요.
자료구조 선택과 배열·연결 리스트
원래 이론 →판단 기준
배열이 적합한 경우
- 인덱스를 이용한 조회가 매우 잦다.
- 원소 수가 비교적 안정적이다.
- 추가 링크 저장 공간을 줄이고 연속된 데이터를 순차 처리하려 한다.
연결 리스트가 적합한 경우
- 크기가 자주 변한다.
- 이미 알고 있는 노드 주변에서 삽입·삭제가 자주 발생한다.
- 양방향 이동이나 원형 순회가 필요하다.
단순히 “삽입·삭제가 많다”는 이유만으로 연결 리스트를 선택해서는 안 된다. 매번 삽입 위치를 처음부터 찾아야 한다면 탐색 비용 때문에 장점이 줄어든다.
헷갈리는 개념
표를 좌우로 밀어 나머지 열을 확인하세요. 키보드: ←·→, Home·End
| 연산 | 배열 | 연결 리스트 | 판단 조건 |
|---|---|---|---|
| 인덱스로 i번째 원소 접근 | O(1) | O(n) | 연결 리스트는 앞에서부터 순차 이동한다. |
| 정렬되지 않은 데이터의 값 검색 | O(n) | O(n) | 접근 O(1)과 검색 O(1)을 혼동하지 않는다. |
| 중간 삽입 | O(n) | O(1)* | * 선행 노드를 이미 알고 있을 때이며, 위치 탐색은 별도다. |
| 중간 삭제 | O(n) | O(1)* | * 단일 리스트는 선행 노드, 이중 리스트는 대상 노드를 알고 있을 때다. |
| 끝에 원소 추가 | 여유 공간이 있으면 O(1) | 꼬리 포인터가 있으면 O(1) | 배열 재할당이나 꼬리 탐색이 필요하면 O(n)이 될 수 있다. |
대표 계산·예제
배열 [10, 20, 30]에서 10 뒤에 15를 삽입하려면 20과 30을 오른쪽으로 이동해야 한다. 단일 연결 리스트라면 새 노드의 다음 링크를 기존 20 노드로 연결하고, 10 노드의 다음 링크를 새 노드로 바꾸면 된다. 링크 수정 자체는 O(1)이지만 10 노드를 값으로 찾아야 한다면 그 탐색에는 O(n)이 걸릴 수 있다.
내 최근 연습 오답
현재 브라우저의 연습 채점 기록에서 공개된 단원과 연결된 오답을 확인합니다.
오답 기록을 확인하고 있습니다.