전체 글
다익스트라 알고리즘(Dijkstra Algorithm)
☞ 최단 경로를 구하기 위해선 어떤 방법을 써야할까? 우리는 BFS(너비우선탐색)을 이용해서 어떤 한 점까지 최소 거리를 알 수 있었고, 또한 경로를 구할 수 있었다. 하지만 너비우선탐색을 이용해 구할 때는 가중치가 없을 때라는 조건이 있었다....... 가중치가 있고, 방향성 그래프일때 어떤 방식을 이용해 최단 경로, 최소 거리를 구할 수 있을까?... 여기서 다익스트라 알고리즘이 나온다. 다익스트라 알고리즘이란 그래프 간선에 가중치가 있을 때 최단 경로를 구할 수 있는 알고리즘이며, 너비 우선탐색을 조금 변형해서 만든 알고리즘이라 할 수 있다. BFS는 큐를 사용해 최단 경로를 구하는 반면, 다익스트라 알고리즘은 우선순위큐를 사용해 최단 경로를 구할 수 있다. 다익스트라의 원리를 살펴보면,,,,, 먼..
[백준] 6593번 - 상범 빌딩
이번 상범 빌딩 문제는 행렬에서 너비우선탐색(BFS)을 이용해 시작점에서 각 위치의 거리만 구할 수 있으면 쉽게 풀 수 있다. 다만, 3차원 행렬을 사용해야하기 때문에 중간 중간 헷갈렸다. queue를 만들때 x,y,z를 다 저장하고 싶은데 지금까지 2개만 묶어서 저장했던 pair 방식 뿐이여서 인터넷에 3개를 묶는 방법을 찾아보며 시간이 소비했지만, 다행히 pair를 한 번 더 사용 할 수 있는 방법을 생각 할 수 있었다. #include #include #include #include #include using namespace std; int L, R, C; vector adj; vector dist; int dir[6][3] = { {1,0,0},{-1,0,0} ,{0,1,0} ,{0,-1,0} ..
[백준] 5014번 - 스타트링크
☞ 이번 문제는 풀면서 정말 많은 방법들을 갖고 접근해보았다. 처음에는 재귀를 이용해 풀려고 했는데, 재귀를 끝내기 위한 조건을 찾는 와중에 어떻게 하면 Up and Down을 계속 지속하며 뺑뺑 도는 부분은 나올 수 있을지에 대한 부분에서 막혔었다. 그래서 다른 방법을 찾아 보았고, 대부분 어떤 점에서 다른 점까지의 거리를 구하는 문제에 사용되는 너비우선탐색(BFS)법을 사용해보았다. ● BFS로 풀기 위해 해당 건물을 인접리스트의 형태로 표현 해보았다. int tmp[2] = { U, -(D) }; for (int i = 1; i > F >> S >> G >> U >> D; adj = vector(F+1); int tmp[2] = { U, -(D) }; for (int i = 1; i
[백준] 2178번 - 미로 탐색
이 문제는 위의 그림과 같이 입구(0,0)에서 출구(N-1,M-1) 까지의 거리를 찾는 문제이다. 거리를 찾는 문제이기 때문에 너비우선탐색을 이용해서 푸는 방법을 쉽게 생각 할 수 있었다. matrix를 이용해서 문제를 풀면 간다하며 마지막으로 저장되어진 dist 행렬에서 N-1,M-1번째 수만 결과를 출력하면 간단하게 풀 수 있다. 여기서 더욱 더 시간을 줄이기 위해 방향을 아래와 같이 행렬에 저장하였다. int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} }; #include #include #include #include #include using namespace std; int N, M; int dir[4][2] = { {-1,0},{0,-1},{0,1},{1,0} }..
[백준] 11266번 - 단절점 (Articulation Point)
이 문제의 유형은 깊이 유형 탐색을 통해 절단점을 찾는 것이다. 절단점이란? - 무향그래프에서 어떠한 점의 인접한 간선들을 모두 지웠을 때 -> 해당 Component가 2개로 나뉠때의 어떤한 점이 절단점 ● 어떠한 점이 절단점이 될 수 있을 조건 - 2가지 1) 기준점이 u일때 자손 v들이 역방향 간선을 통해 u의 선조들로 올라갈 수 있을 때 if (!root && subtree >= discovered[here]) { isCutVertex[here] = true; } subtree = isCutVertexDfs(there, false) 의 의미는 현재 점의 역행 간선이 존재 할 때 자신의 선조 어느 곳까지 올라 갈 수 있는지 보여준다. 따라서 subtree는 discovered를 저장하기 때문에 su..
[Research Paper] The best game in the world
주제 : How League of Legends became a best game in the world Research paper란 연구 논문으로서 한 가지 주제를 정하고, 그 주제에 대해 인터넷에서 자료들을 찾아보며 연구를 한 후 그 연구를 한 내용을 글로 적는 방법의 paper이다. 주제를 정할 때 내가 가장 좋아하는 League of Legends로 정하였다. 어떻게 리그오브레전드가 지금까지 인기를 유지 할 수 있었고, 미래에는 어떻게 인기를 유지할지에 대해 많은 자료들을 찾아보며 연구 논문을 써보았습니다. 많은 자료들을 인용하여 글이 많이 혼란스러울 수도 있으니 양해 부탁드리겠습니다.