하드웨어 뿌수기

백준 알고리즘 9935번 문제는 쉽게 접근하면 너무나도 쉽고, 어렵게 접근하면 너무나도 어렵다. 저번주에는 하루종일 풀었는데도 못풀었고,오늘 다시 시도했을 땐 3분 만에 풀었다. 확실한 건, 스택을 활용하면 아주 쉽게 풀린다는 것이다. 문제 링크 9935번: 문자열 폭발https://www.acmicpc.net/problem/9935 문제 분류 문자열(string) 클래스스택자료구조 문제 해석input은 두 줄이다.첫번째 줄 제시 문자열에서 두번째 줄 폭발 문자열을 모두 찾아 제거하면 된다.폭발문자열이 제거된 이후에 남아있는 폭발문자열도 거듭 제거해야한다.처음 시도에는 폭발문자열이 모두 사라질 때 까지 루프를 돌렸는데, 이렇게 접근하면 당연히 시간초과가 날 수 밖에 없었다.두 번째 시도에서는 제시 문자..

0. BFS란? i. Breadth-First Search, 너비 우선 탐색을 말한다.모든 경로를 탐색하는 문제에서,각 경로를 깊게 방문하지 않고 넓게 방문할거라는 느낌만 우선 가져보자~ ii. 모든 경우의 수를 다 훑는 알고리즘이다. ( 정답을 찾을때까지 )모든 경우의 수를 다 탐색하는 알고리즘에는 DFS 와 BFS 가 있다. 깊이 우선 탐색(Depth-First Search)는 한 경로에 대한 탐색을 우선 완료한 다음 다른 경로를 탐색하지만, 너비 우선 탐색은 경로상 어느 정점(node)에서 다음에 방문할 수 있는 모든 경우의 노드를 전부 방문하고, 그 다음 단계로 넘어간다.(따라서 내가 이해한 바로는 몇번째 방문할 노드인지에 따라 각 노드에 Hierarchy(계층 수준)이 부여되기도 한다.같은 h..

다익스트라(Dijkstra) 알고리즘이란?- 최단 경로를 구할 때 사용한다.- 한 정점에서 다른 모든 정점으로 가는 최단 경로의 비용을 저장한다.- 다이내믹프로그래밍이다. 왜냐하면 A에서 B로의 최단 경로는 A에서 다른 곳들로의 최단경로들로 구성되어 있기 때문이다.- 즉 전체의 문제가 부분의 문제를 포함하므로 다이내믹프로그래밍으로 풀 수 있다.- 한 경로의 최단거리를 구할 때, 이전까지 구했던 최단거리들을 사용한다. 다익스트라 알고리즘의 구현 방법1. 정점과 간선정보를 저장하는 2차원 배열이 필요하다.2. 시작 정점이 정해지면 그 정점으로부터 다른 정점까지의 거리를 벡터로 표현한다.3. 가장 비용이 작은 정점을 선택한다. 그 정점을 거쳐서 다른 정점으로 가는 비용이 원래 값보다 작다면 벡터의 값을 업데이..