너비우선탐색이란 무엇인가? 트리나 그래프를 탐색하는 기법 중 하나로써 너비(Breadth)를 우선적으로 탐색하는 방법이다. 너비우선탐색 구현을 위해서 보통 큐(Queue) 자료구조를 이용한다. 너비우선탐색의 동작 루트 노드부터 탐색을 시작한다. 기준 노드에 자식 노드들이 존재한다면 큐에 추가하고, 자기 자신은 큐에서 나온다. 위의 과정을 반복한다. 큐에 아무것도 존재하지 않게 된다면 탐색이 종료된다. 너비우선탐색 주의사항 만약 너비가 넓은 트리나 그래프라면 큐에 저장해야하는 너비 요소들이 많아지므로 공간복잡도가 증가한다. 따라서 너비우선탐색을 효과적으로 사용하기 위해서는 너비가 좁은 트리나 그래프를 대상으로 사용하는 것이 좋다. 구현 // 트리 구현체 class BST { constructor() { t..
사진출처 : https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC 트리란 무엇인가? 트리는 부모, 자식 노드의 관계를 정의한 자료구조라고 볼 수 있다. 트리에 속한 노드는 부모-자식 관계에 따라 부모가 자식을 가르키는 방향으로 진행된다. 이 때 모든 노드는 루트 노드와 멀어지는 방식으로 연결된다. 이진 탐색 트리의 동작 모든 부모 노드가 최대 2개의 자식 노드(left, right)를 가진다. (모든 이진트리의 공통점) 왼쪽 자식 노드는 부모보다 항상 작고, 오른쪽 자식 노드는 부모보다 항상 크다. 이진 탐색 트리가 단순 이진 트리보다 빠른 이유 단순 이진 트리는 부모 노드가 최대 2개의 자식노드만 가진..
에라토스테네스의 체 고대 그리스 수학자인 에라토스테네스가 고안했다. 주어진 자연수보다 작거나 같은 소수들이 어떤 것들이 있는지 찾아내는 알고리즘이다. 주어진 자연수 만큼 표를 그려놓은 뒤, 소수의 배수들을 지워나간다. 최종적으로 남은 숫자들은 소수이다. 자연수 25에 소수가 몇개 포함되어 있는지 에라토스테네스의 체를 이용해 판별해보자. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 자연수 1은 소수가 아니다. 2는 유일한 짝수인 소수이다. 2는 소수로써 남겨두고 2의 배수들은 전부 지워준다. 3은 소수이다. 3은 소수로써 남겨두고 3의 배수들은 전부 지워준다. 4는 이미 합성수라고 이전에 결론이 났다. 넘어간다. 5는 소수이다. 5는..
유클리드 알고리즘 유클리드 알고리즘은 두 자연수의 최대공약수를 효과적으로 구하는 알고리즘이다. 두 자연수의 최대공약수를 알고 있다면, 두 자연수의 최소공배수도 쉽게 구할 수 있다. 두 자연수의 최대공약수를 구하는 원시적인 방법은 아래와 같다. 각각 자연수의 약수들을 전개한다. 전개된 약수 들 중 공통된 숫자들을 곱한다. 하지만 각 자연수의 약수를 구하는 작업은 굉장히 번거롭다. 프로그래밍적으로도 시간이 많이 걸리는 작업이다. 이를 간단히 해결하기 위해 두 자연수의 최대공약수를 구할때는 유클리드 알고리즘을 사용한다. 유클리드 알고리즘은 유클리드 호제법이라고도 한다. https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC..
더블 링크드 리스트 구현 목표 더블 링크드 리스트 설계하기 싱글 링크드 리스트와 더블 링크드 리스트 비교하기 더블 링크드 리스트의 기본적인 요소 구현하기 싱글 링크드 리스트와의 비교 더블 링크드 리스트와 싱글 링크드 리스트의 차이는 prev 포인터의 추가 유무입니다. 더블 링크드 리스트는 prev라는 포인터가 하나 더 추가됩니다. 그 외엔 같습니다. prev의 존재로 node를 탐색하는데 있어 싱글 링크드 리스트보다 절반의 시간이 걸립니다. 하지만 추가적인 메모리가 들게 됩니다. (메모리 사용량이 싱글 링크드 리스트보다 많습니다.) 시간복잡도(BigO) 삽입(Insertion) - O(1) 삭제(Removal) - O(1) 검색(Searching) - O(N) 접근(Access) - O(N) 기술적으로 ..
싱글 링크드 리스트(Singly Linked List) 목표 싱글 링크드 리스트(Singly Linked List)가 어떤 것인지 정의하기 배열(Array)와 링크드 리스트(Linked List)의 차이점에 대해 비교해보기 싱글 링크드 리스트의 삽입, 삭제, 순회 등의 메서드를 직접 구현해보기 링크드 리스트(Linked List)가 뭔가요? 링크드 리스트는 head와 tail, length 프로퍼티로 구성된 자료구조 입니다. 링크드 리스트 내부에서는 노드가 별도로 존재하며, 각 노드는 노드에 연결된 값(value)과 다음 노드를 연결하거나 null과 연결되는 포인터(pointer)로 구성됩니다. 링크드 리스트와 어레이의 비교 리스트 리스트는 인덱스가 없습니다. 리스트의 노드는 포인터에 의해 다음 노드로 ..
일단 들어가기에 앞서서... 퀵정렬은 나에게 있어 정말 정말 난해한 정렬이었다. 사실 지금도 제대로 이해하고 있지 않은 것 같다. 그래도 지식을 견고히 하기 위해 일단 포스팅 해본다. 퀵 정렬은 어마어마하게 빠르다고 해서 붙여진 이름으로 합병정렬과 비슷하게 동작하지만 매우매우 직관적이지 못하다. 다만, 컴퓨터의 입장에서는 합병정렬보다 효율적일 수 있는 알고리즘이다. 연산 자체가 캐시 메모리에 최적화되어 CPU의 부하를 줄여주는 특징이 있다고 하는데 일단 그렇다는 키워드만 얻어놓고, 다음에 운영체제를 공부할 때 알고리즘과 엮여서 공부해보면 될 것 같다. 퀵 정렬(Quick Sort) 퀵 정렬은 배열 내 피봇(중심축)을 이용해서 엘리먼트를 정렬하는 정렬 방법인데, 합병정렬과의 차이점은 합병정렬이 기존의 배열..
합병정렬(merge sort)부터는 기본 정렬(버블, 선택, 삽입)보다 약간 복잡해진다. 하지만 성능은 훨씬 좋아진다. 정렬 알고리즘에서 빼놓을 수 없는 합병정렬에 대해 한 번 공부해보자. 폰 노이만 합병정렬은 폰노이만이 1945년에 개발한 정렬 알고리즘이다. 기초적인 정렬 알고리즘들(선택, 버블, 삽입)은 아무리 효율성을 고려한다고 해도 결국 배열을 싹 훑어내면서 정렬을 해야하는, 태생적인 O(N^2)의 시간복잡도를 가졌었다. 하지만 폰 노이만의 합병정렬은 알고리즘에 분할과 정복을 도입하여 정렬의 시간 복잡도를 크게 낮추었다. 발상 자체가 굉장히 천재적이다. 합병정렬의 분할과 정복(합병) 최대한 추상적으로 설명해보자면... 분할 먼저 정렬할 배열을 반으로 분할한다. 받은 배열을 또 절반으로 나눈다. 절..
삽입정렬은 배열의 좌측을 정렬된 배열로 두면서 오른쪽의 엘리먼트를 점진적으로 배열의 좌측에 하나씩 삽입해가며 정렬해가는 방식이다. 버블정렬은 큰 값을 뒤로 빼면서 정렬해 나아가고 선택정렬은 작은 값을 앞에 두면서 정렬해 나아간다. 삽입정렬은 일단 좌측의 엘리멘트들을 정렬되었다고 본다. 그리고 우측의 엘리먼트를 좌측의 엘리먼트와 하나하나 비교하며, 우측 엘리먼트를 좌측 엘리먼트에 삽입해가면서 정렬한다. (이러한 이유로 좌측의 정렬된 엘리먼트가 점진적으로 증가한다.) 위의 설명에 따른 삽입 정렬의 의사코드는 아래와 같다. 의사코드 배열의 두번째 엘리먼트부터 시작한다. (첫번째 엘리먼트는 자체로 정렬이 되었다고 가정하기 때문) 이제 두번째 엘리먼트를 첫번째 엘리먼트와 비교하고, 필요하다면 값을 삽입한다. 비교..
선택정렬은 기초적인 정렬 알고리즘 중 하나로써 효율성이 좋다고 평가받지 못하는 알고리즘이지만, 그래도 기초가 가장 중요하다는 관점에서 꼭 배워야만 하는 알고리즘이라고 할 수 있다. 선택정렬은 버블정렬과 비슷하지만 뚜렷한 한가지 차이점이 있다. 버블정렬 : 최대값을 선택하여 연산하면서 계속 뒤로 빼나간다. 선택정렬 : 최소값을 제일 앞에 두는 방식으로 큰 값들을 뒤로 빼나간다. 선택정렬 의사코드(Psuedocode) 배열의 첫번째 엘리먼트를 최소값 포인터로 일단 설정한다. 최소값 포인터를 다음 엘리먼트의 값과 비교를 하며, 현재 최소값 포인터보다 작은 값이 나올때까지 반복한다. 만약, 더 작은 값이 있을 경우, 최소값 포인터를 더 작은 값으로 재할당한다. 배열의 순회가 끝났다면, 가장 작은 값 엘리먼트와 ..
