Daehyunii's Dev-blog

오늘 공부한 내용은 그래프와 그래프 순회에 대해서 공부했다. 그래프란 유한하고 변할 수 있는 꼭지점(노드)의 집합으로 구성된 데이터 구조이다. 이 꼭지점들의 집합에 순서가 없는 경우에는 무방향 그래프, 순서가 있는 경우에는 유방향 그래프라고 한다. 즉, 그래프는 노드와 노드들의 연결을 모은 것이다. 그러므로 트리도 그래프의 일종이다. 다만 트리는 몇 가지 규칙이 추가되어 부모와 자식노드로 구성되고 시작점인 루트가 존재하는 것이다. 하지만 그래프에는 부모 노드라는 것이 없고, 시작점도 없다. 다 동일한 노드일 뿐이다. 또한 그래프는 트리나 연결 리스트 같은 수준의 패턴이 없다. 자유로운 형식의 노드가 있고 그 사이에 연결만 있을 뿐이다. 또한 트리는 한 노드에서 다른 노드로 가는 경로가 딱 한 가지만 존재..

오늘 공부한 내요은 이진 힙과 해시 테이블이다. 이진 힙은 트리의 한 유형인 힙의 한 유형이다. 이진 힙도 트리의 규칙을 가지고 추가적인 규칙을 갖는다. 이진 힙의 규칙은 간단하다. 부모 노드는 자식 노드 보다 항상 큰 값을 갖거나(최대 이진 힙) 반대로 항상 작은 값을 갖는다.(최소 이진 힙) 또한 자식 노드는 최대 2개를 가질 수 있는데 자식 노드들 사이의 위치는 우선순위가 없이 항상 왼쪽 부터 저장이 된다. 그렇기 때문에 이진 힙은 배열로 표현이 되며, 간단한 수학적 규칙을 활용해서 자료를 저장하게 된다. 그렇기 때문에 이진 힙의 루트 노드에는 항상 가작 큰 값이 오거나 가장 작은 값이 오게 된다. 이러한 점을 활용해서 우선 순위 큐를 만드는데 활용할 수 있다. 우선 순위 큐는 노드에 우선 순위를 ..

오늘은 트리를 순회하는 방법에 대해서 공부했다. 앞서 이진 검색 트리에 대해서 공부했었는데 이진 검색 트리만을 위한 검색 방법이 아닌 트리형태의 자료 구조들을 전부 순회할 수 있는 대표적인 방법들에 대해서 공부했다. 오늘 공부하는 것은 개념적으로는 크게 어렵지 않았으나, 코드를 이해하는데 시간이 꽤 걸렸다. bfs방식은 루트 노드부터 시작해서 같은 레벨에 존재하는 모든 노드들을 먼저 순회한 후 또 다시 그 아래에 위치하는 노드들을 검색하는 방식이고 dfs방식은 루트 노드부터 시작해서 자식 노드로 또 그 노드의 자식 노드로 순회를 이어가면서 탐색하는 방법이다. dfs방식에는 다시 전위, 후위, 중위 방식으로 나뉠 수 있는데 순회한 노드를 마지막에 반환 할 배열에 언제 저장하느냐에 따라 달라지게 된다. 사실..

오늘은 스택과 큐 형태의 자료 구조 그리고 이진 검색 트리 자료 구조를 공부했다. 스택은 후입선출 형태를 갖는 자료 구조를 말하고 큐는 선입선출 형태를 갖는 자료 구조를 말하는 추상적인 개념이다. 즉, 어떤 자료 구조이든 후입선출, 선입선출의 규칙을 지켜 활용하면 스택과 큐가 되는 것이다. 모던 자바스크립트 책을 공부할때 종종 등장했었던 개념이었으나 그 당시에는 정확한 개념을 이해하지 못했었다. 하지만 이번에 공부를 하고 나서는 스택과 큐 개념에 대해서 확실하게 이해하게 되었다. 배열에 데이터를 저장할때는 push & pop 메서들를 활용해서 스택 형태로 데이터를 활용하는게 좋겠다는 생각이 들었다. shift & unshift는 인덱스를 다시 설정해야 하므로 적합하지 않음 앞서 공부했듯이 배열은 인덱스를..

오늘은 연결 리스트 자료 구조에 대해서 공부했다. 연결 리스트는 다시 단일 연결 리스트와 이중 연결 리스트로 나뉘게 된다. 단일 연결 리스트는 노드들을 단방향으로 연결하는 자료 구조이고, 이중 연결 리스트는 노드들을 양방향으로 연결하는 자료 구조이다. 배열과 비슷한 것처럼 보이지만 배열은 인덱스를 가지게 되어 데이터를 맨 뒤에 추가하거나 삭제하는 경우를 제외하고는 맨 앞에 데이터를 추가하거나 중간에 데이터를 추가하는 경우에는 인덱스가 다시 설정되어야 한다. 하지만 연결 리스트의 경우에는 인덱스 번호를 가지고 있지 않기 때문에 데이터를 중간에 추가하거나 삭제하더라도 단순히 데이터끼리의 연결만 다시 설정해 주면 되기 때문에 배열에 비해 효율성이 좋다. 그러나 해당 데이터에 접근을 하는 경우에는 인덱스를 가지..

오늘은 퀵 정렬에 대해서 공부했다. 앞서 배운 합병 정렬에 비해서 코드를 이해하는게 쉽지 않았다. 개념 자체도 조금은 생소하게 느껴졌다. 피벗을 정해서 피벗의 왼편에는 작은 숫자들로 또 오른편에는 큰 숫자들로 정렬하여 피벗 숫자만은 정렬이 되고 피벗 숫자를 중심으로 왼편과 오른편에 새로운 피벗을 정하고 또 큰 수는 오른편에 작은 수는 왼편에 정렬하는 방식으로 계속해서 재귀함수를 사용하여 반복하서 정렬된 배열을 반환하는게 퀵 정렬이었다. 가장 헷갈리게 만들었던 부분은 당연히 재귀를 머릿속으로 그리면서 따라가는게 어려웠다. 아니 따라가지 못했다. 그래서 종이에 하나 하나 대입해가면서 코드를 읽어 나갔다. 또한 스스로 느끼기에 가독성이 그렇게 좋아보이지도 않았다. 효율적인 측면을 따졌을때 정렬 알고리즘 애니메..

오늘은 정렬 알고리즘을 이어서 공부했다. 삽입 정렬과 한 단계 효율이 올라가는 합병 정렬에 대해서 공부했다. 우선 삽입 정렬의 경우에는 버블 정렬과 선택 정렬과 마찬가지로 효율이 좋은 쪽에 속하는 정렬 알고리즘은 아니었다. 일반적으로 O(n^2)시간 복잡도를 갖는 정렬 방식이다. 하지만 정렬 알고리즘 에니메이션을 통해 보았을때 거의 정렬이 되어 있는 배열을 정렬하는 것은 다른 알고리즘들에 비해 굉장히 빠르다는 것을 알 수 있었다. 즉 삽입 정렬의 경우에는 거의 정렬이 되어 있는 배열을 정렬해야 하는 상황에서 사용하기에 아주 알맞은 정렬 알고리즘이라는 것이다. https://www.toptal.com/developers/sorting-algorithms Sorting Algorithms Animations..

오늘은 버블 정렬과 선택 정렬에 대해서 공부했다. 알고리즘에 대해서 명확하게 개념 정의가 이뤄지지 않았었는데, 오늘을 기점으로 알고리즘이 무엇인지 조금씩 스스로 개념 정의가 된 것 같다. 우선 기존에 공부했던 내용들은 자바스크립트의 기본 개념에 대해서 공부한 것이고, 그 과정에서 배웠던 메서드들을 활용해서만 코드를 작성한다는 생각에 사로잡혀서 그랬던것 같다. 오늘 공부를 통해 배열을 정렬하는 방식에는 정말 많은 방법이 있다는 것을 알 수 있었다. 그리고 각각의 정렬하는 방법마다 장단점이 많이 있다. 버블 정렬과 선택 정렬의 경우에는 아래 링크를 통해서 정렬 알고리즘 애니메이션을 보았을때, 다른 알고리즘들에 비해 속도가 굉장히 느리다는 것을 시각적으로 확인할 수 있었다. 하지만 이를 공부하는 이유는 비효율..