5. Data Structure

1. array vs linkedlist 비교해서 설명해 보세요

1) array

• 메모리를 연속적으로 할당한다.
• 동일한 데이터 타입을 연속적으로 저장할 수 있다.
• (찾기)탐색이쉽다.
• 고정된 크기를 가지고 있어서 배열의 처음이나 중간에서 원소를 넣고 빼기 어렵다.
• 탐색/정렬 에 용이하다.

2) linkedlist

• 메모리상에 원소들이 연속적으로 위치하지 않는다.
• 배열에 비해 데이터의 추가 /  삽입 이 용이하다.
• 배열에 비해 메모리를 더 효율적으로 쓸 수 있다.
• 특정 위치의 데이터를 검색하기 위해서 처음부터 끝까지 순회해야 한다.
• 추가/삭제 에 용이하다.

2. stack vs queue 비교해서 설명해 주세요

1) stack

• 먼저 들어간 게 나중에 나오는 First In Last Out or Last In First Out 구조
• 스택에 할당된 공간이 꽉 차면 더 이상 Push 할 수 없다.
• 아래 처럼 재귀 함수 실행 시 사용된다. 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조.

2) queue

• 먼저 들어간 게 먼저 나오는 First In First Out or Last In Last Out 구조
• 데이터가 나가는 위치는 가장 앞 / 들어오는 위치는 가장 뒤
• 원형 큐 / 우선순위 큐 등의 베리에이션 존재
• 한 번에 하나의 데이터만 처리가 가능
• 어떠한 작업 / 데이터를 순서대로 실행 / 사용하기 위해 대기시킬 때 사용

자세한설명: nomadkim880901.tistory.com/316

3. HashTable을 설명하고 사용 예를 말씀해 주세요

Key에 Value로 데이터를 저장하는 데이터 구조

 

• 어떠한 키와 값을 넣으면, 내부적으로 이 데이터를 분류하여 지정된 장소에 키와 값을 넣고, 키를 재 호출하면 값을 반환할 수 있다.
• 추가/삭제/탐색이 쉽고 빠르다.(해싱된 키 => 배열의 인덱스) 배열의 인덱스를 사용하여 검색
• 키에 대한 데이터가 있는지 중복확인이 쉽다
• key 값 => hash function(해싱) => 데이터 분류 후 정수 => 인덱스가 되어 저장됨.
• 크기가 정해져 있음(크기 지정 가능)
• *Hash function 과 **Hash collision

*Hash function

어떠한 값을 넣었을 때 정보를 암호화하거나 일련의 값으로 만들어 내는 것.

hashing? 가변 크기의 입력값(input key)에서 고정된 크기의 출력값(hash sum)을 생성하는 과정

• 배열의 크기 안에서 값이 나와야 함
• 언제든지 같은 값이 나와야 함
• 들어온 key를 저장할 수 없음

**Hash collision

같은 index가 나온 경우, collision이 발생한다.

Storage 의 해당 인덱스에 Bucket을 만들어 같은 인덱스를 갖는 key-value 들을 저장해 줄 수 있다.

 

Hash table 사용예

• 검색이 많이 필요한 경우
• 저장, 삭제, 읽기가 빈번한 경우
• 배열의 경우 데이터를 일일이 찾아가야하는 문제가 있어서 비효율적이기 때문이다.
• 캐시 구현시 (중복 확인이 쉽기 때문)

자세한설명: nomadkim880901.tistory.com/318

algorithm question

4. 54321 배열을 12345로 정렬 할 때 어떤 sort를 쓰겠는가. 왜?

https://yabmoons.tistory.com/250

5. random으로 배열된 숫자들이 있을 때 어떤 sort를 쓰겠는가 왜?

용도에 따라 다르지 않을까?

6. insertion sort가 일어나는 과정 설명

• 삽입 정렬
  • 한 번에 한 항목 씩 정렬 된 배열을 작성한다.
  • 1회전을 수행할 때마다 인덱스가 증가하며 해당 인덱스까지 요소들의 정렬이 끝난다.
• 시간 복잡도
  • 최선의 경우 : O(N)
  • 최악의 경우 : O(N^2)
  • 평균 : O(N^2)
• 장점
  • 안정적인 정렬 알고리즘이다.
  • 배열이 대부분 정렬되어 있는 경우에 매우 효율적이다
• 단점
  • 배열 안의 요소들의 이동 수가 많다.
  • 배열의 크기가 큰 경우 시간이 오래 걸린다.

자세한설명: gyoogle.dev/blog/algorithm/Insertion%20Sort.html

7. quick sort가 일어나는 과정 설명

1. 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.
3. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.

• 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다.

시간복잡도

• 최선의 경우(Best cases) : T(n) = O(nlog₂n)
• 최악의 경우(Worst cases) : T(n) = O(n^2)

참고: gyoogle.dev/blog/algorithm/Quick%20Sort.html

 

8. DFS vs BFS?

 

1. 깊이 우선 탐색 (DFS, Depth-First Search) : 최대한 깊이 내려간 뒤, 더이상 깊이 갈 곳이 없을 경우 옆으로 이동

출처 https://developer-mac.tistory.com/64

 

💡 깊이 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에

해당 분기를 완벽하게 탐색하는 방식을 말합니다.

 

예를 들어, 미로찾기를 할 때 최대한 한 방향으로 갈 수 있을 때까지 쭉 가다가

더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서

그 갈림길부터 다시 다른 방향으로 탐색을 진행하는 것이 깊이 우선 탐색 방식이라고 할 수 있습니다.

 

1. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택함

2. 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단함

3. 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느림

 

2. 너비 우선 탐색 (BFS, Breadth-First Search) : 최대한 넓게 이동한 다음, 더 이상 갈 수 없을 때 아래로 이동

 

출처 https://developer-mac.tistory.com/64

 

💡 너비 우선 탐색의 개념

루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법으로,

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법입니다.

 

주로 두 노드 사이의 최단 경로를 찾고 싶을 때 이 방법을 선택합니다.

ex) 지구 상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Sam과 Eddie사이에 존재하는 경로를 찾는 경우

 

* 깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모름

* 너비 우선 탐색의 경우 - Sam과 가까운 관계부터 탐색

 

3. 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 비교

 

출처 https://namu.wiki/w/BFS

 

DFS(깊이우선탐색)	BFS(너비우선탐색)
현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색	현재 정점에 연결된 가까운 점들부터 탐색
스택 또는 재귀함수로 구현	큐를 이용해서 구현

💡DFS와 BFS의 시간복잡도

두 방식 모두 조건 내의 모든 노드를 검색한다는 점에서 시간 복잡도는 동일합니다.

DFS와 BFS 둘 다 다음 노드가 방문하였는지를 확인하는 시간과 각 노드를 방문하는 시간을 합하면 됩니다.

 

N은 노드, E는 간선일 때

인접 리스트 : O(N+E)
인접 행렬 : O(N²)

일반적으로 E(간선)의 크기가 N²에 비해 상대적으로 적기 때문에

인접 리스트 방식이 효율적임

출처: https://devuna.tistory.com/32 [튜나 개발일기]