목록algorithm/CodingTest (27)
on my way
투포인터와 슬라이딩 윈도우 알고리즘: 개념, 특징, 활용코딩 테스트에서 배열이나 리스트와 같은 연속된 데이터 구조를 다룰 때, 투포인터(Two Pointer)와 슬라이딩 윈도우(Sliding Window)는 매우 유용한 알고리즘 기법입니다.이번 포스팅에서는 이 두 가지 기법을 자세히 설명하고, 예제 문제를 통해 어떻게 활용할 수 있는지 알아보겠습니다. 투포인터 (Two Pointer)개념 설명투포인터는 두 개의 포인터를 사용하여 배열이나 리스트의 특정 구간을 탐색하는 기법입니다.이 기법은 주로 정렬된 배열에서 특정 조건을 만족하는 부분 배열이나 값을 찾는 데 사용됩니다.두 포인터는 일반적으로 시작점과 끝점을 나타내며, 조건에 따라 포인터를 이동시키면서 문제를 해결합니다. 특징효율성: O(n) 시간 복잡도..
이진 탐색 (Binary Search) 이해와 응용개요이진 탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정한 값을 효율적으로 찾는 알고리즘입니다.이진 탐색은 배열을 반으로 나누어 탐색 범위를 좁혀가는 방식으로 작동하며, 시간 복잡도가 O(log n)으로 매우 빠릅니다.이 포스팅에서는 이진 탐색의 원리, 구현 방법, 활용 예제 등을 자세히 설명하겠습니다. 이진 탐색의 원리이진 탐색은 다음과 같은 단계로 진행됩니다:초기화: 배열의 중간 요소를 선택합니다.비교: 중간 요소와 찾고자 하는 값을 비교합니다.만약 중간 요소가 찾고자 하는 값이라면 탐색을 종료합니다.찾고자 하는 값이 중간 요소보다 작다면 배열의 왼쪽 절반을 탐색합니다.찾고자 하는 값이 중간 요소보다 크다면 배열의 오른쪽 절반을 탐색..
너비 우선 탐색(BFS) 알고리즘: 이해와 응용개요BFS(Breadth-First Search)는 그래프나 트리 탐색 알고리즘 중 하나로, 넓이 우선 탐색이라고도 합니다.이 알고리즘은 루트 노드에서 시작하여 인접한 노드들을 먼저 탐색한 후, 그 다음 깊이의 노드들을 탐색하는 방식입니다.BFS는 주로 최단 경로 찾기나 레벨별 탐색에서 유용하게 사용됩니다.이번 포스팅에서는 BFS의 원리, 구현 방법, 활용 예제 등을 자세히 설명하겠습니다. BFS의 원리BFS는 다음과 같은 단계로 진행됩니다:초기화: 탐색을 시작할 노드를 큐(queue)에 추가하고 방문 표시를 합니다.탐색: 큐에서 노드를 꺼내어 해당 노드의 인접한 노드들을 모두 큐에 추가합니다. 이때, 방문하지 않은 노드만 큐에 추가하고 방문 표시를 합니다...
깊이 우선 탐색(DFS) 알고리즘: 이해와 응용DFS (Depth-First Search) 이해와 응용개요DFS(Depth-First Search)는 그래프 탐색 알고리즘 중 하나로, 깊이 우선 탐색이라고도 합니다.이 알고리즘은 한 노드를 시작점으로 깊이 들어가며 탐색하다가 더 이상 갈 수 없으면 돌아와 다른 경로를 탐색하는 방식입니다.DFS는 주로 경로 찾기, 사이클 탐지, 연결 요소 찾기 등의 문제에서 유용하게 사용됩니다.이번 포스팅에서는 DFS의 원리, 구현 방법, 활용 예제 등을 자세히 설명하겠습니다. DFS의 원리DFS는 다음과 같은 단계로 진행됩니다:초기화: 탐색을 시작할 노드를 스택(stack)에 추가하고 방문 표시를 합니다.탐색: 스택에서 노드를 꺼내어 해당 노드의 인접한 노드들을 모두 스..
그리디 알고리즘: 최적해를 찾아가는 방법그리디 알고리즘(Greedy Algorithm)은 현재 상황에서 가장 좋은 선택(예를들면 높은 수)만을 하는 알고리즘 기법입니다.이 알고리즘은 문제를 해결하는 과정에서 매 순간 최적이라고 생각되는 결정을 내리며, 이 과정을 통해 전체적인 최적해를 찾아갑니다.그리디 알고리즘은 단순하고 직관적이지만, 항상 최적해를 보장하지는 않습니다.그러나 많은 문제에서 그리디 알고리즘은 효율적이고 효과적인 해결책을 제공합니다. 그리디 알고리즘의 특징단계적 선택: 문제를 해결하는 과정에서 매 단계마다 가장 최적의 선택을 합니다.지역적 최적해: 각 단계에서의 선택이 전체 문제의 최적해를 보장하지는 않지만, 각 단계에서의 최적 선택을 통해 전체 문제의 해결을 시도합니다.비가역적 선택: 한..
스택, 큐, 우선순위 큐, 트리 - 자료구조 이해하기코딩 테스트를 준비할 때, 다양한 자료구조를 이해하는 것이 중요하다.이번에는 스택(Stack), 큐(Queue), 우선순위 큐(Priority Queue), 트리(Tree)에 대해 쉽게 설명하고, 예시 문제를 통해 더 자세히 알아볼게요.스택(Stack)개념 설명 스택은 물건을 쌓아 올리듯 데이터를 세로로 쌓는 자료구조입니다. 이 구조에서는 쌓인 물건을 아래에서부터 꺼낼 수 없고, 가장 위에 있는 물건부터 차례로 꺼낼 수 있어요.이를 'LIFO(Last In, First Out)'라고 하며, 마지막에 들어온 데이터가 가장 먼저 나가는 특성을 가지고 있습니다.특징Push: 데이터를 스택에 넣는 연산.Pop: 데이터를 스택에서 꺼내는 연산.Top/Peek: ..