본문 바로가기

알고리즘5

[기본] 스택 자료구조 활용 스택을 활용해야하는 문제스택을 활용해야 하는 경우는 보통 짝을 짓는 문제입니다. 남녀가 반복돼서 나타나거나, 동물 등등 교차로 반복되는 상황에서 짝을 맞춰야하는 경우에 사용합니다. 그 중 대표적인 문제는 괄호입니다. 괄호는 반드시 여는 괄호와 닫는 괄호가 짝이 이루어져야겠죠. 그렇지 않으면, 문제가 발생합니다. 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.

주요 자료구조의 시간복잡도 들어가며프로그래밍 초창기에는 시간도 중요했지만, 공간도 매우 중요했습니다. 지금처럼 고사양 메모리와 하드디스크를 저렴한 가격에 살 수 없었기 때문이죠. 그당시에는 용량이 충분한 메모리도 없었습니다. 따라서 변수와 함수를 선언하거나 사용할 때도 불필요한 부분을 만들지 않았으며 프로그램 실행파일의 용량도 중요했죠. 컴퓨터가 발전하면서 지금은 공간에 대한 제약은 거의 없다고해도 무방합니다. 그러니 더욱 시간에 대한 중요도가 올라가기도 했죠. 시간복잡도는 빅오(Big-O)라는 표현방식을 대부분 사용합니다. 어떤 알고리즘이 실행되는데 가장 최악의 조건인 상태로 얼마나 걸리냐를 판단하는 지표입니다. 주로 사용하는 자료구조에 대한 시간복잡도를 알아보겠습니다.다음은 주요 자료구조의 연산별 시간복잡도입니다. 배열 (A.. 2025. 2. 7.

하노이의 탑 이해하기 겉으로 보기에는 하노이의 탑에서 재귀의 조건인 부분 분할의 경우가 없어보이지만, 자세히 들여다 보면 반드시 존재한다. 하노이의 탑은 기둥 3개는 고정이기 때문에 시작점(From), 옮길 지점(To), 나머지 지점(Mid)로 구성된다. 원반 3개 예를 들어보자.(원반을 1에서 3으로 옮기는 과정, N: 3, From: 1, Mid: 2, To: 3) 첫번째 빨간 영역은 원반 2개를 (1)에서 (2)로 옮기는 과정이다.(N: 2, From: 1, Mid: 3, To: 2) 이 후, 1->3은 가장 큰 원반을 목적(To)지점으로 옮기는 과정이다. 두번째 빨간 영역은 원반 2개를 (2)에서 (3)로 옮기는 과정이다.(N: 2, From: 2, Mid: 1, To: 3) 정리하면, hanoi(3)의 결과는 han.. 2022. 2. 18.

이전 1 다음

티스토리툴바