컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 해결 알고리즘 dp[i][j]에서 i는 배열의 i번째 원소 까지라는 뜻이고 j는 시간이다. dp[i][j]는 i번째까지의 원소들 중에서 j시간을 썼을 때, 최대 메모리이다. 소스 코드 #include using namespace std; int N, M; int Byte[101], Time[101], dp[101][10001], Sum = 0; int main(){ cin >> N >> M; for..

https://www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 문제 해결 알고리즘 근우는 더 큰 카드를 갖고 점수를 최대로 하고, 명우는 근우의 점수가 최소로 되는 방향으로 플레이 해야한다. 소스 코드 #include using namespace std; int arr[1001], dp[1001][1001]; int cardgame(int left, int right, int turn){ if(left > right) return 0; if(dp[left][ri..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 해결 알고리즘 간단한 문자열 + DP 문제 문자열을 탐색할 때, 두 문자가 같으면 그 두개의 전에 해당하는 배열에서 +1한 값을 입력한다. 거기서 최댓값을 구해준다. 소스 코드 #include using namespace std; int dp[4001][4001], result = 0; int main(){ string str1, str2; cin >> str1 >> str2; s..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍으로 주변에 있는 사각형들 중 가장 작은 크기의 정사각형 크기에서 + 1 해준다. 갱신해줄 때마다 최댓값도 갱신해준다. 소스 코드 #include using namespace std; int n, m, result = 0; int dp[1001][1001]; void find_max_square(){ for(int k=1;k> m; for(int i=0;i> str; for(int j=0;j

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제 해결 알고리즘 백트래킹으로 네 개의 칸까지 가는 경우의 합들의 최댓값을 구한다. 이 부분은 백트래킹으로는 탐색이 불가능하므로 따로 완전탐색을 실행해주어야한다. 소스 코드 #include using namespace std; int N, M, result = 0; int arr[501][501]; bool visited[501][501]; int dir[4][2] = {{0, 1}, {0, -..

https://www.acmicpc.net/problem/2268 2268번: 수들의 합 7 첫째 줄에는 N(1 ≤ N ≤ 1,000,000), M(1 ≤ M ≤ 1,000,000)이 주어진다. M은 수행한 명령의 개수이며 다음 M개의 줄에는 수행한 순서대로 함수의 목록이 주어진다. 첫 번째 숫자는 어느 함수를 사용했는 www.acmicpc.net 문제 해결 알고리즘 세그먼트 트리 기초 문제 long long자료형을 써주고, 합을 구할 때 b와 c가 무조건 c가 크게 주어지지 않기 때문에 이 점 유의하여야한다. 소스 코드 #include #define ll long long using namespace std; const int MAX = 1000000; int N, M; ll arr[MAX+1], tr..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 해결 알고리즘 빙산의 위치를 따로 받아서 바로바로 빼고 다해주는 방식으로 해야 시간초과를 피할 수 있다. 옆에 바다가 있다고 바로 빙산에서 빼주지 말고 따로 배열을 만들어서 거기에 뺄 값을 저장해두고 for문이 끝나면 한 번에 빼줘야 문제에서 원하는대로 빙산이 녹는 걸 구현할 수 있다. BFS를 이용해 두 가지로 나누어졌다면 년도를 출력해준다. 아니면 0을 출력함. 소스 코드 #incl..

https://www.acmicpc.net/problem/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 문제 해결 알고리즘 LCA 문제인데 여기에 각각의 거리도 같이 다이나믹프로그래밍 해주면서 LCA를 해준다. 아무 노드나 루트와 잡아도 상관 없는 문제 소스 코드 #include using namespace std; const int MAX = 40000; const int i_MAX = 16; int N; vector tree[MAX+1]; int parent[MAX+1][i_MAX], ..

LCA(최소 공통 조상)이란? 두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 알고리즘이다. 동작 과정 1. 최소 공통 조상을 찾을 두 노드를 확인한다. 2. 먼저 두 노드의 깊이를 같게 만들기 위해 깊이가 더 큰 쪽이 작은 쪽의 깊이에 맞게 거슬러 올라간다. 3. 부모가 같아질 때까지 계속 거슬러 올라간다. 4. 이 과정을 계속 반복해준다. 알고리즘 사례 예를 들어, 이러한 트리가 있다고 가정하자, 이 때, 트리의 노드들의 깊이는 각각 다음과 같다. 6번 노드와 10번 노드의 LCA를 구해보자. 두 노드의 깊이가 각각 2와 3으로 같지 않으므로 두 노드의 깊이를 맞춰주는 작업을 진행해준다. 두 노드의 깊이가 같아졌다면 이제 두 노드가 같아질 때까지 거슬러 올라가준다. 6번 노드와 10번 노드의 ..

https://www.acmicpc.net/problem/11438 11438번: LCA 2 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 문제 해결 알고리즘 LCA 기본 문제 https://kimmessi.tistory.com/230 위의 문제와 다르게 다이나믹 프로그래밍을 이용해 2의 몇 제곱만큼 트리를 거슬러 올라가서 $M$만큼의 시간이 들 것을 $\mathrm{log} M$만큼의 시간복잡도를 낮춰줄 수 있다. 소스 코드 #include using namespace std; int N, M; const int MAX =..