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

A Steadily Growing Developer

[Programmers] 17687. [3차] n진수 게임

2023-03-24

devFancy

Algorithm
문제 링크

성능 요약
- 메모리: 74.5 MB, 시간: 2.43 ms
구분
- 코딩테스트 연습 > 2018 KAKAO BLIND RECRUITMENT
Answer Code1(2023.03.24)

```java class Solution { public String solution(int n, int t, int m, int p) { StringBuilder convert = new StringBuilder(); StringBuilder answer = new StringBuilder();
Read All
기본적인 그래프 기법 : DFS, BFS

2023-03-23

devFancy

DataStructure

Read All
그래프

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