신입 개발자 직무면접 정리 - 알고리즘편

정렬

 정렬이란 오름차순 또는 내림차순처럼 기준을 잡고 데이터를 재배열하는 것을 말합니다.

 염두해야할 사항은 정렬할 데이터의 양, 메모리 상태, row data의 정렬된 정도.

 

선택 정렬

 첫 번째 원소에서 시작해 배열 전체를 훑으면서 가장 작은 키를 가지는 원소를 찾아 첫 번째 원소와 맞바꾼다.

 시간 복잡도: O(N^2)

 

삽입 정렬

 한 번에 한 원소씩 이미 정렬된 다른 원소들과 비교하여 새 원소를 제 위치에 삽입하는 방식. 이미 정렬된 리스트의 경우 시간 복잡도는 O(N), 평균적으로 O(N^2)

 안정적인 정렬방법으로 소량의 데이터의 경우 최적.

 

퀵 정렬

 데이터 집합 내에서 pivot값을 고릅니다. 이를 기준으로 두 개의 집합으로 나눠서 한 쪽 집합에는 피벗 값보다 작은 것만, 다른 집합은 큰 것만 넣습니다. 더 이상 쪼갤 부분 집합이 없을 때까지 각각의 부분집합에 대해 피벗 설정 and 쪼개기 작업을 반복 수행.

 N이 1이 나올 때까지 반복해서 2로 나누는 횟수, 즉 log(N), 시간 복잡도: O(NlogN)

그러나 피벗을 잘못 고른 경우는 시간 복잡도가 O(N^2).

 

병합 정렬

 데이터 집합을 둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬한 다음 부분집합을 다시 정렬된 형태로 합치는 방식.(분할 정복형 알고리즘)

 데이터가 10개이하일 때마다 삽입 정렬로 정렬하는 최적화 방법이 있다.

 평균 시간 복잡도: O(NlogN), O(N)수준의 메모리가 추가로 필요.

 

 

동적 계획법

 큰 문제를 여러 문제로 분할해서 최적해를 구하는 방식.

 

메모이제이션

 한번 계산한 결과를 재활용

 TOP-DOWN, BOTTOM-UP

 

비트마스킹

 비트 단위로 값을 보존. 방문체크하는데 사용.

 

투 포인터

 1차원 배열에서 Right, Left라는 두 점을 이용해 원하는 값을 얻는 형태. 연속된 값들을 이용해 푸는 문제에 사용.

 

슬라이딩 윈도우

 투 포인터와 유사하지만 차이점은 구간의 넓이가 동일하다는 점이 있습니다.

 전체 정보 중 이미 참조한 정보는 필요없다는 전제 하에 사용되기 때문에 메모리를 절약할 수 있다는 장점.

 

 

그리디 알고리즘

 부분 문제의 최적의 솔루션을 이용해서 기존 문제의 최적해를 구할 수 있는 방식.

 

 분할 정복

 부분으로 나누어서, 부분 문제를 정복하고 이를 통해 기존 문제를 해결

 

 

 

자료구조

List

순서가 있는 데이터의 집합, 중복이 허용.

인터페이스: ArrayList, LinkedList, vector

 

Set

순서를 유지하지 않고, 중복도 허용하지 않는 데이터의 집합.

인터페이스: HashSet, LinkedHashSet, TreeSet

 

Map

Key, Value쌍으로 이루어진 데이터의 집합

순서를 유지하지않고, key값은 중복을 허용하지않지만 value값은 중복을 허용.

인터페이스: HashMap, LinkedHashMap, TreeMap

 

foreach

for문 대신 사용되며 size를 건들필요없음, Stream의 인터페이스로 내부적으로 iterator가 적용.

foreach를 사용할 수 있는 자료구조는 iterable을 상속받은 클래스.

 

iterable

최상위 인터페이스로 Collection인터페이스에서 상속하고 있다.

추상메서드로 iterator를 갖고있다.

 

iterator

자료구조의 반복자 역할을 하며, hasNext(), next()라는 메소드를 오버라이딩.

 

generic

데이터 타입의 일반화

여러 타입의 값을 다룰 수 있는 변형이 가능한 자료구조

컬렉션을 사용할 때는 지정된 특정 타입만 가능.

E, T, V, K

 

generic와 non-generic차이점

 Generic은 데이터타입의 일반화를 의미하는 것으로 클래스나 메소드 내부에서 사용할 내부 데이터의 타입을 컴파일시에 미리 지정하는 방법이다. 이렇게 컴파일시 데이터 타입을 검사하면 클래스나 메소드 내부에서 사용되는 객체의 타입 안정성을 높일 수 있고, 반환값에 대한 타입 변환 및 타입 검사에 들어가는 노력을 줄일 수 있다.