자료구조 & 알고리즘(1)
이 글은 자료구조와 알고리즘을 '코딩 인터뷰'를 준비하기 위해서 정리한 글입니다.
이번 글은 배열과 문자열을 다루겠습니다.
(1) 배열과 문자열
- 배열이나 문자열에 대한 문제들은 서로 대체 가능합니다.
즉, 배열에 관한 것들은 문자열에 대한 문제로 바꿔 출제할 수도 있으며,
그 반대도 가능합니다.
(1-1) 해시 테이블(hash table)
- 해시 테이블은 효율적인 탐색을 위한 자료구조로서 키(key)를 값(value)에 대응시킵니다.
간단한 해시 테이블을 구현하기 위해선,
연결 리스트(linked list)와 해시 코드 함수(hash code function)만 있으면 됩니다.
(1-2) ArrayList와 가변 크기 배열
- 특정 언어에선 배열의 크기를 자동으로 조절 할 수 있습니다.
즉, 데이터를 덧붙일 때마다 배열 혹은 리스트의 크기가 증가합니다.
동적 가변 크기 기능이 내재되어 있는 배열과 비슷한 자료구조를 원할 때는
보통 ArrayList를 사용합니다.
ArrayList는 필요에 따라 크기를 변화시킬 수 있으면서도 O(1)의 접근 시간을 유지합니다.
이 자료구조를 잘하는 것은 면접에서 필수적입니다.
사용하는 언어에 관계없이 동적 가변 크기 배열 리스트에 대해서 익숙해져 있어야 합니다.
(1-3) Stringbuilder
- 생략
Q&A
(1) 배열과 문자열
Q. 배열과 문자열이 대체 가능하다는 점이 왜 중요한가?
A. 결국 배열에 대한 조작과 문자열에 대한 조작이 유사하기 때문입니다.
Q. 왜 배열에 대한 조작과 문자열에 대한 조작이 유사한가?
A. 배열은 복수의 자료에 관한 것이고, 문자열도 복수의 자료(문자)에 관한 것이라는 점에서
유사성이 있습니다.
Q. 복수의 자료에 관한 것이라는 점이 무엇입니까?
A. 결국 복수의 자료를 쉽게 관리하기 위한 자료구조라는 점입니다.
자료구조의 본질은 복수의 자료를 쉽고 편리하게 관리하기 위한 것입니다.
Q. 왜 복수의 자료를 쉽고 편리하게 관리하고자 합니까?
A. 결국은 사람이 특정 프로그램 혹은 시스템을 효율적으로 이용 및 관리하기 위함입니다.
(1-1) 해시 테이블(Hash table)
Q. 연결 리스트란 무엇인가?
A. 연결 리스트는 차례로 연결된 노드를 표현해주는 자료구조입니다.
Q. 왜 해시 테이블 구현에 연결 리스트를 활용하는가?
A. 해시 테이블은 다음과 같은 순서로 구현됩니다.
(1) 키의 해시 코드를 계산한다.
(2) 계산한 해시 코드를 이용해 배열의 인덱스를 구한다.
(3) 배열의 각 인덱스에는 키와 값으로 이루어진 연결 리스트가 존재한다.
키와 값을 해당 인덱스에 저장한다.
즉, 배열 인덱스와 특정한 값을 대응시켜주기 위해서 연결 리스트가 필요합니다.
Q. 왜 배열 인덱스와 특정한 값을 대응시켜주기 위해서 연결 리스트가 필요한가?
A. 하나의 배열 인덱스에 그 배열 인덱스에 저장되는 여러 개의 자료들을 연결해줘야 하고,
그러기 위해서는 연결 리스트가 필요합니다.
또한 연결 리스트를 이용하면 충돌에 대비할 수 있습니다.
Q. 왜 하나의 배열 인덱스와 여러 개의 자료들을 연결해줘야 하는가?
A. 자료의 효율적인 검색을 위해서입니다.
Q. 연결 리스트를 이용하면 충돌에 대비할 수 있다는 것이 무엇인가?
A. 서로 다른 두 개의 키가 같은 해시 코드를 가리키거나,
서로 다른 두 개의 해시 코드가 같은 인덱스를 가리키는 경우를 말합니다.
연결 리스트를 통해 충돌을 예방할 수 있습니다.
충돌이 자주 발생한다면, 최악의 경우 수행 시간이 O(N)이 되지만,
충돌을 최소화하도록 잘 구현한다면 탐색 시간은 O(1)입니다.
Q. 왜 충돌을 최소화해야 합니까?
A. 충돌은 자료의 효율적인 검색을 방해하기 때문입니다
- 이 글의 내용은 '코딩 인터뷰 완전 분석'을 참조했습니다.
