[코딩테스트 합격자 되기 04] 코딩 테스트 필수 문법 : Q&A

챕터 질문 답변

1. 리스트의 기본 개념

- 리스트의 개념에 대해 정리해주세요

순서가 있는 요소들의 집합. 가변적(mutable)인 데이터 타입으로 선언 이후 추가, 제거, 수정할 수 있다. 대괄호로 정의하며 각 요소를 쉼표로 구분함.

 

2. 리스트의 효율성

- 리스트의 임의 접근의 시간 복잡도는 무엇인가요?

인덱스를 이용한 임의 접근의 시간 복잡도는 O(1) 이다. 즉 상수 시간.

 

- 리스트의 맨 앞이나 중간에 데이터를 삽입할 때 시간 복잡도가 어떻게 달라지는지 설명해주세요.

삽입 위치 이후의 모든 요소들을 한 칸씩 뒤로 이동시켜야 한다. 이로 인해 시간복잡도는 O(n)이 된다. 리스트의 맨 뒤에 데이터를 삽입하는 경우는 O(n)의 복잡도를 가진다.

 

3. 튜플

- 튜플의 개념과 리스트와의 차이점을 설명해주세요.

튜플은 리스트와 비슷하지만 불변의 속성을 갖는다. 즉 한 번 정의된 튜플은 그 요소를 변경할 수 없다.

 

- 튜플을 사용하는 것이 적합한 경우는 언제인가요?

데이터의 불변성을 보장하고자 할 때, 데이터가 변경되지 않을 때.

 

4. 셋(Set)

- 셋의 개념과 특징을 설명해주세요.

중복되지 않는 요소들의 집합으로 "순서가 없고" 가변적인 자료형이다. 중괄호 {} 로 정의. 내부적으로 해시 테이블을 사용하기 때문에 효율적.

- 셋(Set)과 리스트의 차이점을 설명해주세요.

리스트는 중복을 허용하고 있지만 셋은 중복을 허용하지 않으며 순서가 없다.

리스트는 요소의 추가, 제거가 느릴 수 있지만 셋은 해시 테이블을 사용해 이러한 작업을 빠르게 수행.

 

5. 딕셔너리

- 딕셔너리의 개념에 대해 정리해주세요

딕셔너리는 키-값 쌍으로 데이터를 저장하는 자료구조이다.

 

- 딕셔너리 키로 사용될 수 있는 데이터 타입은 무엇이며, 그 이유는 무엇인가요?

딕셔너리의 키는 불변인 데이터 타입만 사용할 수 있다. (문자열, 숫자, 튜플 과 같은 타입)

딕셔너리가 내부적으로 해시 테이블을 사용하기 때문에 키는 해시 가능해야 하며, 불변성을 유지해야만 해시 값이 변하지 않는다.

 

- 딕셔너리에서 키-값 쌍을 삽입, 삭제하는 데 걸리는 시간 복잡도는 무엇인가요?

딕셔너리에 키-값 쌍을 삽입하거나 삭제하는 데 걸리는 시간 복잡도는 평균적으로 O(1) 이다. (해시를 기반으로 하기 떄문에 빠르다)

 

6. 성능 비교 문제

- 리스트에서 `pop(0)`과 `collections.deque.popleft()`의 동작 방식이 어떻게 다르며, 성능 차이가 나는 이유를 설명해주세요.

pop(0) 은 리스트의 첫 번째 요소들을 제거한 후 나머지 모든 요소를 앞으로 이동시키므로 O(n) 의 복잡도를 가진다.

반면 'collections.deque.popleft() 는 양방향 큐를 사용하여 첫 번째 요소를 제거하므로 O(1) 의 시간복잡도르르 가진다.

이 차이로 인해 deque.popleft()가 훨씬 더 효율적이다.

 

- 리스트와 셋(Set)에서의 데이터 추가 및 삭제의 시간 복잡도를 비교해주세요.

리스트에서의 데이터 추가(끝에 추가)와 삭제(끝에서 삭제)는 O(1)이지만, 특정 위치에서의 추가 및 삭제는 O(n)

반면 셋에서의 데이터 추가 삭제는 O(1)의 시간 복잡도를 가진다.

 

- 주어진 데이터에서 고유한 값을 찾아야 할 때, 리스트와 셋(Set) 중 어떤 컬렉션을 사용하는 것이 더 효율적인지 설명하고 이유를 서술해주세요.

고유한 값을 찾아야 할 때는 리스트보다 셋이 더 효율적 : 셋은 중복을 허용하지 않기 때문에 데이터 추가 시 자동으로 중복이 제거되며, 삽입 시간이 O(1)로 효율적이다.

 

7. 리스트 슬라이싱

- 리스트 슬라이싱이란 무엇이며, 슬라이싱을 사용해 리스트의 부분 배열을 얻는 방법을 설명해주세요.

리스트 슬라이싱은 리스트의 특정 부분을 추출하는 방법. 슬라이싱은 list[a:b]형태로 사용되며 a부터 b 인덱스 까지(b는 포함되지 않은) 요소들을 반환한다.

 

 

코딩 문제

 

문제 1: 리스트의 중복 제거 및 정렬

리스트 `lst`가 주어졌을 때, 리스트 내 중복된 요소를 제거하고 남은 요소들을 오름차순으로 정렬한 새로운 리스트를 반환하는 함수를 작성하세요.

def remove_duplicates_and_sort (lst) :
return sorted(set(lst))

 

 

 

문제 2: 딕셔너리 키의 빈도수 계산

문자열 리스트 `words`가 주어졌을 때, 각 단어가 리스트에 등장하는 빈도수를 딕셔너리로 반환하는 함수를 작성하세요.

def count_word_frequencies (words) :
    freq = {}
    for word in words:
        if word in freq:
            freq [word] += 1
        else :
            freq[word] = 1
    return freq

 

 

 

문제 3: 딕셔너리 키 존재 여부 확인

딕셔너리 `d`와 키 `key`가 주어졌을 때, 해당 키가 딕셔너리에 존재하는지 여부를 반환하는 함수를 작성하세요.

def key_exists (d, key) :
    return (key in d)

 

 

문제 4: 튜플의 요소 합

튜플 `tpl`이 주어졌을 때, 튜플 내 모든 요소의 합을 반환하는 함수를 작성하세요.

def sum_of_tuple(tpl):
    return sum(tpl)

 

 

 

문제 5: 리스트 슬라이싱으로 부분 리스트 추출

리스트 `lst`와 두 개의 정수 `start`, `end`가 주어졌을 때, 주어진 범위에 해당하는 부분 리스트를 반환하는 함수를 작성하세요. `start` 인덱스는 포함되며, `end` 인덱스는 포함되지 않습니다.

def slice_list(lst, start, end):
    return lst[start:end]