백준

[2352] 반도체 설계(C++)

문제 2352번: 반도체 설계 첫째 줄에 정수 n(1 ≤ n ≤ 40,000)이 주어진다. 다음 줄에는 차례로 1번 포트와 연결되어야 하는 포트 번호, 2번 포트와 연결되어야 하는 포트 번호, …, n번 포트와 연결되어야 하는 포트 번호가 주 www.acmicpc.net 🔎 해결 방법 이 문제는 [11053] 가장 긴 증가하는 부분 수열과 같이 왼쪽 포트는 이미 오름차순으로 정렬이 되어 있으므로 이와 연결된 두번째 포트가 어떻게 해야 가장 긴 증가하는 부분 수열을 이루는지를 찾으면 된다. 그래서 처음에는 [11053] 가장 긴 증가하는 부분 수열 문제를 해결한 것과 같이 이중 for문을 사용한 dp로 해결하려고 했다. 하지만 틀렸습니다가 떠서 질문들을 찾아보니 대부분 "LIS" 라는 알고리즘을 사용하여 ..

[11722] 가장 긴 감소하는 부분 수열

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} � www.acmicpc.net 💡 내 코드(C++) // [11722] 가장 긴 감소하는 부분 수열 // https://www.acmicpc.net/problem/11722 // dp #include #include using namespace std; int main(void) { int n; // size of the sequence int dp..

[11055] 가장 큰 증가 부분 수열

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 💡 내 코드(C++) // [11055] 가장 큰 증가 부분 수열 // https://www.acmicpc.net/problem/11055 // dp #include #include using namespace std; int main(void) { int n; // size of the sequence int a[1001], dp[10..

[11054] 가장 긴 바이토닉 부분 수열

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 💡 내 코드(C++) // [11054] 가장 긴 바이토닉 부분 수열 // https://www.acmicpc.net/problem/11054 // dp #include #include #define MAX 1001 using namespace std; void increase(); void decrease(); int bitonic(); int n, a[MAX] = { 0 }; int dp_inc[MAX], dp_..

[11053] 가장 긴 증가하는 부분 수열

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 💡 내 코드(C++) // [11053] 가장 긴 증가하는 부분 수열 // https://www.acmicpc.net/problem/11053 // dp #include #include using namespace std; int main(void) { int n; // size of the sequence int cn..

[1120] 문자열

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 � www.acmicpc.net 🔎 해결 방법 현재 순간에서 가장 최선의 경우만 고려하는 그리디 알고리즘의 특성을 이용하면 생각보다 코드도 짧고 간단한 문제였다. 예를 들어 A = "adaabc", B = "aababbc" 라면 먼저 (B[0], A[0]), (B[1], A[1]), (B[2], A[2]) ... 이런식으로 비교를 한 다음, 다른 경우에만 gap을 증가시켜 주면 된다. ..

[11051] 이항 계수 2

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 🔎 해결 방법 고등학교 확률과 통계에서 배웠던 파스칼의 삼각형 공식만 기억하고 있다면 매우매우 쉬운 문제이다. 1 > n >> k; dp[0][0] = 1; dp[0][1] = 0; for(int i = 1 ; i

[11048] 이동하기

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 🔎 해결 방법 (1, 1)에서부터 (n, m)까지 가면서 오른쪽, 대각선, 아래쪽 중 가장 큰 값을 더해나가면 되지 않을까? 그럼 dp가 필요없는데? 라고 생각했지만 이 문제를 dp로 풀어야 하는 이유가 있다. 만약의 미로가 위와 같이 주어졌다면, 현재 내 위치에서 갈 수 있는 칸 중 가장 최댓값만 취해서 이동한다면 위와 같이 되고, 이것은 dp가 아니라 그리디 알고리즘이라고 ..