코딩하기 좋은날

https://www.acmicpc.net/problem/4195 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 유니온 파인드 구조를 사용해서 해결을 하여야 하는 문제입니다. 다만 조금 까다로운게 string을 처리해야 하는 문제입니다. 따라서 저는 map을 이용하였고 map parent; 을 선언하여 key값은 사람의 이름을 저장하였고 value값은 pair로 저장하였는데 pair의 first값은 key값의 부모의 이름을 저장하였고 pair의 second값은 key값이 속해있는 그래프의 친구 명수를 저장하였습니다. 저는 이문제를 아예 다 string으로 처리해서 코드가 좀 지저분하게 작성 되었습니다. 다른분들을 보니 union-find 연산시에는 각 들어오는 친구에게 번호를 부여하여 ..

https://www.acmicpc.net/problem/4485 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이문제는 이전글인 1261번 알고스팟과 유사한 문제입니다.(거의 동일합니다) 시작점에서 N-1,N-1까지 가면서 잃는 금액이 가장 최소가 될때 금액을 구하는 문제입니다. 따라서 다익스트라 알고리즘을 통해 최단경로를 구해야 하고 그래프가 N*N행렬 형태로 주어지고 각 노드에서는 상하좌우로 이동할수 있으므로 각 노드는 상하좌우의 노드와 연결되어 있다고 생각 하고 풀면 됩니다. 다음은 코드입니다. #include #include #include using namespace std; #define INF 987654321 int arr[130][130]; priority_queue pq; in..

https://www.acmicpc.net/problem/1261 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 최단경로를 구하는 문제입니다. 출발점에서 N,M까지 가는데 부숴야 하는 벽의 최소 개수를 구해야 하므로 출발지에서 N,M까지의 최단경로를 구하면 해결 할 수 있습니다. 따라서 다익스트라 알고리즘을 통하여 해결하면 됩니다. 노드와 간선으로 정보가 주어지는 것이 아니라 N*M의 판에 대한 정보가 주어지므로 i,j에 위치했을 때는 상 하 좌 우로 이동이 가능하므로 상하좌우 노드와 현재의 노드가 연결 되어 있다고 생각하고 문제를 해결하면 됩니다. 다음은 코드입니다. #include #include #include #include using namespace std; #define I..

https://www.acmicpc.net/problem/1541 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 수식을 입력받았을때 괄호를 적절히 쳐서 최소의 값을 만드는 값을 출력하는 문제입니다. 부호는 +와-밖에 나오지 않으므로 -가 한번이라도 나오면 그 뒤부분은 모두 -로 처리할 수 있음을 알 수 있습니다. 예를들어 2+3-4+5-6+2 라면 -4가 나온순간 4 와 5를 묶고 6과 2를 묶으면 모두 -로 처리 할 수 있습니다. 따라서 그리디하게 처음 - 가 나올때까지의 숫자들과 그 이후 숫자들을 나누어서 서로 합해주면 답을 구할 수 있습니다. 다음은 코드입니다. #include #include using namespace std; int main(void) { ios_base::s..

https://www.acmicpc.net/problem/6549 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 주어진 히스토그램에서 넓이가 가장 큰 직사각형을 구하는 문제입니다. n이 10만 까지있으므로 당연히 모든 넓이를 다 해보는 방법으로는 해결을 할 수 없습니다. 따라서 저는 이 문제를 스택을 이용하여 해결을 하였습니다. 스택을 이용하여 높이가 스택의 top보다 높으면 계속 진행하고 그렇지 않으면 현재 집어넣을 높이보다 높이가 낮아질 때까지 pop하면서 그사이에 존재하는 직사각형의 넓이를 계산해주면서 끝까지 진행해주면 답을 찾을 수 있습니다. 넓이를 계산할 때 현재 높이에 해당하는 부분은 s.top 부분이고 밑변에 해당하는 부분은 top의 원소를 빼준뒤 그다음 top원소가 존재하..

https://www.acmicpc.net/problem/1916 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 원래 다익스트라로 풀어야 하지만 연습겸 벨만포드로 풀어보았습니다. 벨만포드 알고리즘 같은경우 음의 가중치가 있을때 다익스트라를 사용할 수 없으므로 그때 사용을 합니다. 이때 시간복잡도는 O(|V||E|) 만큼 소요되므로 사실 이문제의 입력 최대치를 넣으면 1억이 됩니다. 그래서 시간초과가 나지 않을까 했는데 찾아보니 요즘 컴퓨터는 1억번 반복은 1초안에 해결을 할 수 있으므로 시간초과가 나지 않고 문제가 풀립니다! 간략하게 알고리즘을 설명하면 V-1번의 반복동안 각 정점에서 연결된 정점으로 가는 비용을 완화(더적은 비용이 있으면 그비용으로 교체)시키면서 진행합니다. 벨만포드 ..

https://www.acmicpc.net/problem/11404 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 최단경로 알고리즘중 하나인 플로이드 와샬 알고리즘을 통해서 해결하는 문제입니다. 모든정점과 다른정점들간의 최단경로를 구할때는 O(V^3)이 걸리는 플로이드 와샬 알고리즘이 가장 빠르기 때문에 이를 이용하면 되고 방법은 DP를 이용하여 dp[i][j] = min(dp[i][j], dp[i][k]+dp[k][j]) 라는 점화식을 통하여 k정점을 경유하여 갈때와 기존의 저장된 값과 비교하여 더작은 값을 넣어주면 마지막에는 최단경로가 모두 저장되게 됩니다. #include #include using namespace std; #define INF 987654321 int V,m; ..

https://www.acmicpc.net/problem/3190 문제와 채점은 위 사이트에서 확인 하실 수 있습니다. 이 문제는 뱀이 위치할때 주어진 방향으로 뱀이 이동하며 그위치에 사과가 있으면 꼬리를 그냥두고 사과가 없으면 꼬리를 자르면서 벽이나 자기몸을 만날때 까지 몇초가 걸렸는지 구하는 문제입니다. 저는 뱀이 위치한 곳은 2로 사과가 위치한 곳은 1로 값을 정하고 주어진대로 구현을 하면 되는 문제입니다. 주의할 점은 방향 변환은 이동이 끝난 후에 일어나므로 이점을 주의해야 할 것 같습니다. 또 방향은 왼쪽과 오른쪽이 존재하므로 각 인덱스를 +1, -1 해준다고 생각하면 됩니다. 다음은 코드입니다. #include #include using namespace std; int board[101][1..