Programming (4) 썸네일형 리스트형 [c++/알고리즘] BFS :: 너비우선탐색의 개념 0. BFS란? i. Breadth-First Search, 너비 우선 탐색을 말한다.모든 경로를 탐색하는 문제에서,각 경로를 깊게 방문하지 않고 넓게 방문할거라는 느낌만 우선 가져보자~ ii. 모든 경우의 수를 다 훑는 알고리즘이다. ( 정답을 찾을때까지 )모든 경우의 수를 다 탐색하는 알고리즘에는 DFS 와 BFS 가 있다. 깊이 우선 탐색(Depth-First Search)는 한 경로에 대한 탐색을 우선 완료한 다음 다른 경로를 탐색하지만, 너비 우선 탐색은 경로상 어느 정점(node)에서 다음에 방문할 수 있는 모든 경우의 노드를 전부 방문하고, 그 다음 단계로 넘어간다.(따라서 내가 이해한 바로는 몇번째 방문할 노드인지에 따라 각 노드에 Hierarchy(계층 수준)이 부여되기도 한다.같은 h.. [c++] 백준 1753번 오답노트 :: 다익스트라 구현 다익스트라(Dijkstra) 알고리즘이란?- 최단 경로를 구할 때 사용한다.- 한 정점에서 다른 모든 정점으로 가는 최단 경로의 비용을 저장한다.- 다이내믹프로그래밍이다. 왜냐하면 A에서 B로의 최단 경로는 A에서 다른 곳들로의 최단경로들로 구성되어 있기 때문이다.- 즉 전체의 문제가 부분의 문제를 포함하므로 다이내믹프로그래밍으로 풀 수 있다.- 한 경로의 최단거리를 구할 때, 이전까지 구했던 최단거리들을 사용한다. 다익스트라 알고리즘의 구현 방법1. 정점과 간선정보를 저장하는 2차원 배열이 필요하다.2. 시작 정점이 정해지면 그 정점으로부터 다른 정점까지의 거리를 벡터로 표현한다.3. 가장 비용이 작은 정점을 선택한다. 그 정점을 거쳐서 다른 정점으로 가는 비용이 원래 값보다 작다면 벡터의 값을 업데이.. STL container list 자료구조 :: 백준 알고리즘 1158 요세푸스 문제 오답노트 (2) 지난번 포스팅에 이어서 ...이번에는 STL container를 사용하여 문제를 해결해본다. STL의 list 자료구조는 Sequence Container이다. Sequence Container란 내가 데이터를 넣는 순서대로 Access가 가능한 자료구조이다.list 뿐만 아니라 array, vector, dequeue등은 sequence container이다. List STL Library#include List의 선언std::list list0 {1,2,3,4};std::list는템플릿화 되어 있으므로, 저장하고싶은 원소의 타입을 지정할 수 있다. List의 iteratorstd::list::iterator iter = list0.begin(); 위처럼 list의 iterator를 선언하고 .. 백준 1158 요세푸스 문제 시간초과 오답노트 (1) 백준 알고리즘 1158 요세푸스 문제 오답노트 문제 : 시간초과 문제 링크 :https://www.acmicpc.net/problem/1158 알고리즘 설계요세푸스 문제는 N개 수열을 K 개씩 건너 뛰어가며 삭제하는 동작을 구현해야한다. 나는 이 문제를 보자마자 Linked List로 구현을 하고 싶어졌다. 왜냐하면 Linked List의 Head와 Tail을 연결하면 Cyclic한 자료구조를 구현 가능하고 또한 K번째 노드마다 삭제가 쉽고 빠르기 때문이다. (Linked List는 자료의 중간부분의 삭제나 삽입 효율이 좋다.) 그러나... 첫번째 Try 는 시간초과에 직면한다...내가 시간초과에 직면했던 코드를 살펴보자...나는 STL Container와 Iterator 사용법을 공부하기 전이라..L.. 이전 1 다음
