본문 바로가기

알고리즘

 (82)
[백준] 12015번 가장 긴 증가하는 부분 수열 2 C++ 문제풀이 https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 풀이 이 문제의 핵심이라고 생각된 점은 가장 긴 증가하는 부분 수열의 "길이"를 출력한다는 점이다. 따라서 가장 긴 증가하는 부분 수열에 저장되는 배열을 꼭 정확할 필요가 없다. 따라서 LIS라는 배열을 만든 후 배열의 마지막 값보다 크면 배열에 추가하고, 배열의 마지막 값보다 작은 경우 이분 탐색을 통해 숫자를 대치한다. 예를 들어 10 20 30 15 라는 숫자가 들어오면 우리는 10 2..
[백준] 1647번 도시 분할 계획 C++ 문제풀이 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 문제 풀이 이전에 풀었던 최소 스패닝 트리 문제랑 똑같이 풀었다큰 문제 풀이의 차이점이 없어 그냥 코드랑 링크만 첨부한다.https://itcodeheaven.tistory.com/73 [백준] 1197번 최소 스패닝 트리 C++ 문제풀이 문제 풀이 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를..
[백준] 11049번 행렬 곱셈 순서 C++ 문제풀이 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 맨 처음에는 완전탐색하는 방향으로 문제를 해결할까 고민했는데, 아무리 생각해도 아니여서 고민을 했다. DP로 문제를 어떻게 해결할까 고민하다가, 다른 블로거 분의 풀이를 보고 이해했다. 일단 A, B, C, D가 있다고 가정하게 된다면 AB, BC, CD를 계산한 후 ABC행렬의 계산은 A(BC), (AB)C를 비교하는 식으로 확장해 나가면 되는 문제였다. DP[i][j] ..
[백준] 1197번 최소 스패닝 트리 C++ 문제풀이 문제 풀이 최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 의미한다. 최소 스패닝 트리를 만드는 방법에는 크게 Prim 알고리즘, Kruskal 알고리즘이 있는데 결국은 Greedy를 이용한 알고리즘이다. Kruskal 알고리즘은 맨 처음 각 정점마다 집합을 만든다고 생각하고, Edge를 연결할 때는 서로소인 집합인 경우에만 연결한다. 이를 위해서 맨 처음 가중치를 오름차순으로 정렬하고, 두 정점이 서로소인 집합인지를 확인하면서 연결하면 된다. Edge의 수는 정점의 수 - 1 개이므로 cnt = n-1일 때 까지 위의 과정을 반복하면 된다. 소스 코드 #include #include #include using namespace std; l..
[백준] 10942번 팰린드롬? C++ 문제풀이 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 풀이 맨 처음에 감을 잡지 못해서 알고리즘 분류를 봤더니 DP...? 그때부터 DP로 문제를 풀 방법을 계속 생각했던거 같다. S == E 인 경우는 무조건 팰린드롬이다 . 그리고 S = i , E = j 일때 i번째 수와 j번째 수가 같고, i+1 ~ j-1까지의 수가 팰린드롬이라면 -> i ~ j 는 팰린드롬이다. 위와 같은 규칙을 세우고 코드를 작성했는데 시간초과... ios::sync_with_stdio(false); ci..
[백준] 27172번 수 나누기 게임 C++ 문제풀이 문제 풀이 맨 처음에는 간단하게 이중 for문으로 코드를 작성했는데, 시간 초과로 바로 틀렸다 이중 for문이더라도 에라토스테네스의 체의 시간 복잡도는 O(Nlog(log N)) 이므로 에라토스테네스의 체 방식을 적용해 문제를 해결했다. card 벡터에 를 저장하고, check 배열에는 카드를 가지고 있는지를 저장, score 배열에는 card 번호에 대한 점수를 계산한다. 그리고 아래의 방식처럼 에라토스테네스의 체 방식을 적용해 점수를 계산한 후 출력해줬다. for (int i = 0; i N; int max_idx = 0; //카드 번호 중 가장 큰 수 for (int i = 0; i < N; i+..
[백준] 17404번 RGB거리 2 C++ 문제풀이 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 이 문제는 1번 집과 N번 집의 색을 고려해 문제를 해결해야하기 때문에 조금 까다로웠다. 2중 for문을 통해 1번 집의 색을 고정 시킨 후 dp를 통해서 비용의 최솟값을 구하면 되는 문제이다. 소스 코드 #include using namespace std; #define MAX 1001 * 1001 int cost[1001][3]; int dp[1001][..
[백준] 9252번 LCS 2 C++ 문제풀이 https://www.acmicpc.net/problem/9252 9252번: LCS 2 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; //map을 채우는 코드 for (int i = 0; i < str1.size(); i++) { char s = str1[i..

티스토리툴바