처리중입니다. 잠시만 기다려주세요.
TTJ 코딩클래스
정규반 단과 자료실 테크 뉴스 코딩 퀴즈
더보기
인사이트 FAQ 유튜브 카페

로그인

| 비밀번호찾기

추가 정보 입력

서비스 이용을 위해 휴대전화 번호를 입력해주세요.

회원가입

무료 회원가입 가입비 없이 무료로 가입할 수 있습니다

이미 계정이 있으신가요?

비밀번호 찾기

퀴즈 / 알고리즘 / 문제

알고리즘에서 '분할 상환 분석(Amortized Analysis)'에서 동적 배열(ArrayList)의 push 연산이 평균적으로 O(1)인 이유는?

어려움 freeCodeCamp
보기 및 정답
A 대부분의 push는 O(1)이고, 가끔 발생하는 배열 확장(O(n))의 비용이 이전 n번의 O(1) 연산에 분산되기 때문이다
B 동적 배열은 초기 할당 시 항상 충분히 큰 빈 공간을 미리 확보해 두기 때문에 배열 확장이 발생하지 않는다
C 동적 배열은 내부적으로 해시 테이블을 사용하여 각 원소의 저장 위치를 관리하기 때문에 삽입 연산이 항상 O(1) 시간에 수행된다
D 동적 배열은 내부적으로 연결 리스트로 구현되어 있기 때문에 끝에 새로운 노드를 추가하는 연산이 O(1)이다

해설

동적 배열은 공간이 부족하면 보통 2배 크기의 새 배열을 할당하고 복사합니다(O(n)). 하지만 이 확장은 n번 삽입 후에 발생하므로, 총 비용을 모든 삽입에 나누면 각 push의 분할 상환 비용은 O(1)이 됩니다. 이것이 '분할 상환 O(1)'이라 불리는 이유입니다.

코딩, 제대로 배우고 싶다면?

개념 확인은 퀴즈로, 실력은 실전 프로젝트로.
투더제이 코딩클래스에서 시작하세요.

정규반 살펴보기

관련 문제

'투 포인터(Two Pointer)' 알고리즘 기법이란?
알고리즘
트라이(Trie) 자료구조의 용도로 올바른 것은?
알고리즘
선택 정렬(Selection Sort)의 동작 방식은?
알고리즘
알고리즘에서 '최소 스패닝 트리(MST, Minimum Spanning Tree)'란?
알고리즘
'팬윅 트리(Fenwick Tree, Binary Indexed Tree)'의 주된 용도는?
알고리즘