Daehyunii's Dev-blog

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

14.1 이중 연결 리스트(Doubly Linked Lists) 이중 연결 리스트는 단일 연결 리스트와 별반 다를게 없다. 단일 연결 리스트는 노드들의 연결이 하나의 방향으로만 이어져 있었다면 이중 연결 리스트는 노드와 노드가 서로 양방향으로 이어져 있는 자료 구조이다. 즉 각 노드의 방향 지시가 두 개씩 있다는 것이다. 또한 단일 연결 리스트에 비해 양방향으로 연결되어 있어 노드에 접근할 때 테일 또는 헤드 중에 더 가까운 곳을 택해서 접근할 수 있다. 단일 연결 리스트와 전체적인 구조는 거의 똑같다. 다만 방향을 양쪽으로 다 이어야 한다는 것을 주의하면 된다. 14.2 노드와 이중 연결 리스트 클래스 단일 연결 리스트와 다른 점은 prev 프로퍼티를 추가한 것 밖에 없다. class Node{ con..

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

13.1 단일 연결 리스트 소개(Singly Linked Lists) 단일 연결 리스트는 연결 리스트의 한 종류로 문자열, 숫자 등 무엇이든 원하는 데이터를 저장하는 자료 구조다. 단일 연결 리스트는 데이터와 데이터의 연결이 한 쪽 방향으로만 연결되는 자료 구조다. 배열처럼 순서에 따라 다수의 데이터를 저장한다. 하지만 배열과의 큰 차이점이 있다. 배열의 경우 각 데이터 요소들은 위치가 지정된다. 즉, 배열은 인덱스가 부여된다. 새로운 데이터 요소를 추가할 때 마다 배열은 그 위치에 따른 인덱스가 주어진다. 반면 연결 리스트들은 다음 데이터 요소를 가리키는 인덱스 없이 그냥 다수의 데이터 요소들로 구성되며 데이터에 접근하기 위해 사용할 인데스는 없다. 따라서 연결 리스트들은 다수의 노드들로 구성되고 각 ..

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

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

11.1 퀵 정렬 소개 퀵 정렬은 매우 빠르고 효율적인 정렬 방식이다. 재귀를 통해 해결하기 가장 쉬운 방법 중 하나이다. 우선 기본적으로 데이터를 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 피벗개념을 통해 정렬되는 방식이다. 즉 비교하는 요소가 하나만 있다면 이미 정렬이 된 것이다. 퀵 정렬에 있어서 가장 중요한 개념은 피벗이다. 퀵 정렬은 피벗 포인트라 불리는 단일 요소를 선택하고 이를 기준으로 작업을 수행한다. 예를 들어 피벗 포인트를 가운데 있는 요소로 정했다면 할 일은 해당 숫자보다 작은 숫자를 왼쪽으로 옮기고 피벗 포인트보다 큰 숫자는 오른쪽으로 옮기는 것이다. 이렇게 된다면 피벗 숫자 하나만큼은 올바른 위치에 정렬이 된다. 중요한것은 그 피벗 포인트 숫자 하나만 옳바른 위치에 ..

지금까지 공부했던 정렬들은 일반적인 정렬 알고리즘이었다. 이제는 보다 효율적인 정렬 알고리즘들에 대한 설명이다. 합병 정렬은 정확하게 말하면 분해와 합병을 하는 과정으로 정렬이 이뤄진다. 합병 정렬은 0개의 요소 또는 1개의 요소는 이미 정렬이 되어있다는 것을 활용하는 정렬 알고리즘이다. 즉 정렬되어 있지 않은 배열을 요소가 1개 또는 0개가 될 때까지 배열을 분할한 후 다시 정렬하면서 합병하는 것이다.(1개 또는 0개의 요소를 가지는 배열은 이미 정렬이 되어 있는 것이기 때문이다.) 우선 합병 정렬 알고리즘을 구현하기 위해서는 정렬되어 있는 두 배열을 합병하는 방법을 알아야 한다. 10.1 정렬된 두 배열 합병 의사코드 1. 우선 배열 두 개를 인수로 받는 함수를 정의하고, 마지막에 반환할 빈 배열을 ..