지금의 기록이 미래의 자산이 된다.

Today's records become tomorrow's assets.

그래프

2023-03-21

devFancy

DataStructure
- 그래프
이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

그래프
- 그래프는 트리보다 복잡하다.
- 사실 트리가 그래프의 한 종류에 속한다.
- 하지만 트리와 달리 한 노드에 부모가 여럿 있을 수 있고 사이클이 만들어질 수 있다는 점이 다르다.
- 그리고 노드 자체가 아닌 노드 사이의 링크에도 값 또는 가중치가 있을 수 있다.
- 이렇게 다른 노드를 가리키는 기능 외에 별도의 정보를 담을 수 있는 링크를 에지(edge)라고 부른다.
- 그래프를 수학적 기호로 표현하면 $G = (V, E)$ 으로 쓰이고, V는 Vertex의 약자로 꼭짓점(=Node)을 의미하고, E는 Edge의 약자로 간선을 의미한다.
- 에지에는 당방향 에지와 양방향 에지가 있으며, 단방향 에지가 들어 있는 그래프는 방향성 그래프(directed graph), 양방향 에지만 들어 있는 그래프는 무방향성 그래프(undirected graph)라고 부른다.
- [그림 6-4]에는 방향성 그래프, [그림 6-5]에는 무방향성 그래프가 나와 있다.
- 그래프 자료구조에서 많이 쓰이는 방법 가운데 하나로 인접 리스트(Adjacency list) 또는 인접 행렬(Adjacency Matrix)를 들 수 있다.
- 인접 리스트는 그래프의 각 노드에 인접한 노드들을 연결 리스트로 표현하는 자료구조다.
- n개의 vertics와 e개의 edges를 가진 무방향성 그래프인 G에서 edge의 최대 수는 O(n+e) 이다.
- 인접 행렬은 노드 개수만큼의 차원 수로 만들어지는 정사각형 형태의 2차원 배열로 표현하는 자료구조다.
- n개의 vertics와 e개의 edges를 가진 무방향성 그래프인 G에서 edge의 최대 수는 O(n^2) 이다.
Read All
트리

2023-03-20

devFancy

DataStructure
- 트리
이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

트리
- 트리는 0개 이상의 다른 노드에 대한 레퍼런스가 들어 있는 노드(데이터 원소)로 구성된다.
- 트리를 그림으로 표현하면 아래와 같다.
- 연결 리스트에서와 마찬가지로 노드는 구조체 또는 클래스로 표현되며, 트리는 포인터 또는 레퍼런스만 있다면 어떤 언어로든 구현할 수 있다.
- 객체지향 언어에서는 보통 노드의 공통적인 부분을 하나의 클래스로 정의하고, 노드에 들어가는 데이터를 위해 서브클래스를 만들어서 사용한다.
- 실제 코딩을 할 때는 children은 비공개(private)로 선언하고 그 배열을 건드리기 위한 메서드만 공개하는 방법을 써야 할 것이다.
- 정수가 저장되는 클래스를 메서드와 생성자를 모두 제대로 갖춘 자바로 만든다면 다음과 같은 식의 코드를 쓰면 된다.
```
public abstract class Node {
    private Node[] children;
    
  public Node( Node[] children) {
      this.children = children;
  }
  
  public int getNumChildren() {
      return children.length;
  }
  
  public Node getChildren(int index) {
      return children[index];
  }
}

public class IntNode extends Node {
    private int value;
    
    public IntNode (Node [] children, int value) {
        super(children);
        this.value = value;
    }
    
    public int getValue() {
        return value;
    }
}
```
- 다음은 [그림 6-1]을 참고해서 트리와 관련된 용어들을 몇 가지 정리했다.
- 부모(Parent) : 다른 노드를 가리키는 노드는 그 노드의 부모가 된다. 루트를 제외한 모든 노드에는 부모가 하나씩 있다.
  - [그림 6-1]에서 B는 D, E, F의 부모 노드가 된다.
- 자식(Child) : 루트를 제외한 모든 노드는 그 노드를 가리키는 노드의 자식이 된다.
  - [그림 6-1]에서 D, E, F는 B의 자식 노드가 된다.
- 자손(Descendant) : 특정 노드로부터 자식 노드로 이어지는 경로를 따라 도달할 수 있는 모든 노드는 그 특정 노드의 자손이다.
  - [그림 6-1]에서 D, E, F, H, I, J, K는 모두 B의 자손이다.
- 조상(Ancestor) : 어떤 노드를 자손으로 삼고 있는 노드는 모두 그 노드의 조상이다.
  - 예를 들어 A, B, D는 모두 I의 조상이다.
- 잎(Leaves) : 자식이 없는 노드를 잎이라고 부른다. G, H, I, K는 모두 잎이다.
Read All
연결 리스트

2023-03-19

devFancy

DataStructure
이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

연결 리스트
- 연결 리스트는 동적인 데이터를 처리하는 것과 관련된 수많은 문제의 근간을 이루는 자료구조다.
연결 리스트의 종류
- 연결 리스트에는 단일 연결 리스트(singly-linked list), 이중 연결리스트(doubly-linked list), 원형 연결 리스트(circularly-linked list), 이렇게 세 가지 기본 유형이 있다.
- 면접에서는 대부분 단일 연결 리스트문제가 나오는 편이다.
단일 연결 리스트
- [그림 5-1]에 나와있는 것처럼 리스트에 들어가는 각 데이터 원소에는 리스트의 다음 원소에 대한 연결고리(link)가 들어있다.
- 단일 연결 리스트의 첫 번째 원소는 리스트의 머리(head)라고 부른다.
- 단일 연결 리스트의 마지막 원소는 꼬리(tail)라고 부르며 연결고리는 비어 있거나 널 연결고리로 이어져 있다.
- 단일 연결 리스트에 있는 연결고리는 다음 노드를 가리키는 포인터나 레퍼런스로만 구성되기 때문에 앞으로만 종주할 수 있다.
- 따라서 리스트를 완전 종주하려면 항상 첫 번째 원소부터 시작해야 한다.
- 바꿔 말하자면, 리스트에 있는 모든 원소의 위치를 파악하기 위해서는 리스트의 첫 번째 원소에 대한 포인터나 레퍼런스가 있어야만 한다.
- 기본적으로 C에서 단일 연결리스트의 형태를 다음과 같이 정의할 수 있다.
```
typedef struct InteElement {
    struct IntElement *next;
    int data;
} IntElement;
```
- 자바에서 제네릭을 써서 구현하는 방법도 비슷하다. 물론 포인터가 아니라 레퍼런스를 쓴다는 게 달라진다.
```
// 탬플릿으로 만든 자바용 단일 연결 리스트
public class ListElement<T> {
    public ListElement(T value) { data = value; }
    public ListElement<T> next() { return next; }
    public T value() { return data; }
    public void setNext ( ListElement<T> elem ) { next = elem; }
    public void setValue( T value ) { data = value; }
    private ListElement<T> next;
    private T data;
}
```
이중 연결 리스트
- [그림 5-2]에 나와 있는 이중 연결 리스트는 단일 연결 리스트의 여러 가지 단점을 극복하기 위해 만들어졌다.
- 이중 연결 리스트는 각 원소마다 리스트에서 그다음에 오는 원소에 대한 연결고리 외에 그 앞에 있는 원소에 대한 연결고리도 들어 있다는 점에서 단일 연결 리스트와 다르다.
- 이렇게 연결고리를 추가하면 리스트를 어느 방향으로든 종주할 수 있다.
- 어떤 원소에서 시작하든 리스트 전체를 종주하는 것이 가능하다.
- 이중 연결 리스트에도 단일 연결 리스트와 마찬가지로 머리와 꼬리가 있다.
- 리스트의 머리의 이전 원소에 대한 연결고리는 꼬리의 다음 원소에 대한 연결고리와 마찬가지로 비워두거나 널로 지정한다.
- 이중 연결 리스트는 면접 문제로는 그리 많이 나오지 않는다. 단일 연결 리스트를 쓰는 쪽이 더 어렵기 때문이다.
- 그리고 이중 연결 리스트를 쓰면 불필요하게 복잡해지기만 해서 쓰지 않게 되는 경우도 있다.
원형 연결 리스트
- 원형 연결 리스트에는 끝, 즉 머리나 꼬리가 없다.
- 원형 연결 리스트의 모든 원소에서 다음 원소를 가리키는 포인터나 레퍼런스에는 반드시 널이 아닌 어떤 원소가 들어가며, 이중 연결 리스트라면 포인터/레퍼런스에도 널이 아닌 원소가 들어가야 한다.
- 원소가 하나밖에 없는 리스트라면 그냥 자기 자신을 가리키면 된다.
- 원형 연결 리스트의 종주 문제로는 사이클 회피 문제가 많이 나온다. 시작점을 제대로 추적하지 않으면 리스트에서 무한 루프를 돌 수 있다.
- 원형 연결 리스트도 가끔 쓸 일이 있지만, 면접 문제로는 거의 나오지 않은 편이다.
기초적인 연결 리스트 연산
- 연결 리스트 문제를 제대로 풀려면 연결 리스트에 대한 기초적인 연산을 완벽하게 이해해야 한다.
- 기초 연산에는 리스트를 잃어버리지 않기 위한 머리 원소 추적, 리스트 종주, 리스트 원소 추가 및 제거 등이 있다.
- 여기에서는 단일 연결 리스트로 구현할 때 빠질 수 있는 함정에 초점을 맞춰보도록 한다.
머리 원소 추적
- 단일 연결 리스트에는 반드시 머리 원소를 추적해야 한다. 그러지 않으면 언어에 따라 가비지 컬렉터에 의해 제거되거나 어딘가에서 길을 잃고 말게 된다.
- 따라서 새로운 원소를 첫 번째 원소 앞에 추가한다거나 리스트의 첫 번째 원소를 제거할 때 리스트의 머리에 대한 포인터 또는 레퍼런스를 갱신해야 한다.
- 함수나 메서드 내에서 리스트를 변형시킬 때는 머리 원소를 제대로 추적할 수 있도록 주의해야 한다. 함수나 메서드를 호출한 쪽에 바뀐 새로운 머리 원소를 알려줘야 하기 때문이다.
- 예를 들어, 다음과 자바 코드는 리스트의 머리에 대한 레퍼런스를 갱신하기 위해서는 새로운 머리 원소에 대한 레퍼런스를 반환해야 한다.
```
public ListElement<Integer> insertInFront (ListElement<Integer> list, int data) {
ListElement<Integer> l = new ListElement<Integer> (data);
    l.setNext(list);
    return l;
}
```
- 메서드를 호출한 쪽에서는 머리 원소에 대한 레퍼런스를 적당히 갱신해줘야 한다.
```
int data = ...; // 삽입할 데이터
ListElement<Integer> head = ...; // 머리에 대한 래퍼런스

head = insertInFront(head, data);
```
- 리스트의 맨 앞에 새로운 원소를 추가하는 다음과 같은 C 코드를 생각해보자. 제대로 동작하기 위해서는 head 포인터에 대한 포인터를 넘겨줘야 한다.
```
bool insertInFront( IntElement **head, int data) {
    IntElement *newElem = malloc(sizeof(IntElement));
    if( !newElem ) return false;
    
    newElem->data = data;
    newElem->next = *head;
    *head = newElem;
    return true;
}
```
- 이 함수에서는 리턴 값으로 메모리 할당 성패 여부를 돌려주기 때문에 자바에서처럼 새로운 헤드 포인터를 돌려줄 수가 없다. (C에는 예외 기능이 없음)
- C++에서는 머리 포인터에 대한 레퍼런스로 전달할 수도 있고, 새로운 머리 포인터를 리턴할 수도 있다.
리스트 종주
- 머리 원소가 아닌 다른 리스트 원소를 가지고 작업을 해야 하는 경우도 있다.
- 연결 리스트의 첫 번째 원소가 아닌 원소에 대한 연산을 하려면 리스트에 있는 원소 중 일부를 종주해야 할 수도 있으며, 이때 항상 리스트가 끝나지 않는지 확인을 해야 한다.
- 찾아낼 객체가 리스트에 있는 경우와 마지막 원소를 확인하는 경우는 다음과 같은 코드로 생각해 볼 수 있다.
```
public ListElement<Integer> find(ListElement<Integer> head, int data) {
    ListElement<Integer> elem = head;
    while( elem != null && elem.value() != data) {
        elem = elem.next();
    }
    return elem;
}
```
- 함수/메서드를 호출한 쪽에서는 반환 값이 널이 아닌지 확인하여 오류 조건을 찾아야 한다.
원소의 삽입과 삭제
- 단일 연결 리스트에 있는 원소들은 다음 원소에 대한 연결고리를 통해서만 관리할 수 있기 때문에 리스트 중간에서 원소를 삽입 또는 삭제하려면 그 앞 원소의 연결고리를 수정해야 한다.
- 삭제할 원소(또는 삽입해야할 원소)만 지정된 상황이라면 바로 앞 원소를 찾아낼 만한 다른 방법이 딱히 업기 때문에 머리에서부터 리스트를 종주해야만 할 수도 있다.
- 삭제할 원소가 머리 원소라면 한층 더 기울여야 한다.
- 리스트에 있는 한 원소를 삽입 또는 삭제하는 C 함수는 다음과 같이 만들 수 있다.
```
// Insert
void insertNode(listPointer *first, listPointer node)
{   
    listPointer p, q;

    p = q = *first;
    // Empty (비어있는 경우)
    if(!p) {
        *first = node;
        return;
    }
    while(TRUE) {
        p = q;
        q = q->link;
        // Right (맨 끝)
        if(q == NULL) {
            p->link = node;
            return;
        }
    }
}

// Delete
void deleteNode(listPointer *first, int data)
{
    listPointer p, q;
    p = q = *first;
    // Empty (비어있는 경우)
    if(p == NULL) return;
    // Left (맨앞)
    if(p->data <= data) {
        *first = (*first)->link;
        free(p);
        return;
    }
    while(TRUE) {
        // Middle, Right
        if(q->data <= data) {
            p->link = q->link;
            free(q);
            return;
        }
        p = q;
        q = q->link;
        // No data (찾는 값이 없는 경우)
        if(q == NULL) return;
    }
}
```
- 위의 코드를 이해하기 아래와 같이 쉽게 그림으로 그렸다.
- 그림 옆에는 이해하기 쉽도록 슈도 코드(Pseudo-code)로 작성했다. (슈도 코드에는 모든 경우의 수를 생각하여 작성함)
InsertNode [1] 중간 / [2] 맨뒤 / [3] 맨앞 / [4] 비어있는 경우

deleteNode [1] 중간 / [2] 맨뒤 / [3] 맨앞 / [4] 비어있는 경우

연결 리스트 문제
- 자바나 C# 같은 언어에서는 연결 리스트를 직접 구현해서 쓰는 일이 거의 없기 때문에 답안은 모두 C로 구현했다.
- 연결 리스트를 활용한 스택에 대한 기본적인 구현법만 익히는 것을 목표로 정리했다.
스택 구현법

면접 문제 : 스택 자료구조에 대해 논하라.

연결 리스트 또는 동적 배열을 써서 C로 스택을 구현하고 그 자료구조를 사용한 이유를 설명하라.

완전하고 일관성 있으면서 사용하기 편리한 스택 인터페이스를 설계하라.
- 이 문제는 다음과 같은 세 가지를 중점적으로 살펴보기 위한 문제라고 할 수 있다.
1. 기본적인 자료구조에 대한 지식
2. 자료구조를 조작하기 위한 루틴을 만드는 능력
3. 일련의 루틴에 대한 일관성 있는 인터페이스를 설계하는 능력
- 위의 면접 문제에 대해 각 단계별로 나누어 정리했다.
[1] 스택 자료구조에 대해 논하라.
- 스택은 후입선출(LIFO, last-in-first-out), 즉 마지막에 들어간 것이 가장 먼저 나오는 자료구조다.
- 모든 원소는 접시를 쌓아놓았다가 꺼낼 때와 마찬가지로 들어간 순서와 반대 순서로 나온다.
- 원소를 삽입하고 삭제하는 연산은 각각 푸시(Push)와 팝(Pop)이라고 부른다.
- 스택은 여러 개의 하위 작업으로 나눌 수 있는 작업을 관리할 때 유용하게 쓰이는 자료구조다.
- 스택을 사용하는 대표적인 예로 서브루틴에서 사용하는 반환 주소, 매개변수, 지역변수 등을 추적하는 것을 들 수 있다. 프로그래밍 언어를 파싱할 때 토큰을 추척하는 것도 또 다른 예라고 할 수 있다. (파싱이란 웹페이지에서 원하는 데이터를 추출하여 가공하기 쉬운 상태로 바꾸는 것을 의미한다)
[2] 연결 리스트 또는 동적 배열을 써서 C로 스택을 구현하고 그 자료구조를 사용한 이유를 설명하라.
- 스택을 구현하는 방법 가운데 하나로 배열이 추가될 때마다 필요에 따라 크기가 바뀌는 동적 배열을 사용하는 방법을 들 수 있다.
- 연결 리스트에 비하자면 동적 배열은 배열 원소에 대한 임의 접근이 가능하다는 것이 가장 큰 장점이라고 할 수 있다.
- 인덱스만 알면 어떤 원소든 즉시 접근할 수 있다.
- 하지만 스택에 대한 연산은 항상 자료구조의 한쪽 끝(스택 맨 위)에 대해서만 이뤄지기 때문에 동적 배열의 임의접근성이라는 장점이 별 힘을 발휘할 수 없다.
- 그리고 동적 배열이 커지면 그에 맞춰 크기를 조절해야 하고, 그 과정에서 기존 배열의 모든 원소들을 새 배열로 복사해야 하기 때문에 그만큼 시간이 오래 걸릴 수 있다.
- 연결 리스트에서는 각 원소마다 메모리를 동적으로 할당해야한다. 메모리 할당자의 오버헤드에 따라 동적 배열에서 필요한 복사 작업보다 메모리 할당에서 더 오랜 시간이 걸릴 수 있다.
- 게다가 동적 배열에서 인접한 원소는 메모리상에서도 인접해 있지만 연결 리스트에서 인접한 원소는 메모리상에서 떨어져 있을 수도 있다.
- 또한 동적 배열에서는 모든 원소마다 포인터와 관련된 오버헤드를 감수하지 않아도 된다.
- 따라서 동적 배열에서는 메모리 국소성 면에서 장점이 있는데 프로세스가 메모리보다 훨씬 빨라짐에 따라 그 중요성은 점점 더 커지고 있다.
- 이런 이유로 동적 배열을 기반으로 하는 스택이 연결 리스트를 기반으로 하는 스택에 비해 대체로 빠른 편이다.
- 동적 배열보다는 연결 리스트로 구현하는 것이 훨씬 덜 복잡하기 때문에 면접에서는 연결 리스트를 푸는 쪽이 훨씬 낫다.
[3] 완전하고 일관성 있으면서 사용하기 편리한 스택 인터페이스를 설계하라.
- 스택을 구현할 때는 push와 pop 루틴이 필요하다. 각 함수에는 연산을 처리할 스택을 넘겨줘야 한다.
- push 연산에는 집어넣을(푸시할) 데이터를 넘겨줘야 하며, pop 연산에서는 스택에서 꺼낸 데이터를 반환해야 한다.
- 함수 원형을 만들기 위해서 스택에 저장할 데이터형을 알아야 하는데, 보통 조건이 주어지지 않는 경우라면 void 포인터를 저장해서 일반적인 데이터형을 모두 커버할 수 있도록 만드는 것도 나쁘지 않다.
```
#defind MAX_STACKS 10 /* maximum number of stacks */
typedef struct {
    int key;
    /* other fields */
    } element;
typedef struct stack *stackPointer;
typedef struct stack {
    element data;
    stackPointer link;
    } Node;
stackPointer top[MAX_STACKS];
```
- 위과 같은 자료형을 가진 스택 기반의 연결 리스트일 때, push 연산과 pop 연산을 아래와 같이 구현할 수 있다.
push(i, item) : Add to a linked stack
```
void push(int i, element item)
{ /* add item to the ith stack */
    stackPointer temp;
    MALLOC(temp, sizeof(*temp));
    temp->data = item;
    temp->link = top[i];
    top[i] = temp;
}
```
item = pop(i) : Delete a linked stack
```
element pop(int i)
{   /* remove top element from the ith stack */
    stackPointer temp = top[i];
    element item;
    if (!temp)  // 비어있을 때
        return stackEmpty();
    item = temp->Data;
    top[i] = temp->link; // 아래로 한칸 이동
    free(temp);
    return item;
}
```
문제 설명 및 정답 코드

연결 리스트를 활용하여 스택을 생성하고 실행하는 프로그램을 만들어보자.

문제 : 다음과 같은 스택을 생성하고 실행하는 프로그램을 작성하라. 이를 위해 push, pop, stackEmpty 함수를 구현하여야 한다.
- (1) 실행 순서 - [1], [2]
- [1-1] 아래와 같은 입력으로 부터 학번 순으로 미리 정렬된 데이터를 입력받으면서 순서대로 Linked Stack을 구현한다.
  - (과목번호, 학번, 성적)의 쌍으로 데이터들이 입력되며 각 과목별로 스택에 저장된다.
  - (과목번호 : 1자리수, 학번 : 1자리수, 성적 : 2자리수)
```
0 1 95
1 1 80
2 1 89
0 2 45
1 2 81
0 3 45
1 3 12
2 3 33
0 4 99
1 4 94
2 4 91
0 5 67
2 5 49
```
- [1-2] 각 과목 별로 학번의 역순으로 학번과 노드의 데이터(학번, 성적)을 출력하라.
  - (출력형식 - 과목번호 : %d, 학번 : %d, 성적 : %2d)
- (2) 구현 세부사항 - 반드시 linked list를 활용한 stack으로 작성해야 한다.
```
#define MAX_STACK 3
typedef struct {
    int id;         // 학번
    int grade;      // 성적
    } element;
typedef struct stack *stackPointer;
typedef struct stack {
    element data;
    stackPointer link;
    } Node;
stackPointer top[MAX_STACKS];
/***************************
top[i] = NULL, 0 <= i < MAX_STACKS // initial codition
top[i] = NULL, iff ith stack is empty // boundary condition
***************************/
```
- (3) 실행 예
```
0 1 95//서버 입력 시작
1 1 80
2 1 89
0 2 45
1 2 81
0 3 45
1 3 12
2 3 33
0 4 99
1 4 94
2 4 91
0 5 67
2 5 49
0 0 0//서버 입력 종료
0 5 67//사용자 출력 시작
0 4 99
0 3 45
0 2 45
0 1 95
1 4 94
1 3 12
1 2 81
1 1 80
2 5 49
2 4 91
2 3 33
2 1 89// 사용자 출력 종료
```
Read All
[Algorithm] 프로그래밍 문제 접근법 - 빅 오 분석법

2023-03-18

devFancy

AlgorithmSkill
- 풀이 분석
이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

풀이 분석
- 문제에 대한 답을 내놓고 나면 구현의 효율성에 대한 질문이 나오는 경우가 많다.
- 지원자가 구현한 풀이 방법과 다른 풀이 방법을 제시하고 그 둘의 장단점을 비교한다거나
- 어떤 상황에서 어떤 구현 방법이 더 유리할지를 물어보는 경우를 많이 접하게 될 것이다.
- 그리고 메모리 또는 공간 사용에 관한 질문도 자주 나오는 편인데, 특히 재귀 호출을 사요할 경우 이런 질문이 많이 나온다.
- 빅 오 분석법(Big-O analysis)을 제대로 이해하고 있다면 면접관에게 좋은 인상을 남기는 데 크게 도움이 된다
- 빅 오 분석법은 입력 값의 개수에 따라 알고리즘이 수행되는 데 걸리는 시간을 바탕으로 알고리즘의 효율성을 평가하는 실행 시간 분석법이다.
- 알고리즘의 상대적인 효율성을 간단하게 따져보는 데는 유용하다.
빅 오 분석
- 음이 아닌 수가 저장된 배열에서 최대값을 구하는 간단한 함수를 구현하는 방법에는 최소 두 가지가 있다.
- 첫 번째 방법은 배열의 모든 원소를 하나씩 확인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 방법이다.
- 코드로 구현하면 다음과 같다.
```
/* n개의 음이 아닌 정수의 배열에서 가장 큰 값 반환 */
int CompareToMax(int array[], int n) 
{
    int curMax, i;
    
    /* 배열에 적어도 하나 이상의 원소가 있는지 확인 */
    if (n <= 0)
        return -1;
        
    /* 지금까지 확인한 값 중 최대값을 저장할 변수에 배열의 첫 번째 값 저장 */
    curMax = array[0];
    
    /* 모든 수를 최대값과 비교함 */
    for(i = 1; i < n; i++) {
        if(array[i] > curMax) {
            curMax = array[i];
        }
    }
    return curMax;
}
```
- 두 번째 방법은 각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값이 최대값이 된다.
- 코드로 구현하면 다음과 같다.
```
/* n개의 음이 아닌 정수의 배열에서 가장 큰 값 반환 */
int CompareToAll(int array[], int n)
{
    int i, j;
    bool isMax;
    
    /* 배열에 적어도 하나 이상의 원소가 있는지 확인 */
    if(n <= 0)
        return -1;
    
    for(i = n-1; i > 0; i--) {
        isMax = true;
        for(j = 0; j < n; j++) {
            /* 더 큰 값이 있는지 확인 */
            if(array[j] > array[i])
                isMax = false; /* array[i]가 최대값이 아님 */
        }
        /* isMax가 참이면 더 큰 값이 없는 것으로 array[i]가 최대값이다 */
        if(isMax) break;
    }
    
    return array[i];
}
```
- 이 두 함수는 모두 최대값을 제대로 반환한다.
- 그런데 어느 쪽이 더 효율적인지 알기 위해서는 빅 오 분석법을 활용하면 된다.
- 빅 오 분석법을 활용하면 서로 다른 알고리즘의 상대적인 성능을 예측하고 비교해볼 수 있다.
빅 오 분석법의 원리
- 빅 오 분석법에서는 입력 값의 크기(개수) 를 n개라고 가정한다.
- 문제에 따라 n이 연결 리스트의 노드 개수 또는 특정 자료형의 비트 수 또는 해시 테이블에 들어 있는 항목의 개수일 수 도 있는 등 다양한 값들을 입력 값의 크기 n으로 쓰일 수 있다.
- 이때 연산이라는 말은 일반적으로 입력된 값에 상수를 더하거나 새로운 입력 아이템을 만드거나 입력 값을 삭제하는 작업을 통틀어서 표현한 것이다.
- 빅 오 분석법에서는 이런 모든 연산을 동등하게 본다.
- CompareToMax와 CompareToAll에서는 모두 배열에 있는 값을 다른 값과 비교하는 작업을 연산이라고 생각할 수 있다.
CompareToMax : 배열의 모든 원소를 하나씩 확인하면서 가장 큰 수를 계속 기록한 다음, 확인이 끝나고 나면 그 값을 반환하는 메서드
- CompareToMax에서는 각 배열 원소와 최대값을 한 번 씩 비교했으므로 총 n번의 확인 작업이 수행된다.
- 이런 상황을 O(n)이라고 표현하며 선형 시간 내에 수행된다고 말하기도 한다.
- 이 경우에는 알고리즘을 실행 시키는 데 걸리는 시간이 입력된 항목의 개수에 비례하여 선형적으로 증가한다.
- 빅 오 분석을 할 때는 n이 매우 큰 경우의 실행 시간인 점근적인 실행 시간만 따진다.
- 따라서 빅 오 분석을 할 때는 최고차항 즉, n이 매우 커질 때 가장 큰 항만 남기고 다른 항은 무시한다.
- 지금 다루고 있는 예에는 n이 최고차항이기 때문에 CompareToMax 함수는 O(n) 이 된다.
CompareToAll : 각 값을 다른 모든 값과 비교하는 방법이다. 다른 모든 값이 주어진 값 이하라면 그 값을 반환하는 메서드
- CompareToAll 메서드에서는 일단 최대 원소가 배열의 맨 뒤에 있다고 가정했다.
- 이런 경우에는 n개의 원소를 n개의 다른 원소하고 비교해야 한다.
- 따라서 nxn번 확인을 해야 하므로 이 알고리즘은 O(n^2) 알고리즘이다.
- 즉, 배열이 커짐에 따라서 CompareToAll에서의 비교 횟수가 CompareToMax의 비교 횟수보다 훨씬 커질 것임을 알 수 있다.
최선, 평균, 최악 케이스
- 여기에서 CompareToAll을 분석할 때 최대값이 맨 뒤에 있다고 가정했기 때문에 불공평한 것이라고 생각할 수 도 있다.
- 이런 문제 때문에 최선 케이스, 평균 케이스, 최악 케이스의 실행 시간을 따져봐야 하는 문제가 생긴다.
- 위의 CompareToAll을 분석할 때는 최악의 시나리오를 가정했다.
- 하지만 평균을 따져서 최대값이 가운데 있는 경우를 생각해보자.
- 최대값이 중간에 있다면 절반만 n번씩 확인하면 된다. 그러면 n(n/2)이므로 실행 시간은 O(n^2/2) 가 된다.
- 하지만 각 값을 실제로 확인하는 데 걸리는 시간은 코드에 의해 생성되는 기계어와 CPU에서 그러한 명령들을 수행하는 데 걸리는 시간에 의해 크게 좌우된다.
- 따라서 1/2이라는 숫자가 그리 큰 의미를 가진다고 볼 수 없다.
- 빅 오 분석법에서는 모든 상수 인자들을 빼 버리기 때문에 평균 케이스와 최악 케이스 모두 크게 다를 바가 없다.
- 여전히 O(n^2) 일 뿐이다.
- CompareToAll의 최선 케이스의 실행 시간은 최대값이 배열의 맨 앞에 있는 경우다.
- 이때는 최대값을 다른 모든 값들과 딱 한 번만 비교하면 되기 때문에 실행 시간은 O(n) 이 된다.
- CompareToMaax에서는 최선, 평균, 최악 케이스 모두 실행 시간이 같으므로 항상 O(n) 이다.
- 면접관에게 어떤 시나리오에 가장 중점을 둬야 할지 물어보는 것도 한 방법이다.
- 문제 자체에 이에 대한 언급이 들어 있는 경우도 있다.
빅 오 분석법을 적용하는 방법
- 일반적으로 빅 오 실행 시간 분석은 다음과 같은 방법으로 하면 된다.
1. 입력 값이 무엇인지 확인하고 어떤 것을 n으로 놓아야 할지 결정한다.
2. 알고리즘에서 수행해야할 연산 횟수를 n의 식으로 표현한다.
3. 차수가 제일 높은 항만 남긴다.
4. 모든 상수 인수를 없앤다.
- 면접에서 다루는 알고리즘의 경우에는 입력 데이터의 크기에 의존하는 연산을 제대로 파악하면 빅 오 분석법이 그리 까다롭지는 않다.
어떤 알고리즘이 나을까?
- 가장 빠른 것은 O(1) 알고리즘으로, 보통 상수 실행 시간이라고 부른다.
- 알고리즘 성능은 대부분 입력 크기인 n에 따라 변한다.
- 성능이 가장 좋은 것부터 나쁜 것까지 순서대로 알고리즘 종류를 나열하면 다음과 같다.
  - O(log n) : 실행 시간이 입력 크기의 로그에 비례해서 늘어나는 알고리즘을 로그 알고리즘이라고 부른다.
  - O(n) : 실행 시간에 입력 크기에 비례하는 알고리즘을 선형 알고리즘이라고 부른다.
  - O(n log n) : 준선형 알고리즘이라 부르며 선형 알고리즘과 다항식 알고리즘의 중간쯤 된다.
  - O(n^2) : 입력 크기가 늘어나면 실행 시간이 빠르게 늘어나며, 다항식 알고리즘이라고 부른다.
  - O(2^n) : 다항식 알고리즘보다 실행 시간이 빠르게 늘어나며 지수 알고리즘이라고 부른다.
  - O(n!) : 가장 느린 알고리즘으로, n이 작아도 금방 거의 쓰기 힘든 수준으로 느려지며, 팩토리얼 알고리즘이라고 부른다.
- n이 커지면 실행 시간 차이가 매우 두드러진다. ndl 10일 때 각 알고리즘의 실행 시간을 따져보자.
  - log 10 = 1
  - 10 = 10
  - 10 log 10 = 10
  - 10^2 = 100
  - 2^10 = 1,024
  - 10! = 3,628,800
- 준선형 알고리즘, 또는 그보다 더 빠른 알고리즘(로그 알고리즘)을 찾으면 애플리케이션 성능을 크게 향상시킬 수 있다.
메모리 용량 분석
- 성능을 따지는 데 실행 시간 분석 말고도 중요한 게 메모리 용량이다.
- 애플리케이션의 메모리 용량 또는 알고리즘의 메모리 용량은 앞에서 설명한 빅 오 분석법을 썼던 것과 유사하게 필요한 메모리 사용량을 입력 크기 n의 식으로 표현하는 접근법을 사용해야 한다.
- 입력 크기에 따라 필요한 연산 횟수 대신 각 항목에 대해 필요한 저장 공간을 따져보면 된다.
- 면접관이 구현 방법의 메모리 사용량을 물어보는 경우는 실제 자료구조가 어떻게 구현되는지 제대로 이해하는 가를 알고자 하는 것이다.
Read All
[Algorithm] 프로그래밍 문제 접근법 - 문제 해결

2023-03-17

devFancy

AlgorithmSkill
이 글의 코드와 정보들은 책을 공부하며 정리한 내용을 토대로 작성하였습니다.

절차
- 코딩 문제에서 가장 중요한 것은 지원자의 코딩 실력이 어느 정도 되는지를 가늠하는 것이다.
- 면접관은 지원자가 작성한 코드와 지원자의 대답을 바탕으로 채용 추천 여부를 결정하기 때문에 면접에서 가장 중요한 것이 바로 코딩 문제라고 할 수 있다.
시나리오
- 코딩 문제는 면접관과 일대일로 진행하는 것이 일반적이다.
- 컴퓨터 혹은 종이와 펜을 주고 코드를 작성할 수도 있다.
- 보통은 함수나 메서드를 만드는 경우가 많지만 클래스를 정의하거나 연관된 코드 모듈을 만드는 경우도 가끔 있다.
문제
- 면접관이 물어보는 문제에는 특별한 요구 조건이 주어진다.
- 비교적 짧은 시간안에 풀어야 하므로 변별력을 위해 적당히 복잡한 문제가 출제된다.
- 따라서 실전에 직접 적용할 수 있는 코드를 만드는 문제가 나올 가능성은 희박하다.
- 대신 특별한 트릭이나 언어에서 자주 쓰이지 않는 기능들을 필요로 하는 것들이 많다.
- 가장 흔히 쓰이는 방법이나 이상적인 자료구조를 못 쓰게 하는 경우도 종종있다. 예를 들어 “비교 연산자를 전혀 사용하지 않고 두 정수가 같은지 판단하는 함수를 만드시오” 와 같은 문제가 나올 수도 있다.
- 만약 그런 제약 조건이 없을 때 문제를 풀 방법을 설명한 다음에 주어진 대로 문제를 풀도록 하자.
어떤 언어를 사용할 것인가
- 일반적인 프로그래밍 또는 개발 업무에 지원한다면 자바, 파이썬, 자바스크립트, C#, C++ 같은 주류 언어를 제대로 쓸 수 있는 정도면 충분하다.
- 면접을 하러 가기 전에 자신이 사용할 언어의 사용법 및 문법을 제대로 숙지해야만 한다.
소통이 핵심이다.
- 면접관 입장에서 지원자가 만든 코드 중에 직접 본인의 눈으로 확인해볼 수 있는 코드는 면접 시에 작성한 코드뿐이다.
- 따라서 면접 시에 최고의 코드를 만들 수 있어야 한다. 자신이 사용할 언어를 가다듬고 가능하면 가장 좋은 코드를 만들자.
- 프로그래밍 문제는 코딩 실력과 문제 해결 능력을 동시에 평가할 수 있도록 만들어진다.
- 면접관이 정말로 원하는 것은 지원자가 문제를 푸는 각 단계들을 어떻게 진행하는지를 보는 것이다.
- 이런 면접에서 문제를 풀 때는 지원자와 면접관이 계속해서 의견을 주고받게 되며, 문제를 풀다가 막히면 면접관이 힌트를 제시하면서 정답을 맞출 수 있도록 도와준다.
- 지원자가 힌트를 받은 다음에 자신의 능력으로 문제를 풀어나가는 동안 보여주는 사고력과 문제 해결력 또한 매우 중요하다.
- 각 단계를 차근차근히 밝아나가면서 각 단계를 해결하는 사고 과정을 정리해서 대답해야 한다.
- 중요한 것은 어떤 프로그래밍 퍼즐의 정답을 외워서 말하는 것이 아니라 그 밑에 깔려 있는 개념을 제대로 이해하고 있다는 것을 보여주는 것이기 때문이다.
- 문제를 푸는 과정에서 자신의 프로그래밍에 대한 지식 전반을 보여주기 위해 문제와 연관된 다른 내용을 언급하고 싶은 경우가 있다.
- 그런 기회가 있으면 저 이런 지식도 갖고 있어요와 같이 논리적인 사고 능력을 갖추고 있으면서도 컴퓨터에 대한 지식도 출중하고 의사소통에도 능하다는 것을 보여줘야 한다.
- 문제를 풀 때 항상 무슨 일을 하고 있는지 계속해서 설명하는 습관을 가지자.
문제 해결
- 문제를 풀때 우선 문제를 완벽하게 이해하는 것이 중요하다.
- 몇 가지 구체적인 예를 시도해보고, 문제 해결 과정을 알고리즘으로 일반화하고 제대로 된 알고리즘이 만들었다는 확신이 설때 그 내용을 분명하게 설명하자.
- 코드 작성은 가장 마지막에 할 일이다.
기본 단계
- 면접 문제를 해결하는 가장 좋은 방법은 쳬게적인 접근법이다.
[1] 문제를 확실히 이해한다.
- 문제를 이해하지 못하면 주저하지 말고 면접관에게 문제에 대한 질문을 해야 하며, 제대로 이해하기 전에 무작정 풀기 시작하는 일은 금물이다.
- 진짜 문제가 되는 부분을 찾아내서 그런 부분을 분명히 하기 위한 제대로 된 질문을 던지는 것이 정답으로 가는 데 있어서 핵심이 될 수 있다.
[2] 일단 문제를 이해하고 나면 간단한 예를 시도해본다.
- 이렇게 예를 시도하다 보면 문제를 어떻게 풀어야 할지 감을 잡을 수도 있고, 혹시라도 잘못 이해한 부분이 있을 경우 오류를 정정할 수도 있다.
- 예를 시도하는 것은 체계적이고 논리적인 사고 능력을 보여줄 수 있는 기회가 되기도 한다.
[3] 문제 풀이에 사용할 알고리즘과 자료구조에 초점을 맞춘다.
- 이 단계에서는 면접관과의 의사소통이 중요하다.
- 계속해서 면접관에게 지금 무엇을 하는지 얘기하자. 얘기를 하다 보면 면접의 핵심이라고 할 수 있는 자신의 능력을 보여주는 데도 도움이 되고, 면접관이 힌트를 줄 수도 있다.
- (1)문제에 대해서 오랫동안 생각해서 한 번에 제대로 된 코드를 짜는 사람과 (2)무턱대고 달려들어서 코딩하면서 계속 에러만 내고 내가 지금 뭘 하고 있는지 파악도 안 되는 사람 가운데 어떤 사람과 일하고 싶은 마음이 생길지 입장 바꿔 생각해보자.
- 당연히 전자 쪽이 더 나을 것이다.
[4] 알고리즘과 구현 방법을 알아내고 나면 면접관에게 풀이를 설명한다.
- 이렇게 하면 지원자가 코딩을 시작하기 전에 면접관이 풀이에 대해 어느 정도 평가해볼 수 있다.
- 면접관이 긍정 또는 부정적인 의견을 내거나, “안 되는 건 아닌 것 같은데, 분명 더 효율적인 풀이법이 있을 것 같네요” 같은 응답도 나올 수 있다.
- 어느 쪽이든, 코딩으로 넘어갈지 알고리즘을 다시 살펴봐야 할지에 대해 아주 중요한 정보를 얻을 수 있다는 것은 분명하다.
[5] 코딩을 할 때도 뭘 하고 있는지 설명한다.
- 예를 들어, “여기에서는 배열을 전부 0으로 초기화합니다” 같은 식으로 설명을 한다면, 면접관 입장에서 코드를 더 쉽게 따라 갈 수 있다.
풀이에 대한 코드를 작성하기 전에, 그리고 코드를 작성하는 도중에도 계속해서 설명을 하자. 끊임없이 떠들자.

[6] 필요하다면 질문을 한다.
- 레퍼런스에서 찾을 수 있을 법한 내용이라면 면접관한테 질문을 해도 큰 감점 사유가 되진 않는다.
- 예를 들어, “잘 기억이 안나서 그러는데요, 지역화된 날짜 시각을 출력할 때 어떤 형식 문자열을 쓰는지 알 수 있을까요?” 같은 질문은 별로 해가 되진 않는다.
[7] 코드를 완성하고 나면 바로 몇 가지 예를 시도해보고 맞는지 확인한다.
- 자기가 만든 코드가 적어도 자기가 시도해본 예에 대해서 제대로 작동한다는 것을 분명하게 보여줄 수 있다.
- 그리고 자신의 사고 과정 및 결과를 확인하고 버그를 찾아내고자 하는 업무 자세를 보여줄 수 있는 기회도 된다.
[8] 모든 오류 및 특수 상황, 특히 경계 조건을 확인한다.
- 프로그래밍을 하다 보면 오류나 특수 상황을 무시하는 경우가 종종 있다.
- 모두 작성할 시간 여유가 없다면 적어도 말로 오류 확인이 필요하다는 설명은 해줘야 한다.
- 오류 및 특수 상황을 제대로 커버하면 면접관에게도 좋은 인상을 남길 수 있고 문제를 올바르게 푸는 데도 도움이 된다.
문제를 풀다가 막히는 경우
- 문제를 풀다가 막히는 일은 흔이 일어나는 일이며, 이것 자체도 면접의 중요한 부분이라고 할 수 있다.
- 만약 문제를 풀다가 갑자기 막히게 됐을 때 포기하거나 좌절하는 것은 최악의 대응책이다.
- 계속해서 문제에 대한 관심을 가지고 문제를 풀려고 시도하는 모습을 보이자.
예를 다시 따져본다.
- 예를 다시 확인하면서 지금 하고 있는 것을 분석해보자. 시도했던 특정 예를 일반적인 경우로 확장시켜보자.
- 면접관에게 정답을 찾아내기 위한 끈기를 보여줄 수 있는 셈이기 때문에 크게 나쁠 것은 없다.
다른 자료구조를 시도해본다.
- 연결 리스트, 배열, 해시 테이블, 이진 검색 트리 같은 다양한 자료구조를 써보자.
- 올바른 자료구조를 사용하는 것만으로 문제 풀이가 훨씬 수월해지는 일도 흔하다.
언어에서 그리 많이 쓰이지 않는 기능 또는 고급 기능을 고려해보자.
- 때때로 그런 기능을 활용하는 것이 문제 풀이의 핵심이 되는 경우도 있다.
면접에서 다루는 코딩 문제의 답은 대체로 짧은 편이다.

코드가 30줄을 넘기는 경우도 드문 편이고, 50줄을 넘기는 일은 거의 없다고 봐도 된다.

코드가 너무 길어지면 엉뚱한 방향으로 가고 있을 수도 있다.

Reference

프로그래밍 면접 이렇게 준비한다
Read All