SW 전공
시험 직전 요약장
판단 기준과 헷갈리는 개념, 대표 예제를 짧게 확인하세요.
배열과 연결 리스트
원래 이론 →판단 기준
표를 좌우로 밀어 나머지 열을 확인하세요. 키보드: ←·→, Home·End
| 요구사항 | 더 적합한 구조 | 근거 |
|---|---|---|
| 인덱스로 반복 접근 | 배열 | 주소 계산 O(1), 지역성 우수 |
| 중간 삽입·삭제가 많고 필요한 링크를 이미 보유 | 연결 리스트 | 링크 수정 O(1) |
| 원소 수가 자주 늘지만 임의 접근도 필요 | 동적 배열 | 분할 상환 O(1) 끝 삽입과 O(1) 접근 |
| 양방향 이동·현재 노드 삭제 | 이중 연결 리스트 | 이전 링크를 직접 사용 |
헷갈리는 개념
표를 좌우로 밀어 나머지 열을 확인하세요. 키보드: ←·→, Home·End
| 연산 | 일반적인 비용 | 이유 |
|---|---|---|
| 인덱스 접근 | O(1) | 주소를 바로 계산한다. |
| 값 탐색 | O(n) | 정렬되지 않았다면 순서대로 확인한다. |
| 중간 삽입·삭제 | O(n) | 뒤쪽 원소를 이동해야 한다. |
| 끝 삽입 | 고정 배열은 조건부, 동적 배열은 분할 상환 O(1) | 공간이 부족하면 더 큰 배열로 재할당한다. |
대표 계산·예제
B[2..5][1..6]이 행 우선으로 저장되고 시작 주소가 2000, 원소 크기가 4바이트라 하자. 열 수는 6이므로 B[4][5] 주소는 다음과 같다.
예시·텍스트좌우로 이동해 전체 내용을 확인하세요. 키보드: ←·→, Home·End
2000 + ((4-2)×6 + (5-1))×4
= 2000 + 16×4
= 2064
열 우선이라면 행 수 4를 사용하여 2000 + ((5-1)×4 + (4-2))×4 = 2072가 된다.
내 최근 연습 오답
현재 브라우저의 연습 채점 기록에서 공개된 단원과 연결된 오답을 확인합니다.
오답 기록을 확인하고 있습니다.