1주차 - Array 배열 공부 [코딩 인터뷰 공부]

Array / 어레이 / 배열

 

Array의 value 들은 인접한(연속적인) 메모리에 저장됩니다. 그러기에 Array에서는 요소와 요소의 위치(index)가 주 고려 대상입니다.

언어마다 Array가 쓰이는 방법이 달라 time complexity에 각기 다른 영향을 미치는데, 요즘의 프로그래밍 언어(High-level language)들은 크기가 dynamic 하여 크기를 정의할 필요가 없는 반면 초기 프로그래밍 언어(Low-level language)들은 array를 생성하기 전에 크기를 정의해야 했습니다. 요즘의 프로그래밍 언어(Python, JavaScript, Ruby...)등이 상대적으로 인터뷰에서 쉬운 이유이기도 합니다.

 

Array는 자료 구조에 있어서 기본이기 잘 배워둬야겠습니다.

 

코딩 인터뷰 계획 - 무엇을 어떻게 공부할까 [코딩 인터뷰 공부]

 

 

Array 의 장점

다수의 요소를 하나의 변수에 저장할 수 있습니다.

index 가 있는 한 요소에 빠르게 접근 할 수 있습니다.

 

Array 의 단점

Array의 중간에 요소를 추가하거나 제거할 땐 느립니다. Array의 요소를 제거하거나 추가하는 원리는 array 의 끝을 기준으로 요소를 제거하거나 이동(shift)을 합니다.

특정 언어(대게 초기 언어들)는 array 의 길이를 정의해야합니다. 길이가 정해져 있는 만큼 요소를 추가한다면 새로운 array를 배정하는 식으로 길이를 늘려야합니다. 새 array 를 만들고 기존 array 의 요소들은 옮기는 것은 O(n) 시간이 걸립니다.

 

시간 복잡도 Time Complexity

Access O(1)

Search O(n)

Search (Sorted Array) O(log(n))

Insert O(n)

Insert (끝에다가) O(1)

Remove O(n)

Remove (끝에다가) O(1)

 

Big o Cheatsheet - Data structures and Algorithms with thier complexities - Varun N R

 

시간 복잡도, 공간 복잡도는 함수의 개념으로 이해하면 되는데, 곧 자세히 다뤄보려 합니다.

 

인터뷰에서의 Array

Array 안에 중복 요소들이 있는지 파악하고 문제를 쉽게 만드는지 어렵게 만드는지 고려 생각해보기

Array를 자르거나(slicing) 연결(concatenating)하면 O(n) 시간이 걸립니다.

 

Corner cases

Empty sequence

Sequence with 1 or 2 elements

Sequence with repeated elements

Duplicated values in the sequence

 

* Sequence 는 '순차적인 요소들의 집합' 정도의 개념으로 이해하기

Array 는 자료구조의 구성 중 하나이며 Sequence 라는 개념에 포함되어있습니다.

 

기술 Techniques

Sliding window

Two pointers

Traversing from the right

Sorting the array

Precomputation

Index has a hash key

Traversing the array more than once

 

필수 리트코드(LeetCode) 문제들

Two Sum

Two Sum - LeetCode

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

Product of Array Except Self

Product of Array Except Self - LeetCode

Maximum Subarray

Maximum Subarray - LeetCode

 

필수 리트코드(LeetCode) 문제 답

1주차 - 1.Two Sum LeetCode 리트코드 필수 문제 [코딩 인터뷰 공부]

1주차 - 1.Two Sum LeetCode 리트코드 필수 문제 [코딩 인터뷰 공부]