[TIL] 2022-03-23/24 / 3, 4일차

 

오늘 배운 내용(3, 4일차)

 

자료구조와 알고리즘

 

실력 있는 개발자일수록 올바른 데이터, 자료구조 그리고 알고리즘을 골라 좋은 소프트웨어를 만들 수 있다. 적절한 자료구조와 알고리즘을 통해 만들어 낸 결과물이 프로그램이 된다.

 

자료구조

 

메모리를 효율적으로 사용하고 빠르고 안정적으로 데이터를 처리하는 것이 궁극적인 목표이다. 상황 by 상황. 상황에 따라 특정 자료구조가 유리하고, 불리하기 때문에 적절히 자료구조를 선택하는 것이 중요하다.

 

• Stack
• Queue
• Graph
• Tree
• 기타 등등

 

 

알고리즘

 

특정 문제를 효율적이고 빠르게 해결하는 것이 궁극적인 목표이다. 문제를 해결하기 위한 절차를 공식화한 형태로 표현하는 것을 의미한다. 다른 말로 수학적으로 표현할 수 있다는 것을 의미한다.

 

• 이진 탐색
• 최단거리 탐색
• 기타 등등

 

자료구조와 알고리즘이 중요한 이유?

 

실무에서 중요하다고 생각하는 것은 다음과 같다.

1. 기초 코딩 능력 : 코딩 능력, 논리적 사고 능력 -> 문제 해결 능력을 알 수 있다.
2. 전문 분야 지식 : 백&프론트 엔드, 딥러닝 등 특화된 전문 지식을 의미
3. 기본 cs 지식 : OS, 네트워크, SW 공학, 컴퓨터 구조 등 학문적 지식을 의미하며 탄탄할수록 업무상 예외 사항에 빠르게 대응할 수 있다.

 

위 사항 중 1번은 자료구조&알고리즘을 공부하면서 능력치를 키울 수 있다. 실무에서는 특정 프레임워크나 라이브러리를 능통한 사람보다는 기초 코딩 능력을 토대로 빠르게 변하는 세상에서 발생하는 문제를 해결할 수 있는 인재를 원한다. 따라서 새로운 기술을 빠르게 습득할 수 있고, 적용할 수 있는 사람을 원하는 것이다. 논리적 사고가 결핍된 사람은 많은 시가를 투자하더라도 좋은 코드를 작성할 수 없다.

 

문제 해결 능력은?

• 논리적 사고 : 어떤 현상이 존재할 때 추론을 통해 구조화하고 해답을 찾는 것을 말한다. 해결 방법의 정당성이 중요
• 전산화 능력 : 현실에 있는 것을 컴퓨터 프로그래밍 세계로 구현하는 능력, 즉 컴퓨터적 사고가 가능한지
• 엣지 케이스 탐색 : 예외사항을 잘 예측할 수 있는지?

이 세 가지가 문제 해결에서 가장 중요하다고 할 수 있다.

 

자료구조와 알고리즘을 배웠을 때 좋은 점?

 

자료구조, 알고리즘을 잘 익혀두었을 때 좋은 점은 잘 변하지 않는다는 것에 있다. 예를 들어 최단거리 알고리즘은 약 70년 정도 된 다익스트라 알고리즘을 사용하고 있다. 대표적인 것들은 아직도 사용하고 있기에 익혀둔다면 문제를 해결하는데 쉬울 것이다.

 

시간 복잡도

 

우리가 프로그램의 성능을 파악하는 방법은 무엇일까. 우선 고려해야 할 사항으로는 데이터 입력의 크기, HW의 성능, OS 성능, 컴파일러 최적화, 비동기 로직 등이 있다. 동일한 사양과 사항에서 성능을 측정하더라도 동일한 결과는 나오지 않는다(비슷한 수준의 성능). 실행 환경과 메모리 사용량에 따라 제각 기라서 정확하게 성능을 파악하는 것은 불가능하다.

 

따라서 비슷한 수준의 성능을 표현해 대략적 성능을 표기하기로 했고, 이를 위한 것이 Big-O 표기법이다.

 

Big-O (빅 오) 표기법 (개념 이해하기) | 알고리즘 | Khan Academy

 

Big-O 표기를 할 때, 다른 건 무시하고 2가지만 기억하면 된다.

1. 상수항은 무시한다
2. 차수가 가장 높은 항 이외의 항은 무시한다

 

Javascript에서 성능을 측정하는 방법? Date 객체를 이용해서 측정할 수 있다.

const start = new Date.getTime();
// 코드 내용
const end = new Date.getTime();
console.log(end-start);

 

 

자료구조의 종류

 

단순 구조를 제외하고 크게 2가지 종류로 나눌 수 있다.

1. 선형 구조 : 배열, 연결 리스트, 스택, 큐
2. 비선형 구조 : 트리, 그래프

 

 

배열

 

배열은 순차 리스트로 연관된 데이터를 다룰 때 사용한다. 일련의 연관된 데이터가 연속적인 형태를 띠고 있다. 배열에 포함된 원소는 순서대로 index가 붙는다(0부터 시작 ~ 배열의 길이 - 1).

 

배열의 특징

 

고정된 크기를 갖고 있어 일반적으로 동적으로 크기를 변경할 수 없으나 Javascript와 Python과 같은 대부분의 스크립트 언어는 동적으로 크기를 변경할 수 있게 설계되어 있다.

 

탐색 시 배열에서 특정 요소를 탐색할 때 정확한 index를 알고 있으면 O(1)만에 찾을 수 있다.

삭제 시에도 정확한 index를 알고 있다면 O(1)만에 찾을 수 있다. 그리고 해당 원소를 삭제하면 해당 index에 빈자리가 생겨 비효율적이다. 빈자리를 메우기 위해 배열의 요소들을 앞당긴다면 최악의 경우 선형 시간 O(N)이 걸리게 된다.

추가 시 배열의 크기가 아직 여유가 있을 때 추가를 하면 O(1)만에 추가를 할 수 있지만, 중간에 넣는 경우 해당 요소를 기준으로 원래 있던 요소부터 마지막 요소까지 한 칸씩 옮겨야 하므로 최악의 경우 O(N)이 걸리게 된다. 

 

배열은 추가와 삭제가 반복되는 로직에서 사용하는 것은 좋지 않다(O(N)). 탐색이 많은 상황에서 유리한 자료구조이다.

 

연결 리스트(Linked List)

 

배열을 사용할 때 추가, 삭제가 반복되는 로직이 비효율적인데, 이때 적합한 자료구조가 연결 리스트이다. 연결 리스트는 각 요소를 포인터로 연결해 관리하는 선형 구조의 자료구조로 각 요소는 노드라고 명하고 데이터 영역과 포인터 영역으로 구성된다.

 

연결 리스트의 특징

 

메모리가 허용하는 한 요소를 동적으로 계속해서 추가할 수 있다. 탐색 시간은 O(N)이 걸린다. 요소를 추가, 삭제할 때에는(추가할 곳을 찾는 것은 고려하지 않음) O(1)이 걸리게 된다. 탐색 시간과 추가, 삭제 시간이 배열과 정 반대이다.

 

연결 리스트의 종류로는 다음과 같다.

• Singly Linked List
• Doubly Linked List
• Circular Linked List

 

배열과의 차이점

 

메모리에서 차이가 있다. 배열은 순차적인 일련의 데이터가 들어가 있어 메모리 영역을 연속적으로 사용하는 반면, 연결 리스트는 그렇지 않기 때문에 메모리 이곳저곳에 영역이 퍼져있다. 순차적으로 존재하지 않기 때문에 해당 메모리 영역을 알기 위해 포인터를 사용한다.

 

연결 리스트의 핵심 로직

 

연결 리스트를 구현할 때 핵심이 되는 로직은 다음과 같다.

1. 요소 찾기
2. 요소 추가
3. 요소 삭제

예를 들어 데이터 4를 찾는다고 가정하면, 탐색은 가장 앞선 쪽인 Head 포인터에서 시작한다. 이 Head 포인터를 참고해 다음 노드를 탐색하고, 다음 노드에서도 포인터를 통해 그다음 노드를 탐색한다. 원하는 데이터 4가 있는 곳까지 반복해서 탐색하므로 수행 시간은 O(N)이다.

 

데이터 3을 2와 4 중간에 추가하려고 한다면(탐색은 고려하지 않는다, 미리 찾았다고 가정), 추가할 요소의 포인터를 4를 가리키도록 만들고, 이전 노드인 2의 포인터를 추가한 3을 가르키도록 한다. 따라서 수행 시간은 O(1)이다. 탐색을 하는 경우에는 O(N)이 걸리기 때문에 추가를 위해 탐색을 하지 않도록 코드를 작성하는 것이 중요하다.

 

데이터 2를 삭제하는 경우에는 추가와 비슷한 구조로 진행된다. 삭제할 이전의 요소가 삭제될 요소의 다음 요소를 가르키도록 수정하고 해당 데이터를 삭제하면 된다. 이때 수행 시간은 O(1).

 

Singly Linked List에서 리스트 크기를 구하는 size 메서드를 만들기

 

size(){
    let currNode = this.head;
    let cnt = 0;
    if (currNode === null ) return 0

    while(currNode !== null){
        cnt += 1;
        currNode = currNode.next;
    }
    return cnt
}

처음에는 맨 처음 노드부터 시작해 null이 아닌 노드를 만날 때까지 탐색하며 cnt를 증가시키며 리스트 크기를 구했다.

 

class SinglyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
}

 

이후에 연결 리스트를 생성할 때, size를 0으로 초기화하고, 삽입과 삭제가 일어날 때 size의 상태를 변화하도록 수정했다.

 

스택

 

스택은 LIFO 개념의 자료구조이다. Javascript 엔진에서 사용되는 CallStack에서 사용되는 것도 스택 구조이다. 코딩 테스트 문제에서 괄호를 다루는 문제 대부분은 스택으로 풀 수 있다.

 

올바른 괄호 문제 풀이

 

function solution(s){
    let arr = [];
    for(const item of s){
        if(item == '('){
            arr.push('(');
        }else if(item == ')'){
            if (arr.length == 0) return false;
            arr.pop();
        }
    }

    if(arr.length === 0) return true
    else return false
}

 

처음 문제를 풀 때, 괄호가 ')' 경우에 배열의 크기를 고려하는 조건문을 넣지 않고 풀어 몇 개의 테스트 케이스를 통과하지 못했다. 애초에 처음 들어온 괄호가 ')'라면 뒤에 어떠한 괄호가 오더라도 올바른 괄호가 되지 않기 때문에 해당 조건문을 추가해 해결했다.

 

Queue

 

큐은 대기열이라고 생각하면 편하다. FIFO 개념의 선형구조 자료구조이다. 맨 앞의 요소를 Front라고 하고 맨 마지막 요소를 Rear라고 한다.

 

• Linear Queue : 선형 큐
• Circular Queue : 환형 큐

 

Linear Queue

 

배열과 연결 리스트의 두 가지 방법으로 구현할 수 있다. 우선 배열로 표현하는 경우 스택과 달리 사용하기 어렵다. 배열로 사용하는 경우 0번째 index가 Front가 되고, 마지막 요소가 Rear가 된다. 배열로 구현했을 때, DeQueue(맨 앞 요소를 제거)하는 경우 Front부터 사라지는데 배열이라 빈자리가 메워지지 않기에 따로 관리해야 하는 어려움이 있다. EnQueue(맨 마지막 요소 뒤에 요소를 추가)하는 경우 배열의 push를 사용하면 되지만, 배열이 꽉 찬 경우엔 값을 추가할 수 없다. Javascript는 배열의 크기를 동적으로 다룰 수 있기 때문에 문제가 되지는 않는다. 그러나 Front나 Rear의 index 값이 무한정 커지는 문제가 발생할 수 있다.

 

배열로 사용할 때 문제점을 해결하기 위한 방법이 연결 리스트를 사용하는 것이다. 연결 리스트에서 Head는 선형 큐에서 Front가 되고, Tail은 Rear가 된다. 배열과 달리 index에 관한 고민은 하지 않아도 된다.

 

Queue를 사용할 때, shift 함수는 사용하지 않는 게 좋다. 큐 관련 문제를 서칭해 보았을 때, 대부분 shift와 unshift를 이용해 문제를 푸는 것을 봤다. 그러나 shift 연산은 선형시간(O(N))이 걸리기 때문에 큐에서 기대하는 로직이 수행되지 않으므로 사용하지 않는게 맞다.

 

Circular Queue

 

선형 큐와 같은 구조에서 Front와 Rear만 연결되어 있는 구조이다. 한정된 공간을 효율적으로 이용할 때 사용하는 자료구조이다. 구현을 할 때 maxSize를 고려해서 구현을 해야 한다.

 

해시 테이블

 

해시 테이블은 한정된 배열 공간에 key를 index로 변환해 값을 넣는다. 그렇다면 index는 어떻게 구하는가? key와 value를 받아 key를 해싱(Hashing)하여 index를 구한다.

 

삽입 연산은 O(1), key를 알고 있는 경우에 탐색과 삭제는 O(1)이다.

 

해시 함수

 

index로 변환하기 위해 사용하는 함수로 입력받은 값을 특정 범위 내 숫자로 변경하는 함수다. 정해진 구현 방법이 없기 때문에 재량 것 구현하면 된다. 가령 문자열을 해시 함수를 통해 index를 구한다면 ASCII Code를 참고해 구현할 수 있다.

 

해시 테이블의 문제점

 

해시 함수의 결과가 동일한 경우가 발생할 수 있고 이 경우 해시 충돌이 발생한다. 이때 해결할 수 있는 방법은 대표적으로 4가지가 있다.

 

1. 선형 탐사법 : 충돌이 발생하면 index를 한 칸 옆으로 이동한다.
2. 제곱 탐사법 : 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
3. 이중 해싱 : 충돌이 발생하면 기존 해시 함수가 아닌 다른 해시 함수를 이용해 index를 생성한다.
4. 분리 연결법 : 충돌이 발생할 경우 다른 index로 이동하지 않고 해시 테이블의 요소를 연결 리스트로 만들고 충돌이 발생한 자리에 그대로 추가한다.

 

그래프

 

점과 점을 연결하는 선으로 이루어진 비선형 자료구조이다. 정점과 간선은 각각 노드와 엣지로 표현할 수 있다. 인물 관계도, 지하철 노선도 등이 대표적인 예.

 

그래프의 특징

• 정점은 여러 개의 간선을 가질 수 있다.
• 방향 그래프와 무방향 그래프로 분류할 수 있다.
• 간선은 가중치를 가질 수 있다.
• 사이클이 발생할 수 있기 때문에 무한 루프를 주의해야 한다.

 

1. 무방향 그래프 : 간선으로 이어진 정점끼리는 양방향 이동이 가능하다(방향이 없다는 뜻).
2. 방향 그래프 : 간선에 방향성이 존재한다. (양방향이더라도 (A->B), (B->A) 간선은 서로 다른 간선이다.

 

그래프 구현 방법

• 인접 행렬 : 2차원 배열
• 인접 리스트 : 연결 리스트

 

인접 행렬은 정점의 크기만큼 2차원 배열을 만들고, 연결이 안 된 상태로 초기화한다. 열은 시작 정점이 되고 행은 도착 정점이 된다. true flag를 통해 나타낼 수 있고, 가중치를 표현하고 싶은 경우에는 null값과 가중치 값을 이용한다. 무방향 그래프를 구현할 경우 모든 값을 대칭으로 넣는다.

 

인접 리스트는 정점의 수만큼 배열을 만든 후 연결할 정점을 배열에 추가하면 된다. Javascript는 배열을 동적으로 변경할 수 있기 때문에 편리하다.

 

 

인접 행렬

 

방향 그래프의 정점이 연결된 정보가 주어져 있을 때, 인접 행렬을 구하는 방법

 

let arr = [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]]; // 방향 그래프 연결 정보
let graph = Array.from(Array(n + 1), () => Array(n + 1).fill(0)); // 비어 있는 그래프 선언
for (let [a, b] of arr) { // 방향 그래프 연결 정보를 탐색하며 그래프에 true flag 이용
	graph[a][b] = 1;
}

 

인접 리스트

 

마찬가지로 정보가 주어졌을 때, 해당 정점에서 갈 수 있는 정점을 배열로 추가해 준다. 주어진 정보가 커졌을 때 인접 행렬보다 효율적이다.

 

let arr = [[1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 5], [3, 4], [4, 2], [4, 5]];
let graph = Array.from(Array(n + 1), () => Array());    // 노드 갯수 만큼 빈 배열 생성
for (let [a, b] of arr) {   // 인접 리스트 생성, a번째 노드에서 갈 수 있는 b 노드 push
	graph[a].push(b);
}

 

부족했던 점

• 선택과제
• 연결 리스트 예외 찾기
• 알고리즘 구현
• 큐, 해시 실습 문제

 

느낀 점

 

"과거의 나를 반성한다." 학부생 때 알고리즘 수업과 정처기 자격증을 준비하며 자료구조, 알고리즘에 대해 접했던 경험 덕분에 수업 내용을 이해하는 건 어렵지 않았다. 과거에도 꼭 더 추가적인 공부를 해서 구현까지 해보자는 다짐을 했는데, 그때 실천하지 못했던 게 너무 크게 다가왔다. 머리로는 끄덕끄덕 이해가 되지만 구현을 하려고 하니 어려운 점이 한둘이 아니다. 

 

특히, 큐와 해시 관련 실습 문제를 다룰 때 어려웠다. 파이썬으로만 코딩 테스트를 준비해 왔는데 Javascript는 큐를 빌트인으로 제공하고 있지 않았고, 해시 관련 문제에서는 고차 함수를 다뤄봤던 적이 없어 매우 어렵게 다가왔다..