본문 바로가기

스택5

[스택, 큐] 백트래킹(이전 상태 기억)은 스택을 활용하세요 이전 상태를 기억해야 하는 구조(백트래킹)에는 스택을 활용하세요. 들어가며스택과 큐에 대한 설명은 굳이 하지 않겠습니다. 다만 어떤 알고리즘에 스택과 큐를 사용해야 하는지 집중합시다. 스택은 기본적으로 후입선출 구조이기 때문에 DFS(깊이 우선 탐색), 재귀 등에 사용합니다. 모든 것을 관통하는 개념은 이전 상태 복구라고 생각합니다. 스택 자체가 데이터를 쌓아 올리다가 뺄 때는 가장 최신에 쌓인 데이터만 빼기 때문에 바로 이전 상태를 되찾을 수 있습니다. 이런 특성 덕분에 재귀, DFS, 괄호 검사, Undo 등 어떤 방향으로 갔다가 다시 되돌아 올 수 있는 회기 능력이 있습니다. 따라서, 스택은 이전 상태를 기억해 나가면서 필요할 때 빠르게 pop하여 비교하는데 최적화된 자료구조입니다.큐의 경우에는 .. 2025. 5. 11.

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

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

선형 자료구조(Linear Data Structure) 선형 자료구조(Linear Data Structure) 선형 자료구조는 데이터 요소들이 일렬로 배치되어 있는 자료구조를 의미합니다. 이러한 자료구조에서 데이터 요소는 순서를 가지며, 각각의 요소는 바로 이전 요소와 바로 다음 요소와 관련이 있습니다. 선형 자료구조는 데이터를 순차적으로 접근하고 조작하는데 유용하며, 간단한 구조로서 다양한 알고리즘과 응용 분야에서 활용됩니다. 여러 가지 선형 자료구조의 예시와 특징을 살펴보겠습니다 1. 배열 (Array) - 가장 기본적인 선형 자료구조로, 동일한 데이터 타입의 요소들을 순차적으로 저장합니다. - 인덱스를 사용하여 각 요소에 접근하고, 특정 위치에 요소를 삽입, 삭제할 수 있습니다. - 데이터 검색과 접근이 빠르지만, 중간에 요소를 삽입하거나 삭제할 경우 .. 2023. 8. 11.

[C/C++] 10. 포인터(feat. 스마트 포인터) ✅ 포인터 C++의 장점은 메모리를 직접적으로 제어할 수 있다는 것이다. 많은 개발자에게는 단점으로 느껴질 수 있다. 눈으로 훤히 확인해 볼 수 없는 메모리를 잘못 관리하면 프로그램이 죽어버리기 때문이다. 메모리를 직접 제어하는 것이 좋을 수도 있고 아닐 수도 있지만, 확실한 건 C/C++은 컴퓨터의 메인메모리가 어떻게 돌아가는지 알기에는 적합하다는 것이다. 포인터는 주소를 담고 있는 변수이다. 64비트 체제에서 integer 타입의 포인터 변수는 몇인가를 묻는 질문에 많은 분들이 4byte라고 대답한다. 포인터변수는 주소를 담고 있는 포인터변수는 컴퓨터의 워드(word)와 같다. 8비트 체제에서는 1 워드가 8비트=1바이트이다. 따라서 64비트 체제에서는 타입이 무엇이건 간에 포인터 변수의 크기는 64.. 2023. 4. 26.

이전 1 다음

티스토리툴바