4. Data Structure

아현·2021년 11월 4일

Computer Science

목록 보기

11/47

1. BFS, DFS란?

DFS
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법, 즉 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.
- 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.
  깊이 우선 탐색이 너비 우선 탐색보다 좀 더 간단하다.

BFS
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법, 즉 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
- 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.

Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우

깊이 우선 탐색의 경우

모든 친구 관계를 다 살펴봐야 할지도 모른다.

너비 우선 탐색의 경우

Ash와 가까운 관계부터 탐색

2. Queue란? Stack이란?

큐(Queue)
- FIFO(First-In-First-Out) 를 따른다.
- 연결 리스트로 구현
- 데이터가 입력된 시간 순서대로 처리해야 할 필요가 있는 상황에 이용한다.
  - 너비 우선 탐색(BFS, Breadth-First Search) 구현
    - 처리해야 할 노드의 리스트를 저장하는 용도로 큐(Queue)를 사용한다. 노드를 하나 처리할 때마다 해당 노드와 인접한 노드들을 큐에 다시 저장한다. 노드를 접근한 순서대로 처리할 수 있다.
  - 캐시(Cache) 구현
  - 우선순위가 같은 작업 예약 (인쇄 대기열)
  - 선입선출이 필요한 대기열 (티켓 카운터)
  - 콜센터 고객 대기시간, 프린터의 출력 처리, 윈도 시스템의 메시지 처리기, 프로세스 관리

스택 (Stack)
- LIFO(Last-In-First-Out)를 따른다.
  - 가장 최근에 스택에 추가한 항목이 가장 먼저 제거될 항목이다.
- 연결리스트로 구현
- 재귀 알고리즘
  - 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다. 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다. 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다. 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
  - 웹 브라우저 방문기록 (뒤로가기)
  - 실행 취소 (undo)
  - 역순 문자열 만들기
  - 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)

3. 다이나믹 프로그래밍이란?

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다.

4. 오버로딩과 오버라이딩의 차이점은?

참조

오버로딩(Overloading) : 같은 이름의 메서드 여러개를 가지면서 매개변수의 유형과 개수가 다르도록 하는 기술
오버라이딩(Overriding) : 상위 클래스가 가지고 있는 메서드를 하위 클래스가 재정의해서 사용

5. 상속이란?

참조

상속은 현실 세계에서 부모에서 자식에게 전해지는 것과 동일한 의미입니다. 부모 클래스의 정보는 자식에게 전해집니다.
상속은 기존의 클래스를 확장해서 사용할 수 있으며 클래스에 다형성을 부여합니다.
또한, 공통된 속성을 하나로 묶어줄 수 있다는 장점이 있습니다.

6. 객체지향 프로그래밍이란? 객체지향 프로그래밍의 3대 특징은?

객체 지향 프로그래밍(영어: Object-Oriented Programming, OOP)은 컴퓨터 프로그래밍의 패러다임 중 하나이다.
객체 지향 프로그래밍은 컴퓨터 프로그램을여러 개의 독립된 단위, 즉 "객체"들의 모임으로 파악하고자 하는 것이다. 각각의 객체는 메시지를 주고받고, 데이터를 처리할 수 있다.
객체 지향 프로그래밍은 프로그램을 유연하고 변경이 쉽게 만들기 때문에 대규모 소프트웨어 개발에 많이 사용된다. 또한 프로그래밍을 더 배우기 쉽게 하고 소프트웨어 개발과 보수를 간편하게 하며, 보다 직관적인 코드 분석을 가능하게 하는 장점이 있다.

추상화(abstraction)
캡슐화(encapsulation)
상속성(inheritance)
다형성(polymorphism)
동적바인딩(Dynamic Binding)

7. 인터페이스와 추상클래스 각각의 특징과 차이점은?

참조

인터페이스
- 인터페이스는 쉽게 말하면 껍데기라고 말할 수 있고, 설계도 또는 명세라고 생각하면 된다.
- 모든 메소드가 추상 메소드이고, 일반 변수를 가질 수 없다. (추상 클래스와 비교해보자)
- 그 의미는 인터페이스를 구현한 클래스는 모든 메소드를 강제적으로 구현해야한다.

추상 클래스
- 추상 클래스는 0개 이상의 추상 메소드(아직 구현되지 않은 메소드) 를 가지고, 일반 메소드, 일반 변수 또한 가질 수 있다.
- 그렇기에 인터페이스 역할도 하면서, 구현체도 가지고 있는 돌연변이 같은 클래스이다.

추상 클래스, 인터페이스 모두 인스턴스화가 될 수 없다.

8. Call by value, call by reference는 각각 무엇인가?

Call by value(값에 의한 호출)
- 복사하여 처리하기 때문에 안전하다. 원래의 값이 보존이 된다.
- 복사를 하기 때문에 메모리가 사용량이 늘어난다.

Call by reference(참조에 의한 호출)
- 복사하지 않고 직접 참조를 하기에 빠르다.
- 직접 참조를 하기에 원래 값이 영향을 받는다.(리스크)

9. static의 의미는?

항상 값이 변하지 않는 경우라면 static 사용 시 메모리 할당을 딱 한번만 하게 되어 메모리 사용에 이점
static을 사용하는 또 한가지 이유로 공유의 개념을 들 수 있다. static 으로 설정하면 같은 곳의 메모리 주소만을 바라보기 때문에 static 변수의 값을 공유하게 되는 것이다.

10. garbage collection이란?

11. 그래프를 정의한다면?

단순히 노드(N, node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아 놓은 자료 구조, 즉 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조이다.
Ex) 지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 도로(교차점과 일방 통행길), 선수 과목 등
참고

트리는 DAG(Directed Acyclic Graph)방향성이 있는 비순환 그래프라는 차이

12. 해싱이란?

키(Key) 값을 해시 함수(Hash Function)라는 수식에 대입시켜 계산한 후 나온 결과를 주소로 사용하여 바로 값(Value)에 접근하게 할 수 하는 방법이다.
키(Key) 값을 값(Value)이 저장되는 주소 값으로 바꾸기 위한 수식이다.

13. priority queue란?

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것
우선순위 큐는 힙(Heap)이라는 자료구조를 가지고 구현할 수있기 때문에 이 둘을 묶어서 같이 쓴 것

14. 정렬 알고리즘에는 무엇이 있는가? 그 중 하나를 구현한다면?

참조

1. Bubble Sort (버블정렬)

이웃한 두 값을 비교하여 정렬한다. 큰 값이 오론쪽으로 이동하는 과정이 반복되면서 비교했던 모든 값들의 최댓값이 맨 오른쪽으로 옮겨지게 된다.


def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def bubbleSort(x):
    for size in reversed(range(len(x))):
        for i in range(size):
            if x[i] > x[i+1]:
                swap(x, i, i+1)

2. Selection Sort (선택정렬)'

주어진 배열에서 최댓값(최솟값)을 찾아 맨 오른쪽(왼쪽)값과 교체한다. 최댓값을 맨 오른쪽으로 보낸다는 점에서 버블정렬과 비슷하지만, 이웃한 두 값을 정렬하는 과정이 없기 때문에 대체로 버블정렬보다 빠르다.



def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def selectionSort(x):
    for size in reversed(range(len(x))):
        max_i = 0
        for i in range(1, 1+size):
            if x[i] > x[max_i]:
                max_i = i
        swap(x, max_i, size)

3. Insertion Sort (삽입정렬)

아직 정렬되지 않은 값을 이미 정렬된 배열 사이에 끼워 넣는 과정을 반복한다.


def insertionSort(x):
    for size in range(1, len(x)):
        val = x[size]
        i = size
        while i > 0 and x[i-1] > val:
            x[i] = x[i-1]
            i -= 1
        x[i] = val

4. Shell Sort (셸 정렬)

삽입 정렬이 거의 정렬된 배열에서 최적의 성능을 냄과 동시에 값 하나씩 위치를 결정하여 비효율적이라는 점에서 착안되었다. 셸 정렬은 주어진 간격만큼 듬성듬성 떨어진 서브배열을 만들어 삽입정렬을 수행한다. 간격이 3이라면 3개의 서브배열이 만들어진다. 모든 서브배열에 대해 삽입정렬을 마쳤다면, 간격을 (보통 절반으로) 줄여 반복한다. 간격이 1이 되면 거의 정렬이 된 상태이므로 빠르게 정렬할 수 있다.


def gapInsertionSort(x, start, gap):
    for target in range(start+gap, len(x), gap):
        val = x[target]
        i = target
        while i > start:
            if x[i-gap] > val:
                x[i] = x[i-gap]
            else:
                break
            i -= gap
        x[i] = val

def shellSort(x):
    gap = len(x) // 2
    while gap > 0:
        for start in range(gap):
            gapInsertionSort(x, start, gap)
        gap = gap // 2

5. Merge Sort (병합 정렬)

폰 노이만이 개발했으며, 두 부분으로 쪼개는 작업을 재귀적으로 반복한 뒤, 쪼갠 순서의 반대로 작은 값부터 병합해나가는 분할 정복 알고리즘의 일종이다.


def mergeSort(x):
    if len(x) > 1:
        mid = len(x)//2
        lx, rx = x[:mid], x[mid:]
        mergeSort(lx)
        mergeSort(rx)

        li, ri, i = 0, 0, 0
        while li < len(lx) and ri < len(rx):
            if lx[li] < rx[ri]:
                x[i] = lx[li]
                li += 1
            else:
                x[i] = rx[ri]
                ri += 1
            i += 1
        x[i:] = lx[li:] if li != len(lx) else rx[ri:]

6. Quick Sort (퀵 정렬)

피벗(pivot, 기준값) 원소를 정하여 피벗보다 작은 값은 피벗 앞 쪽에, 피벗보다 큰 값은 피벗 뒤 쪽에 오도록 한다. 피벗 양 쪽 배열에 대해 같은 작업을 반복해나간다. 분할 정복 방법의 일종이며, 재귀 호출이 진행될 때마다 최소한 하나의 원소(피벗)는 최종적으로 위치가 정해진다. 병합정렬은 데이터를 쪼갠 뒤 합치는 과정에서 정렬하지만, 퀵정렬은 데이터를 쪼개면서 정렬한다.



def swap(x, i, j):
    x[i], x[j] = x[j], x[i]

def pivotFirst(x, lmark, rmark):
    pivot_val = x[lmark]
    pivot_idx = lmark
    while lmark <= rmark:
        while lmark <= rmark and x[lmark] <= pivot_val:
            lmark += 1
        while lmark <= rmark and x[rmark] >= pivot_val:
            rmark -= 1
        if lmark <= rmark:
            swap(x, lmark, rmark)
            lmark += 1
            rmark -= 1
    swap(x, pivot_idx, rmark)
    return rmark

def quickSort(x, pivotMethod=pivotFirst):
    def _qsort(x, first, last):
        if first < last:
            splitpoint = pivotMethod(x, first, last)
            _qsort(x, first, splitpoint-1)
            _qsort(x, splitpoint+1, last)
    _qsort(x, 0, len(x)-1)