Daehyunii's Dev-blog

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

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

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

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

9.1 삽입 정렬 소개 삽입 정렬이란, 배열의 왼쪽 끝의 숫자를 정렬이 끝났다고 간주한다. 그리고 아직 작업하지 않은 숫자 중에서 왼쪽 끝에 있는 숫자를 꺼내서 왼쪽에 있는 작업이 끝난 숫자와 비교한다. 왼쪽의 숫자가 크다면 두 개의 숫자를 바꾼다. 이 작업을 자신보다 작은 숫자가 나타나거나 왼쪽 끝에 도달할 때까지 반복하여 정렬하는 방법이다. 말 그대로 삽입 정렬은 가장 왼편의 값을 정렬이 완료되어 있는 값으로 보고 나머지 요소들을 하나씩 꺼내와 정렬되어 있다고 가정한 왼편의 요소들과 비교하여 정렬되어야 하는 위치에 삽입하는 방식이다. 의사코드 1. 배열의 두 번째 요소를 선택하여 반복을 시작한다.(왜냐하면 가장 앞에 있는 요소는 정렬이 완료되었다고 간주하기 때문이다.) 2. 그 다음 두 번째 요소를 ..

8.1 선택 정렬 소개 선택 정렬은 버블 정렬과 비슷하지만 약간의 정렬 방식에 차이점이 있다. 많은 스왑을 통해서 가장 큰 값을 맨 뒤에 위치시키는 대신, 한 번에 모든 요소를 비교하여 가장 작은 값을 맨 앞에 위치시킨다. 그리고 그 요소를 제외한 나머지 요소들을 다 비교하여 가장 그 중 가장 작은 값을 첫 번째에 정렬된 요소 다음에 위치시킨다. 즉 배열내의 요소들 중 최솟값을 찾아 마지막에 바꾸어 맨 앞에 정렬시킨다. 우선 비교를 해야 하기 때문에 비교해야 할 요소들 중 가장 앞에 있는 값을 최솟값으로 잡고 그 다음 요소들과의 비교를 통해 최솟값을 찾는다. 이렇게 찾은 최솟값은 배열의 맨 앞에 정렬시키고, 그 다음 루프에서는 제외시키고 나머지를 비교한다. 이 과정을 반복하여 정렬하는 방식이 선택 정렬이..

지금 부터는 정렬에 대해서 공부하려고 한다. 정렬이란 말 그대로 데이터를 일정한 기준을 가지고 재배열하는 과정을 말한다. 정렬을 하는 방식에는 많은 방법이 존재하고 각각의 정렬 알고리즘마다 장/단점을 지니고 있다. 또한 정렬을 할 수 있는 많은 메서드들이 존재한다. 그러한 메서드들을 잘 활용하는것도 중요하겠지만, 그 동작 원리를 아는것 또한 굉장히 중요한 일이다. 대표적이고 일반적인 정렬 방식이 버블 정렬, 선택 정렬, 삽입 정렬이 있고 그 뒤로 효율성을 개선시킨 정렬 방식들이 있다. 버블 정렬, 선택 정렬, 삽입 정렬은 효율성이 떨어져 잘 사용되지는 않지만 특정 상황에서는 유용한 정렬방식일 수 있다. 7.1 버블 정렬 : 개요 버블 정렬은 흔히 사용되지는 않는다. 다른 정렬 알고리즘에 비해 비효율적이기..

6.1 선형 검색(선형 탐색) 오늘 공부한 내용은 검색 알고리즘에 대해서 공부했다. 검색 알고리즘이란 예를 들어 회원가입시 아이디가 중복되는 경우 중복된 아이디가 있는지 없는지 확인을 해야하는 경우 등 이러한 문제를 해결하기 위한 일련의 과정이 바로 검색 알고리즘이다. 우선 자바스크립트는 다양한 검색 관련 메서드들을 제공하고 있다. 1. indexOf : 메서드를 통해 배열내에 해당 요소가 있다면 해당 요소의 인덱스 번호를 반환해주고, 없다면 -1을 반환한다. 2. includes : 배열 내에 특정 요소가 포함되어 있는지 확인하여 불리언값을 반환한다. 3. find : 자신을 호출한 배열의 요소를 순회하면서 인수로 전달된 콜백 함수를 호출하여 반환값이 true인 첫 번째 요소를 반환한다. 4. find..