본문 바로가기

알고리즘

 (82)
[백준] 9251번 LCS C++ 문제풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 소스 코드 #include #include using namespace std; int map[1002][1002] = { 0 }; int main() { string str1, str2; cin >> str1 >> str2; for (int i = 0; i < str1.size(); i++) { char s = str1[i]; for (int j = ..
[백준] 2467번 용액 C++ 문제풀이 https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 풀이 이 문제는 예전에 풀었던 14767번이랑 비슷하게 문제를 해결했다 0에 가장 가까운 값을 만드는 2개의 용액을 찾으면 되는 문제이므로 하나의 vector 배열에 모든 값을 저장한다. 이때 음수인 값은 양수로 바꾼 후 저장하는 대신 -1을 pair의 second로 저장하고 양수인 경우는 pair의 second에 1을 저장한 뒤 정렬을 한다 예를 들어, -99 -2 -1 4 98 이 ..
[백준] 14502번 연구소 C++ 문제풀이 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 풀이 이 문제는 3개의 벽을 어떻게 효과적으로 세울 것인지가 중요한 문제였다. 연구소의 최대 크키가 8x8 이므로 완전 탐색을 이용해 벽을 세우고 bfs를 이용해 세균을 퍼뜨려서 안전지대의 크기가 최대인 값을 구하면 됐다. 사실 시간제한이 2초이긴한데, 완전 탐색을 사용하는게 맞는지 고민을 많이 했는데 맞더라 ㅎ... 소스 코드 #include #include using namespace std; int..
[백준] 11660번 구간 합 C++ 문제풀이 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 풀이 구간합 문제라고 생각하여 한 줄마다 누적합 배열을 만들었다.예를 들어 (2,2)부터 (3,4) 까지의 합이면 (2,1) ~ (2,4) 까지의 누적합에 (2,1)을 빼주고, (3,1) ~ (3,4) 까지의 누적합에 (3,1)을 빼준 뒤 더해주면 답이 나온다. 맨처음에 시간 초과가 나서 cin.tie(NULL), ios_base::sync_with..
[백준] 15650번 N과 M C++ 문제풀이 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 문제 풀이 1 ~ N 중의 수 중에 M개를 오름차순으로 출력하는 문제이다. 문제를 보자마자 백트래킹을 이용해 수열을 탐색해야 한다고 생각해 DFS를 통해 문제의 조건을 만족하는 수열만 출력했다.. bool 타입의 num 배열을 만들어 true인 인덱스의 수만 출력했다. 주의할 점은 dfs를 진행할 때 이전에 true가 된 수의 다음 수부터 탐색을 이어가야 한다는 점이다. 소스 코드 #includ..
[백준] 1629번 곱셈 C++ 문제풀이 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 풀이 시간 제한이 0.5초이기 때문에 맨 처음에는 규칙을 찾는 문제라고 생각했다. 그러나 규칙을 어떻게 표현할 지, 어떤 식으로 규칙을 통해 답을 낼지 감을 잡지 못해 다른 블로거 분들의 글을 읽어보고 이해했다. 일단 이 문제는 10^11 = 10^(5+5+1) = 10^5 x 10^5 x 10^1 임을 이해하고 문제를 풀어야 하더라... 그리고 재귀를 통해서 지수가 1이 나올때까지 나눠주고 나중에 합치는 방식으로 문제를 해결했다. 소스 코드 #includ..
[백준] 1932번 정수 삼각형 C++ 문제풀이 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 풀이 최대가 되는 경우를 구해야하므로 그리디 아니면 DP로 풀어야겠다고 생각을 했다. dp[1][1] = 7, dp[2][1] = 3+7, dp[2][2] = 8+7 이고, dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1]) + (현재 위치의 값)이라는 점화식을 통해 문제를 해결했다. 소스 코드 #include using namespace std; int tree[501][501] = { 0 }; int dp[501][501] = ..
[백준] 14746번 Closest Pair C++ 문제풀이 https://www.acmicpc.net/problem/14746 14746번: Closest Pair Your program is to read from standard input. The input consists of four lines. The first line contains two integers, n (1 ≤ n ≤ 500,000) and m (1 ≤ m ≤ 500,000), where n is the number of points in set P and m is the number of points in set Q. In th www.acmicpc.net 문제 풀이 문제 조건에서 n과 m이 최대 500000이기 때문에.O(n^2)의 시간복잡도를 갖는 알고리즘은 시간초과가 날 것이라고 생..

티스토리툴바