스택11 [자료 구조] 선형(Linear) 자료 구조 (2) 스택(Stack), 큐(Queue) 포스트를 읽으실 때 참고하실 점 해당 카테고리의 포스트들은 C/C++ 언어를 기준으로 작성되어 다른 언어에는 적용되지 않는 내용이 일부 포함될 수 있습니다. 또한, 글의 배치나 띄어쓰기는 PC 버전 전체 화면 크기를 기준으로 작성됩니다. 틀린 부분이 있는 경우, 댓글이나 이메일로 연락주시면 내용을 정정하도록 하겠습니다. 지난 포스트에서 배열, 연결 리스트에 대한 키워드를 정리(정리한 거 맞나?...)해봤는데 이번 포스트에서는 나머지 선형 자료 구조인 스택(stack)과 큐(queue), 그리고 자료 구조를 공부할 때 지속적으로 접하게 되는 개념인 추상 자료형(abstract data type, ADT)의 개념에 대해 정리해보려고 한다. 스택(Stack) 스택은 기본적으로 나중에 들어온 자료를 먼저 내보내.. 2023. 5. 9. [Baekjoon] 1260번: DFS와 BFS https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어지는 간선 정보를 바탕으로 깊이 우선 탐색(depth-first search, DFS)과 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 구현하는 것을 요구하는 문제이므로, 두 알고리즘의 특징에 유의하여 구현하고자 하였다. 깊이 우선 탐색 알고리즘은 스택(stack) 자료 구조를 활용하여 구현(또는 .. 2023. 5. 8. [Baekjoon] 2606번: 바이러스 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 문제 해결 과정 착안 문제를 보자마자 그래프 자료구조를 이용해 시작 정점으로부터 연결되어 있는 모든 정점을 순회하는 알고리즘인 깊이 우선 탐색 알고리즘(depth-first search, DFS), 또는 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 이용해야할 것으로 판단되었다. 마침 지난 포스트에서 깊이 우선 탐색 알고리즘을 구현했었던 것을 활용(...)하여, 해당 코드를.. 2023. 5. 7. [Baekjoon] 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 https://www.acmicpc.net/problem/24479 24479번: 알고리즘 수업 - 깊이 우선 탐색 1 첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N)이 주어진다. 다음 M개 줄에 간선 정보 u v가 주어지며 정점 u와 정점 v의 가중치 1인 양 www.acmicpc.net 문제 해결 과정 착안 간선(edge)의 가중치가 모두 일정한 무향(undirected) 그래프(graph) 자료 구조에서의 깊이 우선 탐색 알고리즘을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 깊이 우선 탐색(depth-first search, DFS) 알고리즘을 구현하였다. 이때, 한 정점에 대한 간선의.. 2023. 5. 7. [Baekjoon] 9012번: 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 이 문제를 보자마자 스택(stack) 자료 구조가 떠올랐다면, 당신은 프로그래밍 에이스 ! (언제나 그렇듯 헛소리에 대해서는 반박 시 당신의 말이 항상 옳습니다) 문제 해결 과정 착안 문제를 보자마자 프로그래밍 에이스가 되기 위해서 스택이라는 자료구조를 떠올렸는데, 조금 더 고찰해본 결과로는 굳이 스택 자료구조 자체를 이용하지 않더라도 스택 자료구조가 구현되는 원리만.. 2023. 5. 6. 이전 1 2 다음
