코딩하기 좋은날

https://www.acmicpc.net/problem/1021 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 deque 구조를 이용하여 초기에 원소의 위치를 입력받고 그 원소를 맨 앞으로 위치시켜 뽑아 내는데 push를 몇번 해야 하는지 최소 횟수를 구하는 문제입니다. 저는 이 문제를 우선 순서대로 찾아야 하는 위치의 원소의 현재 위치를 찾은뒤 그 위치가 전체 덱의 사이즈의 1/2 보다 크다면 뒤에서 앞으로 보내고 그렇지 않다면 앞에서 뒤로 보내도록 코드를 작성하였습니다. 해당 위치의 원소를 가장 앞으로 보내기 위해서는 앞의 원소들을 뒤로 보내거나 뒤의 원소들을 앞으로 보내야 하는데 이때 최소 횟수가 되기 위해서는 전체 덱의 사이즈 1/2을 기준으로 판별을 하여야 합니다. 다음은 코드..

https://www.acmicpc.net/problem/5430 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 배열과 R, D 명령을 입력받고 각 명령에 맞게 배열을 변경한후 출력하는 문제입니다. 우선 기본적으로 deque를 사용하여서 풀었고, 배열의 입력은 stringstream을 이용해서 받았습니다. 주의할 점은 R이 나왔을 때 배열을 뒤집으면 시간초과가 나게 됩니다. 배열을 뒤집는게 아니라 덱의 뒷부분에서 원소를 빼는 상황으로 바뀐다고 생각하면 flag를 하나 주어서 현재 상태를 체크해주며 앞,뒤에서 빼주고 배열을 완성한후 출력하면 해결이 됩니다. 다음은 코드입니다. #include #include #include #include using namespace std; int mai..

https://www.acmicpc.net/problem/1916 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 출발 도시에서 도착 도시까지 걸리는 최소비용을 구하는 문제입니다. 따라서 다익스트라 알고리즘을 통하여 구하여야 합니다. 다익스트라 알고리즘이란 우선순위 큐를 사용하여 이동 할 수 있는 정점중 가장 가중치가 적은 경로로 이동하면서 그 정점으로 이동하는데 지금의 비용과 기존에 저장되어 있는 비용중 더작은 비용을 저장하면서 각각의 정점으로 이동하는데의 최소비용을 구하는 알고리즘입니다. #include #include #include #define P pair #define inf 100000001 using namespace std; priority_queue pq; vector v..

https://www.acmicpc.net/problem/16568 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 한길이가 앞에 있는 N명의 사람들의 앞으로 가는 가장 빠른 시간을 구하는 문제입니다. 한길이는 3가지의 동작을 취할 수 있으므로 어떤 i번째 사람의 앞까지 도달하는데 걸리는 시간을 저3가지의 동작중 가장 적게 걸리는 시간이 답이됩니다. 따라서 dp를 이용하여 N번까지 가는데 시간을 구해주면 됩니다. 다음은 코드입니다. #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int dp[1000001]; int N,a,b; cin >> N >> a >> b; fi..

https://www.acmicpc.net/problem/1197 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 MST(minimun spanning tree)의 가중치를 구해서 출력하는 문제입니다. 기본적으로 MST를 구하는 방법은 prim 알고리즘과 kruskal 알고리즘이 있습니다. 저는 두가지 방법으로 모두 풀어봤습니다. 우선 kruskal 알고리즘은 가중치가 가장작은 간선부터 하나씩 이어나가며 모든 정점을 방문하는 방법입니다. 이때 주의할점은 사이클이 발생하게 된다면 그 간선은 건너뛰어야 합니다. 따라서 사이클 발생유무를 체크하기 위해서 kruskal 알고리즘은 유니온 파인드 구조를 사용합니다. 사이클이 생기지 않는 조건은 두 정점의 루트노드가 동일한 경우입니다. 다음은 prim..

https://www.acmicpc.net/problem/1699 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 어떤수가 제곱수의 합들로 이루어질 때 제곱수의 항의 개수가 가장 적은 경우를 출력하는 문제입니다. 저는 이 문제를 bottom - up 방식을 이용하여 반복문을 통하여 해결 하였습니다. dp라는 배열을 선언하고 i라는 숫자에서 i보다 작거나 같은 제곱수를 빼준뒤 기존의 dp[i]에 저장된 값과 비교하여 더작은 값을 넣는 방식입니다. 초기 dp[0] 에는 0을 넣어주고 dp[1]에는 1을 넣어주고 시작합니다. dp[i] = min(dp[i], dp[i-j*j] + 1 ) 라는 식이 최종 식입니다. dp[i-j*j] + 1 의 의미는 j*j 제곱수를 사용하여 i를 만드는 경우 입니..

https://www.acmicpc.net/problem/11054 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 주어진 수열 중 가장 긴 바이토닉 수열을 구하는 문제입니다. 바이토닉 수열이란 한 값을 기준으로 왼쪽은 증가하는 수열이고 오른쪽은 감소하는 수열을 이루는 형태를 말합니다. 따라서 주어진 수열을 입력받고 수열의 첫번째 원소부터 돌면서 그 원소에서 가능한 가장긴 바이토닉 수열의 개수를 dp배열에 저장하면서 문제를 해결하여야 합니다. 완전 탐색으로 풀게 된다면 시간이 많이 걸리게 되므로 dp배열에 i인덱스에서 가능한 가장긴 수열의 개수를 저장해가면서 다음번에 그 인덱스에 저장된 값을 이용 하는 원리입니다. 탐색을 할 때 다음으로 올 원소가 이전원소보다 크다면 증가하는 중이므로 tr..

https://www.acmicpc.net/problem/2167 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 배열이 있을 때 배열의 i,j 에서 x,y까지의 모든 요소의 합을 구하는 문제입니다. i,j 에서 x,y 까지의 의미는 이 두영역이 만드는 사각형을 의미합니다. 따라서 이 사각형의 요소의 합을 구하기 위해서는 1,1지점에서 x,y까지의 사각형의 합들을 미리 저장해 놓고 i,j에서 x,y까지의 사각형을 구하기 위해 나머지 부분을 빼주면 됩니다. 위 그림을 보시면 저사각형 부분에 해당하는 부분은 3,3에서 5,5까지의 부분이 됩니다. 그렇다면 저부분을 구하기 위해서 5,5까지의 사각형 영역에서 1,1에서 5,2 까지의 부분과 1,1에서 2,5까지의 부분을 각각 빼주고 2번 빼준 부..