알고리즘 (3) 썸네일형 리스트형 두 수의 합 두 수의 합문제는 아래와 같습니다.https://leetcode.com/problems/two-sum/description/1. Two SumGiven an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1:Input: nums = [2,7,11,15], target = 9 O.. Map과 Deque 시간 복잡도 Map 시간 복잡도Map은 해시 테이블로 구현된 HashMap과 LinkedHashMap이 있습니다.Map은 키와 값을 하나의 쌍으로 저장하는 방식을 사용하고 엘리먼트 추가, 삭제, 조회 모두 O(1)이 소요되는 효율적인 자료형입니다. 물론 최악의 경우에는 키 충돌이 발생해 O(n)이 될 수 있지만 분할 상환 분석에 따라 시간 복잡도는 여전히 O(1)입니다. 하지만 기본적으로 HashMap은 입력 순서가 보장되지 않습니다. 이를 보완하기 위해 연결 리스트를 함께 사용하여 입력 순서를 유지한 LinkedHashMap이 있습니다.덕분에 한결 편리하게 Map을 사용할 수 있습니다. 심지어 코틀린에서는 Map의 기본 자료형은 LinkedHashMap을 사용하여 입력 순서를 보장합니다. Map을 사용한 연산의 시.. List 시간복잡도 지금부터 자바가 제공하는 자바 컬렉션 프레임워크의 리스트 시간 복잡도를 살펴보겠습니다. List를 대표하는 ArrayList와 LinkedList를 살펴보고, 빅오로 표현되는 시간 복잡도 말고도 실제 삽입과 삭제 속도도 측정해 비교해 보겠습니다. List 시간 복잡도 (ArrayList, LinkedList)연산ArrayListLinkedList인덱스 끝에 삽입O(1), 더블링 발생 시 O(n)O(1)인덱스 중간에 삽입O(n)탐색 O(n), 삽입 O(1)인덱스 끝에서 삭제 O(1)O(1)인덱스 중간에서 삭제 O(n)탐색 O(n), 삭제 O(1)조회O(1)O(n) ArrayList는 동적 배열이고, LinkedList는 연결 리스트로 구현되어 있기 때문에 위 표와 같이 같은 List 더라도 연산에 시간복잡.. 이전 1 다음
