분류 전체보기166 [자료 구조] 선형(Linear) 자료 구조 (1) 배열(Array), 연결 리스트(Linked List) 포스트를 읽으실 때 참고하실 점 해당 카테고리의 포스트들은 C/C++ 언어를 기준으로 작성되어 다른 언어에는 적용되지 않는 내용이 일부 포함될 수 있습니다. 또한, 글의 배치나 띄어쓰기는 PC 버전 전체 화면 크기를 기준으로 작성됩니다. 틀린 부분이 있는 경우, 댓글이나 이메일로 연락주시면 내용을 정정하도록 하겠습니다. 자료 구조와 알고리즘에 대한 이해는 프로그래머 꿈나무에게 있어서 아주 기초적으로 필요한 덕목이지만 본격적으로 파고 들려면 굉장히 어려운 분야이다. 우리 같은 초보 프로그래머 꿈나무들이 자료 구조를 공부해야하는 목적은 '남들이 봤을 때 휘황찬란하고 복잡한 자료 구조를 써야 멋지고 고수 같아서' 가 절대 아니다. 주어진 상황에 따라 어떤 자료 구조를 사용하는 것이 적합할지 스스로 판단하는 능.. 2023. 5. 8. [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] 24444번: 알고리즘 수업 - 너비 우선 탐색 1 https://www.acmicpc.net/problem/24444 24444번: 알고리즘 수업 - 너비 우선 탐색 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) 자료 구조에서의 너비 우선 탐색 알고리즘(breadth-first search, BFS)을 구현하는 문제이므로, 간단한 그래프 클래스와 문제에서 요구하는 너비 우선 탐색 알고리즘을 구현하였다. 이번에도 한 정점에 대한.. 2023. 5. 7. [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] 2798번: 블랙잭 https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제 해결 과정 착안 문제에서 주어진 \(M\)을 넘지 않으면서 \(M\)에 최대한 가까운 카드 3 장의 합을 구하기 위해서 사용할 수 있는 알고리즘이 마땅히 없다고 판단되어(일단 내가 알고 있는 바로는...), 단순하게 카드 3 장을 뽑는 모든 경우의 수에 대하여 카드 3 장의 합을 계산을 하는 알고리즘을 생각할 수 밖에 없었다. 하지만, 그렇다면 시간 복잡도(t.. 2023. 5. 7. 이전 1 ··· 22 23 24 25 26 27 28 다음
