❒ Description이분 탐색의 동작과정을 정리하자.     ❒ Binary Search 이진 검색이란 정렬된 배열에서  타깃을 찾는 검색 알고리즘이다. 어떠한 경우에는 O(logN)의 시간복잡도를 갖는다. 동작 방식은 아래와 같다.      ❒ 효율적인 중앙 찾기만약 아래와 같이 중앙 위치를 찾는면 중앙 값은 0이 나오게 된다.int start = Integer.MAX_VALUE;int end = Integer.MAX_VALUE;int mid = (start + end) / 2;그 이유는 start와 end의 합이 자료형의 최댓 값을 넘어가기 때문이다.  이런 경우를 방지하기 위해서 다음과 같이 중앙 값을 찾아야 한다.int start = Integer.MAX_VALUE;int end = Integ..

❒ Description[LeetCode#75] Sort Colors 문제를 풀면서 알게된 Dutch National Flag 알고리즘을 정리해보자.     ❒ DNF 알고리즘1. DNF란?Dutch National Flag Problem(네덜란드 국기 문제)은 컴퓨터 과학자 다이크스트라가 제안한 알고리즘문제로, 배열 내의 요소들을 세 개의 범주로 나누는 문제다. 네덜란드 국기의 색깔(빨강, 하양, 파랑)에 비유해서이름이 붙여졌다. 이 문제의 목표는 배열에 세 가지 다른 값이 있을 때, 이를 특정 순서대로 배열하는 것이다. 보통 이 문제는 0, 1, 2로이루어진 배열을 다루며, 0은 왼쪽에, 1은 중간에, 2는 오른쪽에 배치하는 것을 목표로 한다.  2. 동작 방식mid가 2이면 mid와 high의 값을..

❒ Description삽입 정렬의 구현방법을 정리하자.     ❒ Insertion sort 1. 동작 방식삽입 정렬은 target 값과 그 이전 요소들을 비교하면서, `target 인 경우에 swap하는 방식이다.   2. 특징내부 정렬 : 추가적인 배열을 사용하지 않고 원래 배열 내에서 정렬이 이루어진다.안정 정렬 : 같은 값의 원소들 간의 순서가 보존된다.온라인 정렬 : 정렬 과정 중 새로운 데이터를 처리할 수 있다. 3. 장단점장점거의 정렬된 데이터에서 매우 효율적이다.적은 데이터에 적합하다.추가 메모리 사용이 없다.단점비효율적 : 대규모 데이터에서는 비효율적이다.데이터가 역순의로 정렬된 경우 성능이 저하된다. 4. 시간 복잡도BestO(n)AverageO(n²)WorstO(n²)     ❒ ..

❒ Description트리 순회란 그래프 순회의 한 형태로 트리 자료구조에서 각 노드를 정확히 한 번 방문하는 과정을 말한다.그래프 순회와 마찬가지로 트리 순회 또한 DFS 또는 BFS로 탐색하는데, 특히 Binary Tree에서 DFS는노드의 방문 순서에 따라 크게 3가지 방식으로 구분된다.  오늘은 이 3가지 방식에 대해서 학습해볼 것이다.     ❒ 전위 순회 (Pre-Order) : Root > Left  > Right전위 순회는 Root > Left > Right 순으로 노드를 방문하는 방법이다.더보기preorder(node) if (node == null) return visit(node) preorder(node.left) preorder(node.right)더보기pu..

❒ Description[LeetCode#110] Balanced Binary Tree 문제를 풀면서 접하게 된 개념을 정리하자.     ❒ Height-Balanced Binary Tree1. Height-Balanced Binary Tree란?height-balanced Binary Tree는 트리의 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이하인트리를 말한다. 즉, 트리의 각 노드에 대해 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 크게 나지 않도록 균형을맞춘 형태다. 이 균형 덕분에 탐색, 삽입, 삭제 등의 연산에서 시간 복잡도를 최소화할 수 있다.  2. 주요 특징 i ) 높이 차이 제한각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하이다. ii ) 탐색 ..

❒ Description알고리즘 문제를 풀면서 Dijkstra 알고리즘과 Floyd-Warshall 알고리즘을 학습했다.이제 이 두 알고리즘의 차이를 정리해보자.     ❒ 차이점다익스트라(Dijkstra) 알고리즘과 플로이드-워샬(Floyd-Warshall) 알고리즘은 모두 최단 경로를 찾는알고리즘이지만, 두 알고리즘 간에는 여러 차이가 있다.  1. 적용 대상 및 문제 유형다익스트라 알고리즘은 하나의 시작점에서 모든 정점으로의 최단 경로를 찾는데 사용된다.단일 출발점 최단 경로 문제에 적합하다.주로 가중치가 양수인 그래프에 사용된다.그래프가 희소(Sparse)할 때 효율적이다. (간선의 수가 적을 때) 반면에 플로이드-워샬 알고리즘은모든 정점 간의 최단 경로를 찾는데 사용된다.모든 정점엥서 다른 모든..

❒ Description프로그래머스 Lv3. 순위 문제를 풀면서 알게된 Floyd Warshall 알고리즘에 대해서 학습하자. 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr      ❒ Floyd Warshall 알고리즘Floyd warshall 알고리즘은 모든 노드간의 최단 경로 탐색이 필요한 경우에 사용한다.음의 가중치가 있어도 사용할 수 있으며, O(v³)의 시간 복잡도를 갖는 알고리즘이다.  Floyd warshall 알고리즘의 핵심 아이디어는 거쳐가는 정점을 기준으로 최단거리를 구하는 것이다. 거쳐가는 정점을 A로 하게 경로는 `C → A → B`,..

❒ Description743. Network Delay Time 문제를 풀면서 Dijkstra 알고리즘을 복습했다. 이 알고리즘은 한 정점에서 모든 정점까지의 최단거리를 구하는 알고리즘이다.  풀이방법은 총 3가지 였다.배열 내에서 선형탐색 + 배열 내에 중복 정점 허용하지 않음우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용하지 않음우선순위큐 내에서 최솟값 탐색 + 우선순위큐 내에 중복 정점 허용  ※ 참고나무위키(다익스트라 알고리즘)을 보면 잘 정리되어 있어서 별도로 정리하지 않음. 소스 코드 : 링크  관련 문제743. Network Delay Time787. Cheapest Flights Within K Stops778. Swim in Rising Water815. Bus Rou..

❒ DescriptionCourse Schedule 문제를 풀면서 위상 정렬을 사용하는 풀이 방법을 알게 됐다. [ 같이 참고하면 좋은 문제들 ]※ 2024.09.24 추가 : [LeetCode#310] Minimum Height Trees   ❒ DAG (Directed Acyclic Graph)위상 정렬에 대해 공부하기 전 DAG에 대해서 알아보자. 1. 정의유향 비순환 그래프 또는 방향 비순환 그래프는 컴퓨터 과학 분야의 용어로 하나로서, 방향 순환이 없는무한 유향 그래프이다. 이해하기 쉽게 표현하면, 모든 간선들은 방향을 가지고, 어떠한 노드에서 출발해도다시 그 노드로 돌아오는 순환이 존재하지 않는 그래프다. DAG의 특성은 다음과 같다. Directed (유향성)그래프의 각 간선이 방향을 가진다..

❒ Description[LeetCode#641] Design Circular Deque에서 Array와 Doubly-Linked list를 통해서 Circular-DQ를 구현해봤다. 하지만 Doubly-Linked list를 통한 구현은 원형 큐의 이점을 잘 살리지 못한다고 했다.여기서는 왜 이점을 살리지 못하는지 정리해본다.   ❒ 동작원리1. insertFrontFront 앞에 새로운 데이터를 삽입한다.Front가 현재 0번 째 index를 가리키고 있다면, Front는 마지막 index를 가리키도록 변경된다. 2. insertLastRear 뒤에 새로운 데이터를 삽입한다.Rear가 현재 마지막 index를 가리키고 있다면, Rear는 첫 번째 index를 가리키도록 변경된다.   ❒ Why?1. ..