알고리즘/데이터구조/디자인패턴 관련 자료

* 알고리즘 연습을 위해 좋은 사이트

https://www.hackerrank.com/

HackerRank

https://www.geeksforgeeks.org/

GeeksforGeeks | A computer science portal for geeks

 

* 해쉬맵 장단점

- 검색 속도가 가장 빠름

- 저장 시간은 상대적으로 느림

- 데이터 양이 적더라도 일정 크기의 버킷을 가지고 있어야 하기 떄문에 리소스를 많이 사용함

https://m.blog.naver.com/PostView.nhn?blogId=mygirl2&logNo=40103053785&proxyReferer=https%3A%2F%2Fwww.google.com%2F

Vector, ArrayList, Object[], HashMap, TreeMap 의 장,단점(속도 등) 설명

 

* 깊이 우선 탐색(DFS)과 넓이 우선 탐색(BFS)의 차이

- DFS (Depth-First Search) : 모든 노드를 방문하고자 할 경우 사용, 자기 자신을 호출하는 순환 알고리즘 형태

- BFS (Breadth-First Search) : 인접 노드를 먼저 탐색, 두 노드 사이에 최단 경로 혹은 임의의 경로를 찾고자 할때 사용

검색 속도는 BFS가 DFS 보다 빠르다!

https://yunyoung1819.tistory.com/86

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

 

* 이진 탐색 트리 (BST : Binary Search Trees)

- Key-Value를 저장하기 위해 사용하는 자료 구조

- 이진 트리(Binary tree)에 이진 탐색(Binary Search) 알고리즘을 사용해 처리

- 왼쪽 노드(Left node)가 부모(Parent node)보다 작고, 오른쪽 노드(Right node)가 부모보다 크다

https://www.slideshare.net/choeunwoo/songorithm-balanced-searchtrees-53041698

Balanced Binary Search Trees

이진 탐색 트리의 탐색, 삽입, 삭제 방법

- 탐색 : 루트 노드부터 순회, 탐색해야 하는 값이 루트 노드보다 클 경우 오른쪽 자식을, 작을 경우 왼쪽 자식을 방문하고 같은 값일 경우 탐색을 마침, 방문한 노드가 NULL이 될 때까지 탐색값을 찾지못하면 해당 트리에 존재하지 않는 것으로 간주

- 삽입 : 탐색처럼 현재 노드와 값을 비교하여 왼쪽/오른쪽 자식 노드를 방문하는 것을 반복하다가 NULL을 만나면 해당 위치에 노드를 삽입하고 종료

- 삭제 : 트리 순회 중 삭제해야 하는 값을 발견하면 해당 노드를 삭제, 삭제된 빈자리는 오른쪽 자식 트리 중에서 가장 작은 값을 가지는 노드로 대체

https://wkdtjsgur100.github.io/binary-search-tree/

(C언어) 이진탐색트리(BST, Binary Search Tree) 구현

 

* 디자인 패턴

디자인 패턴 : 문제를 해결하기 위한 코드 구조를 일정한 형태로 정의하여 재이용이 용이하게 만든 패턴

https://gone-sw.tistory.com/4

[디자인 패턴] GoF의 디자인패턴 간단 정리.

 

* 기본 정렬 알고리즘

- 선택 정렬 (Selection Sort) : O(n^2)

- 삽입 정렬 (Insertion Sort) : O(n^2)

- 버블 정렬 (Bubble Sort) : O(n^2)

- 합병 정렬 (Merge Sort) : O(NlogN)

- 퀵 정렬 (Quick Sort) : O(N^2)

https://hsp1116.tistory.com/33

기본 정렬 알고리즘(Sorting Algoritm) 요약 정리 (선택, 삽입, 버블, 합병, 퀵) v1.1