주어진 문제를 조금 더 구체화하기 위한 질문들 - 파이썬

파이썬은 직관적인 문법 덕분에 많은 개발자들에게 사랑 받는 언어이지만, 그 만큼 깊게 생각하지 않으면 함정에 빠지기 쉬운 언어이다. 이 글에서는 파이썬 개발자들이 자주 놓칠 수 있는 핵심 사항에 대해 다시 생각해보고 효율적인 코드를 작성하는데 도움이 되었으면 하여 아래의 체크 리스트를 만들었다.

배열 (Array)

배열 구현시 놓치기 쉬운 것

• 배열 수정 여부 / 추가 공간 확보 가능 여부: 원래 배열을 수정해도 되는지, 아니면 백업을 위해 원래 입력을 유지한 채 새로운 공간을 할당해야하는지, 계산 속도 향상을 위해 추가 공간을 사용할 수 있는지
• 숫자의 특성 확인: 양수, 음수, 홀수, 짝수인지, null 값이 있을 수 있는지, 숫자의 범위는 얼마이고 다른 제약 조건이 있을지
• 배열에 담긴 데이터 확인: 정렬되어 있는지, 중복이 있는지, 정렬 가능한지, 정렬시 어떤 이점이 있을 수 있는지
• 예외 데이터 유형 확인: 테스팅을 위해 0 값, 빈 배열 등 예상하지 못한 데이터 유형을 생각하기
• 배열 크기 확인: 배열의 최대 크기는 얼마인지, 매우 큰 배열을 처리하도록 솔루션을 설계해야 하는지

배열 구현시 생각해야 하는 것

• 배열이 resizing cost가 높음에도 자주 사용되는 이유는 특정 elements에 접근할 때 효율성이 있기 때문이다.
• 반대로 크기 조정시에는 모든 요소를 새 배열에 복사해야하기 때문에 이 높은 비용을 감당할 때는 깊은 생각을 해야 한다.
• Linked list와 배열 중 어느 것을 사용해야하는지 구분해야 하는데, element의 삽입과 삭제가 빈번하다면 링크드 리스트가 유리하다. 특히 LRU Cache 시나리오(최근에 사용된 데이터를 앞으로, 오래전에 사용한 데이터는 삭제)에서는 링크드 리스트로 접근하는 자연스럽다.
• 동적 배열은 확장시 2배씩 증가하고 이로 인해 때때로 O(N)의 시간 복잡도가 발생할 수 있다. (Efficient Dynamic Arrays)

행렬(매트릭스)

면접에서 행렬을 직접 사용하는 경우는 드문 케이스이지만, 2차원 평면이나 격자에 위치해있는 정보를 추출하거나 어떤 방식으로 변환해달라는 요청을 받게 되는 경우가 있다.

• 2차원에서 게임 구현
• 수도쿠 풀기

행렬 구현시 놓치기 쉬운 것

• 지저분한 코드 - 행렬을 순회하고 조작하는 것은 순조롭지만, 행렬과 직접 상호 작용하는 함수들을 만들어 코드를 깔끔히 만들 필요가 있다. 인접 요소 확인, 행 또는 열 변경, 행 또는 열의 모든 요소 가져오기 등 필요한 함수를 작성하는 연습을 해보도록 하자. 그리고 요소 접근시 y, x 인덱스를 차례로 지정하는 것이 일반적이니 가독성 높은 코드를 작성하는 것이 좋다.
• 제자리에서 값 변경 - 단일 행렬을 사용해 값을 제자리에서 업데이트하도록 요구 받을 수 있는데, 주변 셀의 상태를 업데이트하면 정보 손실이 발생할 수 있기 때문에 업데이트시 새로운 값으로 라벨링하는 것도 방법이다.예를들어, 0, 1, 3, 4에 대한 각 의미를 부여한다. 0인 경우 이전에도 0 지금도 0, 1인 경우 이전에는 1 지금도 1, 3인 경우, 이전에는 1 현재는 0, 4는 이전에는 0 현재는 1 등으로 논리를 만들 수 있다.
• 공간 주의 - 행렬을 직접 사용하는 것은 시간과 공간 모두에서 많은 비용이 발생한다는 의미이다. 그래프를 행렬로 표현하는 것보다 해시와 같은 다른 방식으로 표현하는 것이 더 유리할 수 있다.
• 라이브러리 활용 - Pandas, Numpy, Torch 등을 이용해 저수준의 언어 성능의 이점을 가져가면 행렬에 매우 숙달되어있음을 간접적으로 보여줄 수 있다.

문자열

문자열 구현시 놓치기 쉬운 것

• 알파벳 문자만 있을 처리하는가? 영어나 숫자, 다른 특수문자나 기호가 올 가능성이 있는가?
• 구두점을 별도로 처리해야 하는가?
• 문자열이 비어 있거나 null이 될 수 있는가?
• 문자열은 항상 소문자/대문자인가? 대소문자가 섞인 문자열을 받을 수 있나?
• 문자열 인코딩에 대해 전혀 걱정할 필요가 없나? (UTF-8, ASCII 등)
• 해당 문자열이 메모리에 적합하게 할당 되어 있는가?

문자열 구현시 생각해야 하는 것

• String은 문자의 배열이며, 배열과 마찬가지로 문자열도 크기가 가변적이다. 즉, 문자열이 차지하는 공간과 해시를 생성하는데 걸리는 시간은 선형적이다.
• 대부분의 언어에서 문자열은 변하지 않는다. = 문자열 업데이트는 새로운 문자열을 다시 빌드하는 것과 같다.
• 문자열에서 나올 수 있는 문제들은 다양하다.

문자열의 시간복잡도 요약

	시간	공간
길이	O(1)	O(1)
인덱스 접근	O(1)	O(1)
문자열 결합	O(N)	O(N)
루프문	O(N)	O(1)
하위 문자열 검색 (contains, indexOf)	O(N*M)	O(1)
하위 문자열	O(M)	O(M)

집합(Set)

집합의 특성

• 유일성: 집합은 고유한 요소만 포함 = 집합 내 중복 요소 없음
• 순서없음: 집하은 요소에 고요한 순서가 없고 어떤 순서로든 나열될 수 있음
• 가변성: 집합은 가변적이어야 하며, 집합에 요소를 추가 또는 제거할 수 있음
• 부분 집함: 모든 요소가 다른 집합에도 포함된 경우 집하은 다른 집합의 부분 집합이 될 수 있음, 공집합은 모든 잡합의 근본적인 부분 집합임
• 동등성: 두 집합이 같은 요소를 포함하고 있으면 나열된 순서에 관계없이 두 집합은 동일

집합 연산

• 파이썬에서는 set1 = {1, 2, 3} 이나 set1 = ([1, 2, 3])으로 사용

연산자	설명	시간복접도	Set 1	Set 2	결과
union(set1, set2)	set1과 set2의 모든 요소를 ​​포함하는 세트를 반환	O(len(set1) + len(set2))	{1, 2, 3}	{3, 4, 5}	{1, 2, 3, 4, 5}
intersection(set1, set2)	set1과 set2에 모두 있는 요소만 포함하는 세트를 반환	O(min(len(set1), len(set2)))	{1, 2, 3}	{3, 4, 5}	{3}
difference(set1, set2)	set1에는 있지만 set2에는 없는 요소만 포함하는 세트를 반환	O(len(set1))	{1, 2, 3}	{3, 4, 5}	{1, 2}
symmetric_difference(set1, set2)	set1에는 있지만 set2에는 없는 요소만 포함하는 세트를 반환	O(len(set1) + len(set2))	{1, 2, 3}	{3, 4, 5}	{1, 2, 4, 5}
insertion(element, set)	set1 또는 set2에 모두 존재하지만, 두 개 모두 존재하지 않는 요소만 포함하는 세트를 반환	O(1)	4, {1, 2, 3}	-	{1, 2, 3, 4}
deletion(element, set)	집합에서 요소를 제거	O(1)	3, {1, 2, 3, 4}	-	{1, 2, 4}
lookup(element, set)	요소가 세트에 있으면 True를 반환하고, 그렇지 않으면 False를 반환	O(1)	3, {1, 2, 3, 4}	-	True
update(set1, set2)	set2의 요소로 set1을 업데이트	O(len(set2))	{1, 2}, {2, 3, 4}	-	{1, 2, 3, 4}

면접에서 집합(set)를 고려해야하는 경우

• 빠른 조회가 필요할 때 - 조회, 삽입, 삭제의 시간 복잡도에서 효율이 있고 중복 제거 작업을 수행할 때 요소를 추적할 때마다 이전에 본 요소를 다시 살펴봐야하는 경우 세트는 유리하다.
• 고유한 요소를 사용해야 할 때 - 정수, 문자열, 부동 소수점 등 유사한 요소 유형의 컬렉션이 존재하고 중복이 없도록 해야 하는 경우 세트를 사용하는 것이 좋다.

집합(set)을 사용시 흔히 하는 실수

• 세트 대신 해시 테이블을 사용하는 경우
  • 해시테이블의 경우에도 조회는 빠르지만 오버헤드가 큼, 그리고 키와 값이 모두 필요
  • 해시테이블 사용시 공간 복잡도 측면에서 두 배 이상이 사용될 것
• 리스트와의 혼동
  • 리스트의 경우 순서를 보장하지만 세트는 순서를 보장하지 않음
  • 순서를 보장해야하는 문제인지 아닌지 잘 살펴보아야 할 것
  • 마찬가지로 리스트에서는 인덱스로 조회하지만, 세트에서는 요소 자체를 검색하는 것이기 때문에 이 차이를 염두해두고 접근해야 함
• 요소의 유형이 혼합 사용되는 경우
  • 세트 작업시 요소들은 동일한 타입이어야 함
  • 종종 집합에 추가하는 요소의 데이터 유형을 확인하거나 요소의 캐스팅시 데이터 유형을 통일하는 것을 잊는 경우가 많음
  • 특히 목록에서 집합으로 변환할 때 일반적으로 많이 발생
  • 세트 사용시 명시적으로 캐스팅하는 습관을 들여야 함

세트 사용시 질문 또는 확인하면 좋은 것

• 세트에 들어갈 요소의 타입은 무엇이 좋을까요?
• 세트 작업시 최악의 경우를 염두해두고 면접관과 상의하여 사용할 것
• 값의 빈도나 위치를 알아야할 필요가 있을까요? => 있다고 한다면 해시테이블로 구현하는게 좋고, 기억할 필요가 없다면 세트로 충분할 것

해시 테이블 (Dicts)

인터뷰에서 해시 테이블을 사용하는 경우

• 시간을 빠르게 하기 위해 공간을 희생할 수 있는 상황
• 무언가의 빈도수를 세는 경우
• 데이터 추적 및 구성 - 문자, 인덱스, 노드 등의 항목 위치를 추적해야 하는 경우 (예: LRU 캐시 문제)
• 그래프를 표현해야 하는 경우 (정점을 키, 인접 리스트를 값으로) (간선 수가 가능한 총 간선 수보다 훨씬 적은 그래프를 처리할 때 특히 유용)
• Top Down 형태의 DP

구현을 위한 팁

• 파이썬의 collections 내에 Counter(리스트를 인풋으로 동일 단어나 글자 갯수 세기), defaultdict (초기값을 설정하기)를 활용하면 빠르게 구현할 수 있다. OrderedDict는 요소의 삽입 순서를 기억하는 유용한 기능이 있다.
• 키가 없어서 발생하는 Null을 처리해야 함
• 해시 불가능한 객체를 해시하려는 경우 (TypeError) - 파이썬의 리스트는 추후 변경 가능하기 때문에 해시가 불가함, 튜플은 변경 불가하기 때문에 튜플을 사용할 수는 있음
• 만약 튜플이 없는 경우 또는 급하게 처리해야하는 경우, 리스트를 정렬하고 정렬된 리스트를 문자열로 변환 후 해시한다 (O(N log N)). 

인터뷰시 물어보아야 하는 내용

• 해시테이블은 상수 시간 조회가 가능하지만, Set이나 Array가 작업을 수행할 수 있는지 상황을 파악해야 한다.
• 해시테이블 사용시 왜, 무엇을 할 것인지 잘 설명해야 하며, 상수 시간 조회에 대한 설명을 곁들여야 한다.

해시테이블에 대해 알아야 할 내용

• 해시테이블은 실제로는 배열이다.
• 충돌이 무엇이고 왜 문제인지 이해한다.
• 선형 프로빙, 이중 해싱, 오픈 체이닝, 2차 해싱 등 충돌을 처리하는 데 활용하는 전략을 이해한다.
• 좋은 해시 함수의 특징을 이해한다.
• 해시 테이블의 크기 조정시, 충동을 처리하고 다시 해싱해야하기 때문에 조회에 걸리는 시간이 상수 시간이 아닌 경우가 있다. 그 이유를 숙지하고 있으면 좋다.

이진트리 (Binary Trees)

인터뷰에서 이진 트리를 사용하는 경우

• 검색, 추가, 삭제 작업에 최적의 성능을 얻어야 할 때 활용 (O(log N))
• 데이터 구조를 탐색
  • 무작위 접근이 없으면서, 검색, 추가, 삭제, 인쇄 등 데이터를 처리할 수 있는 유일한 방법

이진트리의 대표적인 예: 데이터베이스 구현 등

• AVL 트리
• Red-Black Tree

이진트리에 대해 알아야할 내용

• 이진 트리의 특성상 효율적인 탐색 과정이 가능함 (이진 탐색 트리)
  • 트리의 각 노드에 대해, 해당 노드의 값은 왼쪽 서브트리의 모든 노드 값보다 크고 오른쪽 서브트리의 모든 노드 값보다 작음
  • 이진 탐색 트리 구현시, insertNode는 루트부터 탐색하여 올바른 위치를 재귀적으로 탐색한다. currentNode가 새 노드보다 크면 왼쪽으로 탐색하고, currentNode가 새 노드보다 작으면 오른쪽으로 탐색한다. 탐색은 동일한 로직을 적용하지만, 대상 노드가 발견되면 반환한다. (삭제도 마찬가지)
• 이진트리에서는 탐색 순서가 매우 중요
  • DFS (깊이 우선): preorder(전위), inorder(중위), and postorder(후위) traversal.
    • preorder(전위): 각 노드를 먼저 방문하고 그 다음 왼쪽 서브트리를 순회한다. 마지막으로 오른쪽 서브 트리를 순화한다. (왼쪽 먼저 순회 후, 그 다음에 오른쪽 순회)
    • inorder(중위): 오름차순 방문, 왼쪽 서브트리를 우선 탐색, 각 노드에서 항상 가장 작은 값을 향해 이동하고 중위 후속 노드를 반환
    • postorder(후위): 왼쪽 서브 트리에서 DFS를 수행 후 오른쪽 서브 트리에서 DFS를 수행한 후 마지막으로 현재 노드를 방문
      • 특정 순서로 트리의 노드를 삭제하는 데 자주 사용
      • 노드 참조를 쉽게 재구성할 수 있음
      • 기본적으로 방문한 각 노드를 즉시 출력하여 재귀 호출의 정확한 경로를 표시
  • BFS (넓이 우선): level-order traversal
    
    • BFS는 트리의 더 깊은 곳으로 이동하기 전에 같은 레벨에 속하는 각 노드를 방문하는 방식
    • BFS는 레벨 순회 방식을 유지하기 위해 스택이나 재귀 대신 큐 자료 구조를 사용
• 복잡도: 시간복잡도 - O(n), 공간복잡도 - O(n) 이고 n은 노드 수이다. 공간복잡도의 경우 재귀 수행시 호출 스택에 추가 공간이 필요하다.

인터뷰시 이진트리에 대해 물어봐야할 내용

• 보통 문제는 "주어진 트리에 대해 X를 실행하라" 형태로 나오는데, 문제를 접할 때 가장 중요한 것은 어떤 유형의 트리를 다루고 있는지 이해하는 것이다.
  • 이진 탐색 트리인지, 그냥 정렬되지 않은 트리인지 확인해야 한다.
  • 만약 데이터를 효율적으로 저장해달라고 한다면, 이진 탐색 트리를 구현하는 문제일 수 있다.
    • BST(이진탐색트리)의 삽입, 검색을 구현하는 것과 더불어 노드를 삭제하는 것을 구현하는 것도 나올 수 있다.
• 일반 이진 트리의 경우 다음과 같은 경우를 자주 물어본다.
  • 높이: 이진 트리의 높이를 계산 (가장 긴 경로)
  • 대칭 판별: 이진 트리가 대칭인지 판별
  • 최소 공통 조상(LCA): 두 노드의 최소 공통 조상 노드 찾기
  • 트리의 지름: 두 노드 사이의 가장 긴 경로 길이 계산하기
  • 경로 합: 이진 트리의 루트에서 리프까지의 경로가 주어진 합과 동일한지 확인
  • 직력화 및 역직력화: 이진 트리를문자열 표현으로 직렬화하고 다시 이진 트리로 역직렬화하기
• 주의해야하기 때문에 물어봐야 하는 것
  • "이진 트리" 인지, "이진 탐색 트리"인지를 확인할 수 있도록 잘 질문할 것
  • 이진탐색트리에서 탐색시 중복키를 고려하는 건지
  • 이진 트리의 논리는 재귀로 인해 복잡하다. 시각 자료를 활용할 수 있는지 조율할 것.
  • BFS와 DFS를 잘못 사용하지 않도록 명확히 알고 있어야 한다.
    • BFS는 두 노드 사이의 최단 경로 찾기에 유용
    • DFS는 정렬된 순서대로 노드를 탐색하는 경우 유용
  • 마지막 노드의 유효성을 검사해야한다. 이진 트리가 비어있거나, 널 노드가 있는 경우라면?
  • 재귀 구현시 반환 데이터에 대해서도 잘 고려해야 한다. (부모 -> 자식, 자식 -> 부모 순회가 가능하도록)
  • 재귀 순회에 대한 공간복잡도를 잊지말 것. 새로운 데이터 구조가 아니기 때문에 선형적으로 증가.