[기술면접]자료구조 정리

kjsu0209.github.io/Tech-Interview/data-structure/ds

자료구조

1. 스택과 큐

- 스택, 큐 둘다 선형 자료구조이다.

- 스택은 선입후출LIFO 형식이고, 재귀 알고리즘의 작동 원리이다.

- 큐는 후입후출FIFO 형식이고, 넓이 우선 탐색에 사용된다.

- 큐는 스택 2개로 만들 수 있다. 큐에 들어온 값을 넣는 스택 a, dequeue 요청된 값을 넣는 스택 b를 구현한다.

- dequeue는 b가 비어있다면 a를 모두 pop하여 b에 넣은 후 b를 pop하면 된다. b가 비어있지 않다면 그냥 pop하면 된다.

a = []
b = []

for i in input:
    c = input('Command (I/D): ')
    if c == 'I':
        a.append(input())
    elif c == 'D':
        if len(b) == 0:
            while len(a) != 0:
                b.append(a.pop())
            print(b.pop())
        else:
            print(b.pop())

 

2. 배열과 연결 리스트의 장단점

- 배열은 인덱스로 순차적으로 메모리에 접근할 수 있으나, 메모리 길이가 정적이기 때문에 삽입, 삭제 등 변경이 비효율적이다.

- 연결 리스트는 노드와 링크를 구조화한 자료구조로, 메모리 저장 위치에 구애받지 않아 데이터 재구성 및 삽입, 삭제가 용이하다. 인덱스로 메모리 접근이 어려워 순차적으로 접근해야 해 탐색 속도가 느리다.

 

3. 연결 리스트에서 한번에 중간값을 찾을 수 있는 방법은?

Two-pointer를 사용하면 된다. 포인터 하나는 노드를 한개씩 탐색하고, 다른 포인터는 노드를 2개씩 탐색한다. 2개씩 탐색하는 포인터가 리스트의 끝에 도달할 때, 한개씩 탐색하는 포인터가 가리키는 노드가 중간값이다.

 

4. 원형 연결 리스트인지 확인할 수 있는 방법은?

Two-pointer를 사용하면 된다. 포인터 하나는 노드를 한개씩 탐색하고, 다른 포인터는 노드를 2개씩 탐색한다. 2개씩 탐색하는 포인터가 한개씩 탐색하는 포인터를 따라잡을때, 두 포인터는 같은 노드를 가리키게 된다. 연결 리스트에 loop가 발생하는 경우에서만 가능하다.

 

5. 1에서 100까지의 정수가 있는 배열에서 한개가 중복되었다. 어떻게 찾을까?

n(n-2)/2는 1부터 n까지의 수를 더한 값이다. 따라서 배열의 요소를 모두 더하고, 1에서 100까지 더한 값을 빼면 중복된 값을 알 수 있다.

 

6. 자바에서 문자열을 뒤집는 방법은?

StringBuffer가 가장 간단한 방법이다.

StringBuffer를 사용하지 않고는 재귀를 사용하면 된다. return할 때 인자로 받은 문자열의 1번 인덱스부터 마지막 인덱스까지 범위의 문자열을 재귀 호출하고, 그 return값의 뒤에 문자열의 0번 인덱스 문자를 붙이면 된다.

public void reverseString(String s){
    if(s.length <= 1){
        return s;
    }
    
    return reverseString(s.substring(1)) + s.charAt(0);
}

 

7. 이진 탐색 트리 설명

- 이진 트리를 이용한 자료구조로, 중위 순회를 통해 정렬된 값을 얻을 수 있다.

- 단점은 반정렬상태로, 부모-자식 관계에서만 대소 관계를 만족한다.

- 편향트리가 되었을 때, 최악의 경우 배열의 정렬과 다름없다.

- 이진 탐색 트리의 4가지 조건:

모든 노드의 값은 유일하고, 왼쪽 서브트리의 모든 값은 루트의 값보다 작아야 한다.

오른쪽 서브트리의 모든 값은 루트의 값보다 커야 한다. 서브트리도 이진 탐색 트리여야 한다.

- 탐색:

찾는 데이터와 노드의 값을 비교하여, 노드의 값이 크면 왼쪽 자식노드로 이동하고, 작으면 오른쪽 자식노드로 이동한다. 노드의 값이 같으면 탐색을 종료한다.

- 삽입할 때는 탐색과 같은 과정으로 적절한 삽입 위치를 탐색한 뒤 삽입한다.

- 삭제는 이진 탐색 트리의 조건을 위배하지 않도록 한다.

=> 삭제할 노드의 자식 노드가 있을 때!!

=> 1개 있을 때: 삭제할 노드의 자식노드와 부모노드를 연결한다.

=> 2개 있을 때: 중위 순회했을 때 바로 앞의 값과 뒤의 값으로 메꿔 넣는다. 앞의 값은 왼쪽 서브트리에서 가장 큰 값, 뒤의 값은 오른쪽 서브트리에서 가장 작은 값이다.

 

8. 해시 테이블에서 Collision발생 시 해결법

충돌(Collision)은 서로 다른 key값을 해시함수로 변경했을 때, 같은 해시값이 나올 경우 발생한다.

=> 체이닝(Chaining): 충돌이 발생한 레코드들을 연결 리스트로 연결한다.

=> 개방 주소법(Open Addressing): 충돌 발생 시 삽입 방법에 따라 다른 버켓(메모리)에 데이터를 삽입한다.

 1) 선형 탐색: 다음 빈 버켓에 삽입

 2) 제곱 탐색: 제곱만큼 건너뛰어서 삽입

 3) 이중해시: 한번 더 해시함수 적용

 

9. 그래프와 트리 차이점

- 그래프는 노드와 노드를 연결하는 간선을 모아 놓은 자료구조이다.

- 트리는 그래프의 일종으로, 순환되지 않는 방향그래프이다.

- 트리는 계층 구조를 가진다. 루트 노드를 제외한 자식노드는 한 개의 부모노드만 가진다.

- 그래프는 네트워크 구조를 가진다. 부모-자식 노드 간의 개념이 없다.

- 그래프에서는 노드 간 다양한 경로를 구할 수 있지만, 트리는 하나의 경로만 가진다.

 

10. 우선순위 큐 구현방법 설명

우선순위 큐는 데이터들이 우선순위를 가지고 있고, 우선 순위가 높은 데이터가 먼저 나가는 힙 구조이다. 배열로 구현할 수 있다.

- 배열의 1번째 인덱스부터 사용한다.

- 왼쪽 자식의 인덱스 = 부모 인덱스*2

- 오른쪽 자식의 인덱스 = 부모 인덱스*2 +1

- 부모 인덱스 = 자식 인덱스 / 2

- 삽입: 마지막 노드에 삽입. 힙의 성질을 유지할 때까지 부모노드와 교환한다.

- 삭제: 루트 노드가 삭제된다. 마지막 노드를 루트 노드에 위치시킨 후, 제자리를 찾을 때까지 자식노드와 비교해가며 교환한다.