본문 바로가기

전체 글121

[우선순위 큐] 최솟값 or 최댓값 찾기 알고리즘(feat. deque) 최솟값, 최댓값 찾기 문제에서 정렬을 사용할 수 없다면, 우선순위 큐를 생각하세요 들어가며시간복잡도를 측정하는 문제 중에서는 까다로운 문제들이 많습니다. 특히 정렬이 필요한 경우인데, 정렬은 기본적으로 NlogN의 시간복잡도를 가집니다. 특정 문제의 요구사항에서는 적어도 N의 시간복잡도를 요구하는 부분이 있습니다. 이럴 땐 우선순위 큐를 사용하면 logN의 시간복잡도를 가질 수 있습니다. 문제백준 11003 처음에는 문제 자체가 이해되지 않았습니다. 슬라이딩 윈도우 형태로 고정된 구간이 이동하면서 그 중 최소값을 찾는 문제더라구요. N의 최대 범위가 5,000,000이므로 정렬을 사용하게 되면 시간초과입니다.저는 문제를 두가지 파트로 나눴습니다. 첫 번째는 구간이 이동함에 따라 최소값 리스트를 갱신해주는.. 2025. 4. 13.

[기본] 투 포인터 들어가며투 포인터는 2개의 포인터로 알고리즘의 시간 복잡도를 최적화합니다. 알고리즘은 매우 간단합니다. 하지만 알고리즘에 익숙하지 않은 사람들은 투 포인터를 활용할 생각을 쉽게 하지 못합니다. 따라서 오늘은 투 포인터를 어떻게 사용하는지 알아봅시다. 투 포인터는 인접한 리스트에서 두 인덱스를 기록해가면서 조건 체크를 해 나갑니다. 여기서 중요한 것은 기록입니다. 포인터가 기록을 해나가기 때문에 전체 원소를 순회하면서 복잡도를 낭비하지 않아도 된다는 큰 장점이 있습니다. 투 포인터는 병합정렬(merge sort)의 counquer 영역의 기초가 되기도 합니다. 문제1백준 2018: 수들의 합 5(링크)분석주어진 제한시간은 2초인데 N의 최댓값은 10,000,000으로 매우 크게 잡혀있습니다. nlogn의 .. 2025. 3. 25.

[기본] 구간합 응용 들어가며구간합의 중요성을 더 알아보고자 구간합과 관련된 응용문제를 더 풀어보고자 합니다. 지난 구간합보다는 조금 더 어려운 문제를 풀어보려고 합니다. 다시 한 번 구간합을 구해놓는 것이 얼마나 시간복잡도를 낮춰주는 지 체크해보는 시간이 될 것 같습니다. 문제백준 11660: 구간합 구하기 5(링크) 풀이1#include #include using namespace std;int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int size, count; cin >> size >> count; vector> sumMetrix(size + 1); for (int i = 1; i num.. 2025. 3. 13.

[기본] 스택 자료구조 활용 스택을 활용해야하는 문제스택을 활용해야 하는 경우는 보통 짝을 짓는 문제입니다. 남녀가 반복돼서 나타나거나, 동물 등등 교차로 반복되는 상황에서 짝을 맞춰야하는 경우에 사용합니다. 그 중 대표적인 문제는 괄호입니다. 괄호는 반드시 여는 괄호와 닫는 괄호가 짝이 이루어져야겠죠. 그렇지 않으면, 문제가 발생합니다. json파일을 분석할 때도 괄호의 여닫음을 분석해야 합니다. 중첩으로 객체가 있을 수 있고 그 내부에 array까지 있다면, 함수 콜 스택 처럼 내부로 들어갔다가 나올때 닫는 괄호를 기준으로 빠져나오게 됩니다. 문제 풀기백준 9012: 괄호(링크) 풀이#include #include #include #include #include using namespace std;int main() { .. 2025. 3. 10.

[기본] 합배열과 구간 합 구하기 합배열과 구간합합배열은 특정 배열의 누적 합을 저장하는 배열로, 구간합을 빠르게 계산하기 위해 사용됩니다. 배열의 i번째까지의 누적 합을 저장하여, 특정 구간의 합을 O(1) 시간 복잡도로 구할 수 있습니다.합배열 계산배열 A가 주어졌을 때, 합배열 S는 다음과 같이 정의됩니다.S[i]=A[1]+A[2]+...+A[i]즉,S[0]=0 (기본값)S[i]=S[i−1]+A[i]를 만족합니다.예제배열 A=[2,4,5,7,9,12] 가 주어졌을 때, 합배열 S 는 다음과 같습니다.iA[i]S[i]00012224635114718592761239 구간합 계산구간합을 구하는 공식은 매우 쉽습니다. 구간 i에서 j까지의 구간합을 구하는 공식은 다음과 같습니다.S[j] - S[i -1]예: 구간 [2, 5]의 합은 S[5.. 2025. 3. 8.

[그래프 탐색] 깊이 우선 탐색(Depth First Search, DFS) 깊이 우선 탐색(Depth-First Search, DFS)깊이 우선 탐색(DFS)은 그래프 탐색 알고리즘 중 하나로, 한 정점에서 시작하여 가능한 깊이까지 탐색한 후, 더 이상 갈 곳이 없으면 되돌아오는 방식(백트래킹)으로 동작합니다.🔹 DFS 개념DFS는 스택(재귀 호출 or 명시적 스택)을 사용하여 그래프를 깊게 탐색하는 방법입니다.먼저 현재 노드를 방문하고,방문하지 않은 인접 노드가 있으면 해당 노드로 이동하여 탐색을 계속함.더 이상 방문할 노드가 없으면 이전 노드(부모 노드)로 돌아감(백트래킹).🔹 DFS 동작 방식DFS의 기본 동작 순서는 다음과 같습니다.시작 노드를 방문하고 방문 처리현재 노드에서 갈 수 있는 노드를 확인방문하지 않은 노드가 있으면 해당 노드로 이동방문한 노드라면 스킵더 .. 2025. 2. 12.

이전 1 2 3 4 ··· 21 다음

티스토리툴바