Java 웹/서버 개발자 면접 질문(알고리즘)

2019. 12. 12. 18:08

1. array, linked list

배열 : 데이터를 물리적 주소에 순차적으로 저장, 인덱스를 가지고 있으며 특정 데이터에 바로 접근할 수 있어 속도가 빠르다

연결리스트 : 데이터를 저장할 때 데이터 + 다음 데이터 물리적 주소까지 같이 저장 / 첫 노드 부터 원하는 노드까지 링크를 따라가야 접근 가능하기에 접근 속도는 떨어짐

속도 : 데이터에 대한 접근 속도 (배열 > 연결리스트)
- 배열 : index 만 있으면 O(1) 접근
- 연결리스트 : 최소 한 번은 리스트를 순회하여야 하므로, O(n)에 접근
데이터 삽입 속도 : 경우에 따라 다르지만(전체적으로 배열 < 연결리스트)
- 배열에 공간이 많이 남아있고 맨 끝에 삽입 한다면 O(1)이 가능하지만 매우 드뭄
  - 배열은 중간, 맨 앞에 삽입 할 경우 데이터를 한 칸씩 미뤄야 하고
  - 데이터 삽입 시 모든 공간이 다 차버렸다면, realloc() 또는 새로이 할당하여 메모리 공간 확장 필요
- 연결리스트 : 어느 곳에 삽입하던지 O(n) 시간 접근
데이터 삭제 속도 : 경우에 따라 다르지만(전체적으로 배열 < 연결리스트)
- 위와 비슷하다
- 연결리스트의 경우 예외 조건 처리를 꼼꼼히 필요로 함
삽입 삭제가 빈번하다면 연결리스트의 , 이미 만들어진 구조에서 데이터 접근만 필요로 하면 배열

2. 버블 정렬

서로 인접한 두 원소를 검사하여 정렬하는 알고리즘(인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환)

특징
- 장점 : 구현이 매우 간단
- 단점 : 순서에 맞지 않은 요소를 인접한 요소와 교환 / 배열에서 모든 요소들과 교환해야 왼쪽 -> 오른쪽으로 이동 가능

3. 퀵 정렬

리스트 안에 있는 한 요소(피벗) 를 가지고 이를 기준으로 삼아 분할하고 분할된 부분 리스트 정렬 후
두 개의 정렬된 부분 리스트를 합하여 전체 리스트 한다
분할-> 정복 -> 결합

4. 힙 정렬

5. 합병 정렬

하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬 , 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법
분할 -> 정복 -> 결합

6. ArrayList<>란

: 배열의 확장판. 배열의 크기를 임의적으로 변화시킬 수 있음, list에 들어갈 데이터 타입 설정 가능

(add, remove, isEmpty, size, get, indexOf 등의 메소드가 있음)

7. hash란?

: 내부적으로 배열을 사용(HashTable)하여 데이터를 저장, 검색 속도가 빠름.

데이터 삽입/삭제시 기존 데이터를 밀어내거나 채우지 않고, 데이터와 연관된 고유한 숫자를 생성해 이를 인덱스로 사용.

8. equals와 HashCode?

(equals) 동일한 내용을 가진 객체인지를 비교

(hashcode) 동일한 객체인지 구별하기 위해 고유한 정수 값으로 출력

9. 스택과 큐의 차이

: (stack) Last in First out

-> 함수를 호출 할 때, 현재 함수에서 사용되는 값을 스택에 넣고, 작업이 끝나면 함수를 리턴하고 스택에 넣었던

값을 꺼내는 방식으로 동작

(Queue) First in First out

->프로세스 처리, CPU 관리, 프린터 큐 등에 사용

exp_blog