자료구조/알고리즘, 컴파일러

## 자료구조/알고리즘 ##

1. 배열과 LinkedList(연결 리스트)의 차이

배열은 입력된 데이터들이 메모리 공간에 연속적으로 저장되어 있는 자료구조입니다. index를 통한 접근이 용이하며 배열의 크기는 한 번 정한 이후 변경이 불가능합니다.

 

연결 리스트는 여러 개의 노드들이 순차적으로 연결된 형태를 갖는 자료구조입니다. 배열과는 다르게 메모리를 연속적으로 사용하지 않습니다. 

 

○ 장단점

*배열

- 인덱스를 통한 빠른 접근이 가능

- 삽입/삭제가 오래 걸림

- 배열 중간에 있는 데이터가 삭제되면, 공간 낭비 발생

 

*연결 리스트

- 삽입/삭제 용이

- 임의 접근이 불가능하여, 처음부터 탐색을 진행해야 함

 

○ 용도

배열: 빠른 접근이 요구되며, 데이터의 삽입과 삭제가 적은 경우

연결 리스트 : 삽입과 삭제 연산이 많고, 검색 빈도가 적은 경우

 

2. List와 Set의 차이

List는 중복을 허용하며, 중복된 데이터를 저장하고 순서를 유지하는 선형 자료구조입니다. Set은 중복을 허용하지 않으며 중복되지 않은 데이터를 저장하며 순서를 유지하지 않는 선형 자료구조입니다.

 

○ 용도

- 저장되는 데이터의 순서를 보장해야 한다면 List를 사용해야 합니다.

- List의 contains 실행 속도는 O(n)이지만, Set은 O(1)로 매우 빠르다는 특징이 있습니다.

탐색이 많다면 Set을 고려해볼 수 있습니다.

- 데이터가 많지 않다면 성능보다, 구조가 간단한 List를 고려해볼 수 있습니다.

- 중복을 허용하지 않는 Collection이 필요하다면 Set을 고려해볼 수 있습니다.

 

3. Hash Function, HashTable에 대해 설명

○ Hashing

- 데이터가 해시 함수를 거치는 과정

- 해시 함수를 사용해 Key값을 인덱스로 변환하는 과정을 해싱이라고 한다.

=> 해싱의 본질적인 의미는 각 데이터에 고유한 키값을 주는 것이다.

 

*Hash Function

임의의 길이를 갖는 데이터를 고정된 길이의 데이터로 변환시켜주는 함수

(사례 : 암호화 - 해시값을 통해 위변조 여부 판별하고, 무결성을 검증)

※ 참고 : 여러 데이터에 동일한 키값을 줄 수밖에 없는 경우가 발생하고, 이러한 해시충돌을 최대한 적게 만들어주는 해시함수가 좋은함수이다. 즉 키값을 고르게 만들어 내는 것이다)

 

정리 : 좋은 해시 함수는 연산이 빠르고, 충돌이 적고, 고르게 분포될 수록 좋은 해시함수이다.

 

*Hash Table

Key, value 형태로 데이터를 저장하는 자료구조입니다. Key를 받아 임의의 해시 함수를 통해 도출된 해시값을 배열의 index로 사용합니다. 이런 방식을 통해 O(1)이라는 아주 빠른 속도로 데이터에 접근할 수 있습니다. 

대표적으로 Python의 딕셔너리가 해시테이블로 구현되어 있습니다.

 

4. Stack, Queue의 차이점

스택은 마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 LIFO(Last In First Out)방식의 자료구조 입니다.

스택의 사용 예시로는 웹 브라우저의 방문기록(뒤로가기), 실행 취소(undo) 등이 있습니다.

 

큐는 처음에 저장한 데이터를 가장 먼저 꺼내게 되는 FIFO(First In First Out)방식의 자료구조 입니다.

큐의 사용 예시로는 프린터의 인쇄 대기, 콜센터 고객 대기 시간 등이 있습니다.

 

5. Heap, 우선순위 큐(Priority Queue)에 대한 설명

우선 순위 큐(Priority Queue)는 들어간 순서에 상관없이, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조입니다.

우선 순위 큐는 배열, 연결 리스트, 힙으로 구현이 가능합니다.

이 중에서 힙(Heap)을 이용하여 구현하는 것이 가장 효율적입니다.

 

힙(Heap)은 완전 이진 트리의 종류로써 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조를 말합니다.

 

*힙(Heap)의 특징과 종류

느슨한 정렬 상태(반정렬 상태) 유지.

- 큰 값이 상위 레벨에 있고, 작은 값이 하위 레벨에 있다는 정도

- 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰(작은) 이진 트리

 

최대 힙(max heap)

- 부모 노드는 항상 자식 노드보다 크거나 같아야 한다

- 가장 큰 값이 루트 노드에 있다

- key(parent) >= key(child)

 

최소 힙(min heap)

- 부모 노드는 항상 자식 노드보다 값이 작거나 같아야 한다

- 가장 작은 값이 루트 노드에 있다

- key(parent) <= key(child)

 

6. DFS, BFS에 대한 설명

DFS, BFS 두 가지 모두 그래프를 탐색하는 방법입니다.

 

DFS는 깊이 우선 탐색이라고도 하며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘입니다. DFS는 재귀나 스택을 이용해서 구현하며, 구현할 때 어떤 노드를 방문했는지 검사를 해야 합니다(무한 루프 방지). 보통 모든 노드를 방문하고자 할 때, DFS를 이용합니다.

 

BFS는 너비 우선 탐색이라고도 하며, 가까운 노드부터 탐색하는 알고리즘입니다. 즉, 시작 노드에서 가까운 노드를 먼저 방문하고 멀리 떨어져 있는 노드를 나중에 방문하며 깊게 탐색하기 전에 넓게 탐색합니다. BFS는 DFS와 달리 재귀 함수로 구현할 수 없습니다. 대신 방문한 노드들을 차례로 저장한 꺼낼 수 있는 자료 구조인 큐를 사용합니다. BFS도 DFS와 마찬가지로 어떤 노드를 방문했는지 검사를 해야 합니다 (무한 루프 방지).

 

7. 정렬, 탐색에 대한 설명

*정렬

- 복수의 원소로 주어진 데이터를 정해진 기준에 따라 늘어놓는 작업입니다.

 

*탐색

- 복수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업입니다.

 

## 컴파일러 ##

1. 스크립트 언어와 컴파일 언어를 나열하고 차이점을 설명

스크립트 언어는 PHP, Javascript, Python이 대표적인 스크립트 언어입니다. 컴파일 언어는 C, C++, Go가 있습니다.

 

*스크립트 언어- 컴파일 언어에 비해 단순하고 쉬운 문법 구조를 가지고 있다.- 컴파일러 없이 명령어를 한줄씩 읽으면서 실행하기에 번역속도는 빠르지만 프로그램 실행시 매번 같은 코드를 번역해야 하기에 속도가 느리다.- 컴파일 과정이 없기 때문에 프로그램을 실행시켜야 오류를 알 수 있다. (사전에 오류 확인이 어려움)- 컴파일 과정이 없기 때문에 소스코드가 그대로 실행파일이 되어 메모리에 적재된다. 그 이후 런타임시 메모리가 명령어를 실행하기 위해 내부적으로 기계어로 변환하는 과정을 거친다.

 

*컴파일 언어- 문법적 제약이 많아, 스크립트 언어에 비해 사용이 어렵다.- 컴파일을 하기에 규모가 큰 프로그램인 경우 컴파일을 하는데 시간이 오래 걸린다.- 기계어를 통해 프로그램이 실행되기 때문에 프로그램의 소스코드가 유출되기 어렵다.- OS마다 기계어가 다르기 때문에 OS에 따라 작업을 다르게 해줘야 한다.- 컴파일러가 소스코드를 기계어로 변환시켜준다. 그 이후 기계어가 메모리에 적재된다.

 

 

*참고
https://living-only-today.tistory.com/233

https://hazel-developer.tistory.com/2

https://well-made-codestory.tistory.com/30

https://velog.io/@chayezo/%ED%9E%99-Heap

https://propercoding.tistory.com/110

https://prerain.tistory.com/22