BFS(너비 우선 탐색) BFS(Breadth-first search)는 같은 깊이에 있는 정점부터 탐색하는 알고리즘이다. BFS(너비 우선 탐색) - Queue 를 사용하여 구현 - 시작 지점에서 가까운 정점부터 탐색 - 시간 복잡도 O(정점의 수 + 간선의 수) Queue 를 사용한 BFS step 1 | Queue [ 1 ] Queue에 1을 enqueue step 2 | Queue [ 2 ] [ 3 ] [ 4 ] 1을 dequeue 하고, 자식 정점 2, 3, 4를 enqueue step 3 | Queue [ 3 ] [ 4 ] [ 5 ] [ 6 ] 2를 dequeue 하고, 자식 정점 5, 6를 enqueue step 4 | Queue [ 4 ] [ 5 ] [ 6 ] 3을 dequeue 하고, 자..

☘️ 정렬 정렬 정의 정렬이란 요소들을 일정한 순서대로(오름차순 or 내림차순) 열거하는 알고리즘이다. 정렬 방식 삽입 정렬 선택 정렬 버블 정렬 머지 정렬 힙 정렬 퀵 정렬 등。。。 버블 정렬 버블 정렬은 인접한 두 요소의 크기를 비교하여, 자리를 교환하면서 정렬하는 방식이다. 예) 오름차순 정렬 6과 4를 비교했을 때, 앞에 있는 6이 더 크기 때문에 자리를 교환한다. 다음으로 6과 1을 비교했을 때, 앞에 있는 6이 더 크기 때문에 자리를 교환한다. 다음으로 6과 2를 비교했을 때, 앞에 있는 6이 더 크기 때문에 자리를 교환한다. 6과 8을 비교했을 때, 정렬 순서가 맞기 때문에 자리를 교환하지 않는다. (첫번째 순회 완료) 첫 번째 순회를 완료했다. 그러면 맨 끝에 있는 8은 정렬이 완료 된 것..

☘️ 이진 탐색 이진 탐색 정의 이진 탐색은 정렬된 요소들을 절반씩 줄여가며 찾는 알고리즘이다. 이진 탐색 정렬이 되어 있어야 함 배열, 이진 트리 사용하여 구현 시간 복잡도 O(log n) 로 빠름 이진 탐색 구현 - 배열 원하는 숫자를 찾기 방법은 다음과 같다. 정렬된 배열에서 맨 앞을 left, 맨 뒤를 right, 가운데를 mid 로 설정 찾는 숫자를 mid 값과 비교 mid 값이 더 크면 right = mid - 1 mid 값이 더 작으면 left = mid + 1 새롭게 설정된 left 또는 right 값으로 mid 값 다시 설정 이를 반복하여 mid 값과 찾는 숫자가 같으면 종료 배열을 사용하여 이진 탐색을 구현하면 선형 시간 O(n) 이 소요된다. 그래서 이를 해결하기 위해 이진 탐색 트리..

☘️ 트라이(Trie) 트라이 정의 트라이는 트리 형태로 되어 있는 자료구조이다. 트라이 문자열 저장 문자열을 효율적으로 탐색하기 위한 자료구조 이전 정점으로부터 더해진 문자열 정보 가짐 트라이 특징 검색어 자동완성, 사전 찾기 트라이는 검색어 자동완성, 사전 찾기 등에서 활용된다. 효율적인 문자열 탐색 단순하게 문자열을 비교하여 탐색하는 것보다 효율적이게 찾을 수 있다. 탐색 시간 문자열을 탐색, 삽입하는 시간 복잡도는 문자열의 길이만큼 소요된다. 문자열 길이: L 시간 복잡도: O(L) 저장공간 각 정점이 자식에 대한 링크를 전부 가지고 있어 저장공간이 많이 차지한다는 단점이 있다. 트라이 구조 특징 빈 루트 트라이의 Root는 문자열이 없는 비어있는 상태이다. 간선(링크) 키 값 각 간선(링크)는 ..

☘️ 힙(Heap) 우선순위 큐 우선 순위가 높은 요소가 먼저 나가는 큐 힙(Heap)은 우선순위 큐를 구현하기 위한 가장 적합한 자료구조이다. 그러면 힙(Heap)은 무엇일까? 힙(Heap) 이진 트리 형태 우선 순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬됨 우선 순위가 높은 요소는 Root에 배치 여기서 우선순위 큐는 자료구조가 아닌 개념이고 힙은 우선순위 큐라는 개념을 구현하기 위한 자료구조이다. 만약 우선순위 큐를 힙이 아닌 배열을 사용하면 매번 우선순위에 따라 정렬이 되며, 단지 힙보다 효율이 떨어질 뿐이다. 우선순위 큐 != 힙 힙의 특징 우선 순위 먼저 나감 힙은 이진트리 형태로 우선 순위가 가장 높은 요소가 Root에 배치하고 항상 먼저 나간다. 최대 힙, 최..

☘️ 그래프 그래프 정의 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 그래프에서 정점은 Node, 간선은 Edge 라고 불리며, 아래 사진에서 파란색 원이 정점(node), 검은색 선이 간선(edge) 이다. 그래프 사용 예시 이러한 그래프가 사용되는 예시로는 지하철 노선로가 있다. 지하철역이 정점(node), 지하철역과 역 사이를 이어주는 것이 간선(edge) 이라고 할 수 있다. 그래프 특징 1. 다수의 간선 그래프는 비선형 구조라서 정점이 여러 개의 간선을 가질 수 있다. 비선형 구조 하나의 데이터에 여러 개의 데이터가 존재할 수 있고, 데이터 간 1:n 또는 n:n 관계를 가짐 2. 방향, 무방향 그래프 그래프는 방향이 있는 방향 그래프와, 방향이 없는 무방향 그래프가 있다. 3..

☘️ 해시 테이블 해시 테이블은 키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조 각 테이블에 해당하는 index를 해시 테이블에서는 buckets 이라고 하며, 테이블의 각 요소는 키와 값이 저장되어 있다. 해시 테이블에서 요소를 삽입하는 것은 상수 시간 O(1) 이 소요되며, 키를 알고 있을 경우 요소를 삭제, 탐색하는 것도 상수 시간 O(1) 이 소요된다. 해시 함수 입력받은 값을 특정 범위 내 숫자로 변경하는 함수 키 값을 해시 함수를 통해 해싱하여 buckets에 저장하며, 해시 함수는 특정한 구현 방법이 없어 사용자 마음대로 구현하면 된다. 해시 테이블 문제점 해시 함수를 통해 키 값을 해싱하는데, 만약 해시 함수의 결과가 동일하여 겹칠 수 있다는 문..

☘️ 스택(stack) 스택은 LIFO(Last In First Out) 로 "나중에 들어간 것이 먼저 나온다" 라는 개념을 가진 선형 자료구조이다. 예를 들어 아래부터 1, 2, 3, 4, 5 상자를 순서대로 넣으면, 뺄 때 순서대로 5, 4, 3, 2, 1 이렇게 되는 구조이다. 여기서 요소를 넣는 것을 Push, 빼는 것을 Pop 이라고 하며, 제일 위에 있는 요소를 Top이라고 한다. ☘️ 자바스크립트에서 스택(stack) 구현 자바스크립트에서 스택을 구현하기 위해 배열(Array)를 사용할 수 있다. 이미 배열에 push와 pop 함수가 구현되어 있어서 보다 편리하다. 그래서 아래 코드와 같이 배열을 사용하여 스택을 구현할 수 있다. 코딩 테스트에서 스택을 사용하는 경우로는 짝을 맞춰야 하는 문..

☘️ 연결 리스트 사용하는 이유 그 전 글에서 배열을 알아보았는데, 배열 같은 경우 원하는 위치에 데이터를 추가하고 삽입하는 경우에 시간 복잡도가 O(n) 으로 크다. 그래서 요소 추가와 삭제가 반복되는 로직 같은 경우는 배열을 사용하지 않고 연결 리스트를 사용하고, 배열은 탐색이 많은 로직에서 사용하면 좋다. 배열 - 탐색 유리 연결 리스트 - 요소 추가, 삭제 유리 ☘️ 연결 리스트란? 연결 리스트 정의 연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조로 각 요소는 노드라고 부르고, 각 노드에는 해당 노드의 값이 있는 데이터 영역과 다음 노드를 가리키는 포인터 영역으로 구성된다. 그리고 첫번째 노드를 헤드(Head)라고 부른다. 연결리스트의 핵심 로직은 요소 찾기 요소 추가 요소 삭제..

☘️ 배열 배열은 연관된 데이터를 연속적인 형태로 저장하는 복합 타입으로, 배열에 포함된 원소는 순서대로 인덱스가 붙는다. 또한 배열은 탐색이 유리한 자료구조이다. 만약 배열의 요소를 추가 및 삭제하면 O(n) 이 소요된다. 그래서 요소의 추가와 삭제가 반복되는 로직일 경우 배열을 사용하지 않는 것이 좋다. ☘️ 배열 생성 자바스크립트에서 배열은 다음과 같이 다양한 방법으로 배열을 생성할 수 있다. 또한 자바스크립트에서 배열은 크기가 고정되어 있지 않고, 필요에 따라 줄이거나 늘릴 수 있다. ☘️ 배열 요소 추가, 삭제 - push, pop, splice push와 pop을 사용할 경우 빅오 표기법이 O(1) 이다. 그러나 splice를 사용하여 중간에 값을 추가하거나, 제거하면 빅오 표기법이 O(n) ..