Algorithm
세그먼트 트리 (구간 트리, Segment Tree)
☞ 세그먼트 트리란 이름 그대로 저장된 자료를 적절히 구간별로 전처리해 그들에 대한 질의들을 빠르게 대답할 수 있도록 해주는 트리입니다. 예를 들어 A={1,2,3,4,5}에서 [2,4] 구간의 최소치를 알고 싶다면 해당 배열을 순회하며 찾는 방법도 있지만, 해당 배열을 전처리해 세그먼트 트리를 생성해 더욱 더 빠르게 구현 할 수 있습니다. A배열을 세그먼트 트리로 바꾼 후 -> 아래처럼 구간별로 나눠 세그먼트 트리를 만들 수 있다. ☞ 이렇게 이론적으로만 설명했지만, 코드 구현에 많은 어려움이 있을 수 있습니다. 그래서 세그먼트 트리 문제의 한 유형인 구간 최소 쿼리(range minimum query,RMQ)를 구현해보겠습니다. ※ 여기서 중요한 점은 세그먼트 트리에 초기 크기를 설정해줘야하는데 가장..
[백준] 11657번 - 타임머신 (벨만-포드 알고리즘)
☞ 이 문제에서는 음수 간선이 존재하며, 출력 내용에서의 "만약 1번 도시에서 출발해 어떤 도시로 가는 과정에서 시간을 무한히 오래 전으로 되돌릴 수 있다면 첫째 줄에 -1을 출력한다." 를 보면 그래프에 음수 사이클이 존재하는 경우 -1을 출력하라는 말이라고 볼 수 있다. 따라서 음수간선이 존재하며 음수 사이클의 존재를 판단 할 수 있는 '벨만-포드 알고리즘'을 사용하면 된다. '벨만-포드 알고리즘'은 아래에 잘 설명이 되어있으니 참고해주세요. https://withseungryu.tistory.com/34 벨만-포드 알고리즘 (Bellman-Ford Algorithm) ☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로..
벨만-포드 알고리즘 (Bellman-Ford Algorithm)
☞ 그래프의 최단 경로를 알고 싶고, 그래프에 음수 간선이 있으며, 음수 사이클이 존재 할 때 다익스트라 알고리즘을 사용해 최단 경로를 구해도 될까? -> 정당성에 성립되지 않습니다. 따라서 음수 간선이 존재하고 음수 사이클이 존재한다는 것을 확인하고 싶을 때 Bellman-Ford Algorithm을 사용해야합니다. ☞ 벨만-포드 알고리즘이란 무엇일까? 벨만포드 알고리즘 원리는 시작점에서 각 정점까지 가는 최단 거리의 상한을 적당히 예측한 뒤 예측 값과 실제 최단 거리 사이의 오차를 반복적으로 줄여가는 방식입니다. 여기서 상한은 upper 배열에 저장하며 이 upper의 값은 알고리즘이 진행됨에 따라 점점 줄어들고 알고리즘이 종료되면 실제 최단 거리를 담게 되는 원리입니다. ☞ 벨만-포드 알고리즘 동작..
[백준] 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} ..