https://www.acmicpc.net/problem/20303 20303번: 할로윈의 양아치 첫째 줄에 정수 $N$, $M$, $K$가 주어진다. $N$은 거리에 있는 아이들의 수, $M$은 아이들의 친구 관계 수, $K$는 울음소리가 공명하기 위한 최소 아이의 수이다. ($1 \leq N \leq 30\ 000$, $0 \leq M \leq 100\ 000$, www.acmicpc.net 1. Logic - 친구관계를 bfs를 돌면서 친구관계를 만들어준다. - Knapsack 알고리즘을 활용하여 사탕을 뺏을 수 있는 가치합의 최대값을 구해준다. 2. Code #include using namespace std; int n, m, k; vector vec[30001]; bool vis[30001];..
백준
https://www.acmicpc.net/problem/1738 1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 주어 www.acmicpc.net 1. Logic 1. 최적경로 즉 시작부터 목적지까지 최단거리로 가는 경우가 있는지를 먼저 파악하기 위해 BFS통해 최단거리를 확인해놓는다. 2. 벨만포드를 돌면서 최단경로를 확인하고 v번을 돌면서 마지막 사이클에서 음의 사이클을 확인한다. 3. 벨만 포드 알고리즘을 돌면서 최단경로를 갱신할 때에만 주의 해야 할 사항 음의 사이클이 있다고 무조건 -1을 반환하는게 아니..
https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 1. Logic - 해당 문제에서 시간이 거꾸로 가는 경로인 웜홀이 존재한다고 하였다. 이건 음수 간선을 나타내는 말이기 때문에 그래프 최단거리 알고리즘 중에서 음수가중치가 있을 때 사용할 수 있는 방법인 벨만-포드 알고리즘을 사용해서 풀이할 수 있다. 원래 벨만 포드 알고리즘은 V(노드의 갯수)-1만큼 순회하며 모든 간선을 확인하며 최단거리를 구하는 방법이다. 이 문제에서는 음수싸이..
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..
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/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 1. Logic - 입력수가 10억을 넘기 때문에 입력만으로 시간복잡도가 터진다. 그래서 시간복잡도가 O(logN)인 자료구조인 priority_queue를 썼다. 그렇기 때문에 시간복잡도 log10억은 9이다. 작은 값부터 탐색해야 하기 때문에 priority queue에 greater인자를 넣어 오름차순으로 정리해주었다. 앞의 원소들 부터 차례대로 탐색하면서 1. 입력받은 수의 전체 합이..
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..
