알고리즘
[백준] 2014번 - 소수의 곱
☞ 이 문제에서 가장 중요하게 생각 할 점은 배열에 저장되어 있는 소수들을 어떤 방식으로 곱해야 최대한 순서대로 저장시킬 수 있도록 해줘야 합니다. 그냥 순서대로 처음에 한개씩 다음에 2,2 2,3 2,4 2,5와 같이 2개씩 계산을 해서 우선순위 큐에 저장시켜주면 나중에는 같은 수로 곱하여도 차이가 많이 나기 때문입니다.(예를 들어 2*2*2 와 7*7*7의 차이가 어마어마하다.) 따라서 여기서 우선순위 큐를 이용해 앞에 있는 수와 배열에 저장되어 있는 수들을 곱해 우선순위 큐에 저장시킨 후 다시 앞에 있는 수와 배열에 저장되어 있는 수들을 곱하는 방법을 반복한 후 N-1번째까지 반복 한 후 맨 앞에 있는 수가 정답이라는 것을 알 수 있었습니다. 여기서 2*2 를 하고 2*3 2*5를 가는 것보다 맨 ..
다익스트라 알고리즘(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..