https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 1. Logic - 모든 점에서 모든 점까지의 최단 거리를 각각 구해야한다. >> 플로이드 와샬 알고리즘 플로이드 와샬 알고리즘은 3중 for문을 돌아야하기 때문에 노드의 갯수가 적을 때 사용할 수 있다. 2. Code #include using namespace std; int n, m, r; const int INF = 0x3f3f3f3f; vector dist(101, vector (101, IN..
알고리즘
1. 다익스트라(Dijkstra) 란? 다익스트라 알고리즘이란 하나의 그래프에서의 최단 경로 탐색 알고리즘이며, 우리가 흔히 알고있는 동적계획법 즉 다이나믹 프로그래밍을 활용한 최단경로 탐색 알고리즘이다. 한 정점에서 모든 정점까지의 최단거리를 구할 때 사용하며, 주어진 그래프중에서 음의 가중치가 없는 그래프에서 사용 가능하다. 음의 가중치가 있을 경우 벨만-포드 알고리즘을 사용하여 해결할 수 있다. 2. Default Logic 다익스트라 알고리즘 동작 반복 과정 1. 방문하지 않은 정점 중 가장 가중치 값이 작은 정점을 방문한다. 2. 현재 위치한 정점을 거쳐 다른 노드로 넘어가는 가중치 값을 계산하여 최소 비용을 갱신한다. 3. 위의 과정을 목표한 노드에 도달 할 때까지 반복한다. 이해를 돕기 위해..
https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 1. Logic - 모든 버스 비용이 0보다 크거나 같다고 나왔기 때문에 다익스트라 알고리즘을 사용하여 풀이한다는 것을 유추할 수 있다. 일반 다익스트라 알고리즘과 동일하게 풀이하지만 해당 문제는 지나온 경로까지 표현해줘야 하기 때문에 경로를 추적하는 trace 배열을 한개 더 선언해주었다. trace배열로 경로를 찾는 과정 문제의 Testcase에서 내가 도출한 ..
https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 1. Logic - 문제의 조건에 따라 왼쪽에서도 값을 넣고 오른쪽에서도 값을 넣다 뺏다하기 쉬운 자료구조는 deque가 적절하다. 연산을 최소로 하기 위해서는 구해야하는 수를 기준으로 오른쪽과 왼쪽 중 어디가 더 값이 적게 남았는지 체크를 해야한다. 덱에서는 큐와 다르게 인덱스로 값을 알 수 있기때문에 덱을 사용해서 풀이하며 된다. 2. Code #include using namespace ..
https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 1. Logic 비슷한 문제인 벽 부수고 이동하기 1(boj - 2206) 과 비슷하게 풀어보았다. 2206번 문제에서와 마찬가지로 vis배열 설정이 중요하다. 이번 문제에서는 부실 수 있는 블록의 갯수를 유동적으로 입력받기 때문에 BFS에서 처음 시작구간을 queue에 넣을 때 부실수 있는 block의 갯수를 입력받은 k만큼 넣어준 상태로 0이 될때까지 부셔나..
https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. Logic - 방문처리를 하는 vis배열을 2차원으로 좌표로만 구성하는 것이 아닌 3차원으로 형성하여 벽을 뚫을 수 있는지 아니면 이전에 뚫은 적이 있는지 확인한다. 부분문제를 나눠보자면 1. 벽을 뚫을 기회가 있을 때 벽을 만난경우 2. 갈 수 있는 길이면서 방문한적 없는 경우 이렇게 2가지로 나눌 수 있다. 2. Code #include using namespac..
https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 1. Logic - 줄세우기 문제는 최장 증가 부분 수열(LIS) 를 사용해서 풀이한다. LIS로 풀이하는 이유는 이미 순서대로 서있는 가장 많은 수를 제외한 나머지의 위치를 변경해주면 되기 때문이다. 2. Code #include using namespace std; int n; vector vec; int dp[1000001]; int main() { ios_base::sync_with_stdio(f..
https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 1. Logic 음수와 양수가 섞여있기 때문에 먼저 오름차순으로 정렬을 한다. 두개의 포인터중 하나는 음수에서부터 하나은 양수에서 부터 서로 끝과 끝에서 가운데로 모이는 방식으로 투포인터를 적용한다. 2. Code #include using namespace std; const long long INF = 1e12; vector ans(2); vector vec;..
https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 1. Logic - 인덱스를 가르키는 두개의 포인터 변수(start, end)를 선언 한 뒤 원하는 수보다 sum이 작으면 다음 배열로 end를 옮기고 vec[end] 더해주고 크면 vec[start]를 빼주고 start 포인터를 하나 더해준다. 해당 문제는 투포인터를 설명하면서 똑같이 풀이해놨으니 투포인터를 잘 모른다면 다음 글을 참고하면 좋을 것 같다!..
1. Two pointers 란? 리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 치리하는 알고리즘 보통 알고리즘에서 엄청나게 많은 입력들 중에서 원하는 값을 찾거나 반복문을 사용했을때 시간복잡도가 터지는 경우에 사용. 시간 복잡도 : O(N) || 매 과정에서 인덱스를 옮기는데 무조건 1씩 증가하고 항상 start m (현재 부분합이 우리가 원하는 부분합보다 클 때) - sum -= vec[start] (start인덱스의 값) - start 증가 글로는 이렇게 표현할 수 있지만 직접 그림으로 보자 Testcase 10 4 5 1 3 5 10 7 4 9 2 2 end == 2가 됐을 때 구간합과 원하는 Value가 일치하게 된다. 그리고 이후에 원하는 Value 값이 나왔기때문에 end..
