알고리즘

1. 개념 1. 퀵 셀렉트퀵 셀렉트는 주어진 배열에서 k째로 작은 원소를 찾는데 활용되는 알고리즘입니다. 퀵 셀렉트 알고리즘은 퀵 정렬과 비슷한 분할-정복 방식을 활용하지만, 주어진 배열을 모두 정렬하는 대신 특정 원소를 찾는 작업에 초점을 맞춥니다. 퀵 셀렉트 알고리즘은 평균적으로 O(n)의 시간 복잡도를 가지며, 최악의 경우 O(n²)의 시간 복잡도를 갖습니다. 최악의 시간 복잡도가 O(n²)인 이유는 퀵 정렬과 같습니다. 2. 동작 방식주어진 배열에서 피벗을 선택합니다.피벗 원소를 기준으로 배열을 두 개의 부분 배열로 나누고, 피벗 원소보다 작은 원소는 왼쪽 부분 배열로 이동시키고, 반대로 피벗 원소보다 큰 원소는 오른쪽 부분 배열로 이동시킵니다.k(찾고자 하는 k번째 작은 원소의 위치)가 피벗의 ..

#1. 개념 1. LCA(Least Common Ancestor) LCA 알고리즘은 트리 자료구조에서 두 노드의 가장 가까운 공통 조상 노드를 찾는 알고리즘입니다. 이때, 가장 가까운 노드란, 주어진 두 노드의 경로 상에서 가장 깊은 곳에 위치한 공통 조상 노드를 의미합니다. LCA 알고리즘을 효율적으로 구현하는 방법으로 Binary Lifting 기법이 있습니다. 2. Binary Lifting 기법  Binary Lifting 기법은 주어진 트리 자료구조에서 두 노드의 LCA를 찾는 방법 중 하나입니다. 특히, Binary Lifting 기법은 깊이가 깊은 트리에서 두 노드의 LCA를 찾는데 효율적입니다. BL의 핵심 개념은 각 노드에 대해 미리 점프할 수 있는 조상 정보를 계산해 ..

#1. 문제 #2. 풀이 1. 투 포인터 알고리즘 [알고리즘]#7_투 포인터 #1. 개념 1. 투 포인터 [정의] : '투 포인터' 알고리즘은 배열 또는 리스트에서 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다. [특징] : '투 포인터' 알고리즘은 일 webddevys.tistory.com [정의] : '투 포인터' 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다. [특징] : '투 포인터' 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다. [동작 방식] 배열의 시작 지점을 가리키는 포인터, 그리고 끝 지점을 가리키는 포인터, 두 개의 포인터를 초기화합니다. 두 포인터가 움직이며 주어진 조건을 만족하는지 검사합니다. 조건을 ..

#1. 개념 1. 투 포인터 [정의] : '투 포인터' 알고리즘은 두 개의 포인터를 활용해 원하는 조건을 만족하는 부분을 찾는 알고리즘입니다. [특징] : '투 포인터' 알고리즘은 일반적으로 정렬된 배열 혹은 리스트에서 활용합니다. [동작 방식] 배열의 시작 지점을 가리키는 포인터, 그리고 끝 지점을 가리키는 포인터, 두 개의 포인터를 초기화합니다. 두 포인터가 움직이며 주어진 조건을 만족하는지 검사합니다. 조건을 만족할 경우, 원하는 동작을 수행하고, 조건을 만족하지 못할 경우, 포인터를 이동시킵니다. 원하는 결과 값을 얻을 때까지, 2~3번 동작을 반복합니다. #2. 예제 1. 연속된 부분 수열의 합 [Programmers]#Level2_연속된 부분 수열의 합, 투 포인터 [Programmers 알고..

[BOJ알고리즘, C++]#2263_트리의 순회 BOJ 알고리즘 문제 풀이, 2263번 문제 "트리의 순회" 트리의 순회 방법에 대해 공부하고, 후위순회와 중위순회를 통해 전위순회를 구하는 방법 Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 트리 [자료구조]#5_트리 [자료구조]#5_트리 트리 자료구조에 대해 알아보겠습니다. Overview 개념 이진트리 순회 이진 탐색 트리 균형 이진트리 AVL 트리 레드-블랙 트리 Map, Set 힙 #0. 개념 1. 트리? [정의] : 트리는 1:n 관계의 webddevys.tistory.com [정의] : 트리는 1:n 관계의 계층 구조를 갖는 비 선형 자료구조입니다. 트리는 노드와 노드 간 연결관계를 표현하는 간선으로 이루어져 있습니다. [특징]..

[BOJ알고리즘, C++]#17299_오등 큰 수 BOJ 알고리즘 문제 풀이, 17299번 문제 "오등 큰 수" C++의 STL이 제공하는 stack과 unordered_map 컨테이너를 활용하는 문제 Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 스택 [자료 구조]#0_선형 자료구조 [자료 구조] #0_선형 자료구조 선형 자료구조에 대해 알아보겠습니다. Overview 개념 스택 큐 원형 큐 덱 배열 벡터 리스트 이중 연결 리스트 #0. 개념 1. 선형 자료구조? 선형 자료구조는 데이터를 일 webddevys.tistory.com [Basic C++] #64_stack [Basic C++] #64_stack C++에서 제공하는 stack 클래스에 대해 알아보겠습니다. Overview 개..

[BOJ알고리즘, C++]#9935_문자열 폭발 BOJ 알고리즘 문제 풀이, 9935번 문제 "문자열 폭발" C++의 STL이 제공하는 string 클래스 활용하여 푸는 문제 Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 문자열 [Basic C++] #63_string [Basic C++] #63_string C++에서 제공하는 string 클래스에 대해 알아보겠습니다. Overview 정의 선언 멤버 함수 그 외 특징 예제 #0. 정의 1. string 클래스 C++에서 제공하는 string 클래스는 문자열을 다루기 위 webddevys.tistory.com Details C++ STL은 문자열을 저장하고 다양한 조작 함수를 제공하는 string 클래스를 제공합니다. 2. 주어진 문자열..

[BOJ알고리즘, C++]#24511_queuestack BOJ 알고리즘 문제 풀이, 24511번 문제 queuestack 덱을 활용하여 푸는 문제 Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 덱 [자료 구조]#0_선형 자료구조 [자료 구조] #0_선형 자료구조 선형 자료구조에 대해 알아보겠습니다. Overview 개념 스택 큐 원형 큐 덱 배열 벡터 리스트 이중 연결 리스트 #0. 개념 1. 선형 자료구조? 선형 자료구조는 데이터를 일 webddevys.tistory.com [Basic C++] #68_deque [Basic C++] #68_deque C++의 STL에서 제공하는 deque 컨테이너에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 1. 덱..

[BOJ알고리즘, C++]#12789_도키도키 간식 드리미 BOJ 알고리즘 문제 풀이, 12789번 문제 도키 도키 간식 드리미 스택과 큐를 활용하여 푸는 문제 Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 스택 [자료 구조]#0_선형 자료구조 [자료 구조] #0_선형 자료구조 선형 자료구조에 대해 알아보겠습니다. Overview 개념 스택 큐 원형 큐 덱 배열 벡터 리스트 이중 연결 리스트 #0. 개념 1. 선형 자료구조? 선형 자료구조는 데이터를 일 webddevys.tistory.com [Basic C++] #64_stack [Basic C++] #64_stack C++에서 제공하는 stack 클래스에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 1...

[BOJ알고리즘, C++]#28279_덱2 BOJ 알고리즘 문제 풀이, 28278번 덱2 문제 C++의 STL이 제공하는 deque컨테이너를 활용하는 문제 Overview 문제 풀이 코드 #1. 문제 #2. 풀이 1. 덱 [자료 구조]#0_선형 자료구조 [자료 구조] #0_선형 자료구조 선형 자료구조에 대해 알아보겠습니다. Overview 개념 스택 큐 원형 큐 덱 배열 벡터 리스트 이중 연결 리스트 #0. 개념 1. 선형 자료구조? 선형 자료구조는 데이터를 일 webddevys.tistory.com [Basic C++] #68_deque [Basic C++] #68_deque C++의 STL에서 제공하는 deque 컨테이너에 대해 알아보겠습니다. Overview 개념 선언 멤버 함수 예제 #0. 개념 ..