Baekjoon

[1920] 수 찾기(C++)

문제 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 해결 방법 1. n개의 정수를 배열 a에 입력받는다. 2. 배열 a를 오름차순으로 정렬한다. 3. 배열 a에 존재하는지 알고싶은 숫자들을 하나씩 입력받으면서 직접 구현한 binsearch 함수를 실행한다. (binsearch 함수는 그냥 일반적인 binary search 함수로 구현하면 된다.) 이 문제에서 핵심은 '시간 초과'가 나지 않도록 하는 것이었다. 처음에는 cin, cout, sort()를 사용하여 코..

[10610] 30

https://www.acmicpc.net/problem/10610 10610번: 30 문제 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶� www.acmicpc.net 🔎 해결 방법 우선 30의 배수가 되기 위해서는 두 가지를 만족해야 한다. 일의 자리가 0 각 자리의 합이 3의 배수 따라서 코드도 이런식으로 짜면 된다. ✍️ 알고리즘 1. string으로 문자열을 입력받은 후, sort 함수를 사용해서 오름차순으로 정렬한다. ex) 입력 : 80875542 -> 정렬한 후 : 02455788 2. 문자열의 첫번째 원소가 0인지 확인 0이라면 30의 배수가 되..

[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을 증가시켜 주면 된다. ..