cs 메모장

2024-06-24 면접대비질문 / char와 string/ 시간복잡도 / 동적 프로그래밍/ 버블정렬/ 선택정렬 / 삽입정렬 / 힙정렬 / 병합정렬/ 퀵정렬 / 정렬알고리즘의 따른 시간복잡도 / 재귀 알고리즘 / 허프만 코딩

nakgopsae 2024. 6. 24. 14:39

char와 string이 나누어져있는 이유는?

char 는 개별문자 string은 개별문자들의 배열이며 사용용도가 다르고 메모리 효율성을 고려해 나누어져있습니다

시간복잡도에 대해 설명 하세요

시간복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 걸리는 시간을 입력 크기에 대한 함수로 표현한 것입니다
알고리즘의 효율성을 표현할수 있으며 다음과 같은  빅오표기법으로 표현됩니다 

O(1): 상수 시간 복잡도, 입력 크기에 상관없이 일정한 시간이 소요됨.
O(log n): 로그 시간 복잡도, 이진 탐색 같은 알고리즘에서 나타남.
O(n): 선형 시간 복잡도, 입력 크기에 비례하여 시간이 증가.
O(n log n): 선형 로그 시간 복잡도, 효율적인 정렬 알고리즘에서 나타남 (예: Merge Sort, Quick Sort).
O(n^2): 이차 시간 복잡도, 중첩 루프가 있는 알고리즘에서 흔함 (예: Bubble Sort, Selection Sort).
O(2^n): 지수 시간 복잡도, 주로 재귀 알고리즘에서 나타남 (예: 피보나치 수열).

동적프로그래밍이란?

동적프로그래밍이란 문제를 작은 하위문제로 나누어 해결한 후 그 결과를 저장하여 같은 문제를 반복적으로 풀지 않도록 하는 알고리즘입니다

동적 프로그래밍의 기본아이디어

문제를 작은 하위 문제로 나누기:원래 문제를 해결하기 위해 작은 문제들로 나눕니다

하위 문제의 결과 저장하기 : 각 하위 문제를 해결할 때 그 결과를 저장하여 같은 하위 문제가 다시 필요할 때 계산을 반복하지 않도록 합니다 이를 메모이 제이션이라고 합니다

저장된 결과를 이용하여 문제 해결 : 저장된 하위 문제들의 결과를 조합하여 원래문제의 해를 구합니다

DP의 두가지 방식

Top-Down (Memoization): 재귀적으로 문제를 푸는 도중 중복되는 결과를 메모리에 저장하여 나중에 사용.

Bottom-Up (Tabulation): 작은 하위 문제부터 풀어나가며 결과를 표에 저장하고, 이를 기반으로 최종 문제를 해결

버블 정렬이란?

버블 정렬(Bubble Sort)은 인접한 두 요소를 비교하여 필요시 교환하는 과정을 반복하여 배열을 정렬하는 알고리즘입니다. 과정은 다음과 같습니다

1. 첫 번째 요소와 두 번째 요소를 비교하여 순서가 맞지 않으면 교환.
2. 두 번째 요소와 세 번째 요소를 비교하여 순서가 맞지 않으면 교환.
3. 배열 끝까지 이 과정을 반복.
4. 한 번의 패스 후, 가장 큰 요소가 배열의 끝에 위치.
5. 배열이 정렬될 때까지 이 과정을 반복.
6. 시간복잡도: 최악, 평균 모두 O(n^2).

//어떤때 써야할까 - 큰배열에서 성능이 떨어짐

선택 정렬이란?

선택 정렬(Selection Sort)은 배열에서 가장 작은 (혹은 큰) 요소를 찾아 맨 앞 요소와 교환하는 과정을 반복하여 정렬하는 알고리즘입니다. 과정은 다음과 같습니다:

1 배열에서 최소값을 찾아 첫 번째 요소와 교환.
2 두 번째 요소부터 배열 끝까지 최소값을 찾아 두 번째 요소와 교환.
3 배열 끝까지 이 과정을 반복.
시간복잡도: O(n^2).

삽입 정렬이란?

삽입 정렬(Insertion Sort)은 배열의 요소를 하나씩 비교하여 올바른 위치에 삽입하면서 정렬하는 알고리즘입니다. 과정은 다음과 같습니다: 

1 두 번째 요소부터 시작하여 이전 요소들과 비교.
2 비교한 요소들이 정렬된 상태를 유지하도록 삽입.
3 배열 끝까지 이 과정을 반복.
4 시간복잡도: 평균, 최악 모두 O(n^2). 최선의 경우 (이미 정렬된 경우) O(n).

힙 정렬이란?

힙 정렬(Heap Sort)은 힙 트리를 이용하여 정렬하는 알고리즘입니다. 과정은 다음과 같습니다:

1 주어진 배열을 힙 트리로 변환 (Max-Heap 또는 Min-Heap).
2 힙의 루트 요소 (가장 큰 요소)를 배열의 끝으로 이동.
3 힙 크기를 줄이고 남은 요소들로 다시 힙을 구성.
4 배열이 정렬될 때까지 이 과정을 반복.
시간복잡도: O(n log n).

//안정적이다

병합 정렬이란?

병합 정렬(Merge Sort)은 분할 정복(Divide and Conquer) 기법을 사용하는 정렬 알고리즘입니다. 과정은 다음과 같습니다:

1 배열을 절반으로 나눔.
2 각 절반을 재귀적으로 병합 정렬.
3 두 정렬된 절반을 합쳐서 하나의 정렬된 배열로 만듦.
4 시간복잡도: O(n log n).

퀵 정렬이란?

퀵 정렬(Quick Sort)은 분할 정복 기법을 사용하는 정렬 알고리즘입니다. 과정은 다음과 같습니다

//분안정한 정렬 알고리즘

피벗 요소를 선택.
1 피벗을 기준으로 배열을 두 부분으로 나눔 (피벗보다 작은 요소들, 피벗보다 큰 요소들).
2 두 부분을 재귀적으로 퀵 정렬.
3 병합 단계 없이 배열이 정렬됨.
4 시간복잡도: 평균 O(n log n), 최악 O(n^2) (피벗이 매번 최악으로 선택될 경우)

정렬 알고리즘의 따른 시간복잡도

재귀 알고리즘이란?

재귀 알고리즘(Recursive Algorithm)은 함수가 자기 자신을 호출하여 문제를 해결하는 알고리즘입니다

기저 조건(Base Case): 재귀 호출을 멈추는 조건. 문제를 더 이상 쪼갤 수 없는 상태를 정의.
재귀 호출(Recursive Call): 현재 문제를 더 작은 하위 문제로 나누어 자기 자신을 호출.
재귀 알고리즘의 대표적인 예로는 피보나치 수열, 팩토리얼 계산, 트리 탐색 등이 있습니다.

장점
 간결함: 북잡한 반복구조를 단순화 할수 있다
 문제분할: 문제를 작은 하위 문제로 분할 하는것이 용이합니다 
 자연스러운 표현: 재귀적으로 표현하는것이 자연스럽다

단점
 성능문제:재귀 호출이 많아지면 함수 호출 오버헤드로 인해 성능이 저하될 수 있습니다
 스택오버플로우 : 깊은 재귀호출은 스택 오버플로우를 유발할 수 있습니다
 디버깅의 어려움: 재귀 함수는 디버깅과 추적이 어려울수있다
 메모리사용: 재귀 호출은 각 호출마다 매모리를 사용한다

 

콜백과 다릅니다 헷갈리지 맙시다

허프만 코딩이란?

허프만 코딩(Huffman Coding)은 가변 길이의 접두사 코드(prefix code)를 사용하는 무손실 압축 알고리즘입니다.
문자들의 빈도에 따라 짧은 코드와 긴 코드를 배정하여 전체 데이터의 길이를 줄이는 방식입니다

1 각 문자의 빈도를 기반으로 우선순위 큐에 노드를 추가.
2 빈도가 가장 낮은 두 노드를 선택하여 합침.
3 새로운 노드를 우선순위 큐에 추가.
4 큐에 하나의 노드만 남을 때까지 이 과정을 반복.
5 각 문자를 트리에서 경로를 따라 0과 1로 인코딩.

허프만 코딩은 파일 압축, 데이터 전송 등에 사용되며, 효율적인 압축률을 제공합니다