거의 알고리즘 일기장

using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Diagnostics; using System.IO; using System.Linq; using System.Runtime.InteropServices; using System.Text; using System.Threading.Tasks; using System.Runtime.Serialization.Formatters.Binary; using System.Threading; namespace ConsoleApp1 { class Program { static void Main(st..

C#은 string으로 입력받아서 parsing해서 사용. 한 문자 입력받을때는 read. using System; using System.Collections; using System.Collections.Generic; using System.Collections.Specialized; using System.Diagnostics; using System.IO; using System.Linq; using System.Runtime.InteropServices; using System.Text; using System.Threading.Tasks; using System.Runtime.Serialization.Formatters.Binary; using System.Threading; namespac..

https://codeforces.com/contest/1213 Dashboard - Codeforces Round #582 (Div. 3) - Codeforces codeforces.com 먼저 풀었던 a, b, c 번 부터 리뷰하고 이후 문제는 아직 풀이를 제대로 하지 못해 이후에 리뷰하겠다. 풀이방법 A. Chips Moving 칩을 옮겨서 같은 곳에 두는 방법중 최소의 수를 찾는 문제다. 먼저 조건을 잘보자. 잘 보면 홀수와 짝수인 개수를 세고 둘중에 작은 것의 개수를 구하는 문제라는 것을 알수있을것이다. 이후는 생략~ B. Bad Prices 이 문제는 지금 위치의 값보다 작은 값이 있는지 없는지 알아보는 문제이다. 별건 없고 역순으로 MIN값을 만들어 비교하면 개수를 세면 끝이다. C. Boo..

https://codeforces.com/contest/1213 Dashboard - Codeforces Round #582 (Div. 3) - Codeforces codeforces.com 코드포스 virtual 처음풀어봤는데 3문제밖에 못풀었다.. 1시간넘게 D번을 시간내에 푸는 방법을 찾지못했다. 그리고 문제 이해도 잘 못하겠어서 많이 힘들었다. 하다보면 늘겠지ㅠ 리뷰 하다간 오늘 밤샐것 같으니 걍 자야지 ㅎ

https://www.acmicpc.net/problem/11055 11055번: 가장 큰 증가 부분 수열 수열 A가 주어졌을 때, 그 수열의 증가 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8} 인 경우에 합이 가장 큰 증가 부분 수� www.acmicpc.net 풀이방법 일반적인 top down 메모제이션 풀이로 풀면 됨. 전체코드 #include #include using namespace std; int A[1001]; int dp[1001]; int N; void dpInit() { for (int i = 0; i > N; for (int i = 1; i > A[i]; } int getMa..

https://www.acmicpc.net/problem/16500 16500번: 문자열 판별 첫째 줄에 길이가 100이하인 문자열 S가 주어진다. 둘째 줄에는 A에 포함된 문자열의 개수 N(1 ≤ N ≤ 100)이 주어진다. 셋째 줄부터 N개의 줄에는 A에 포함된 단어가 한 줄에 하나씩 주어진다. A에 포함된 문자열은 알파벳 소문자로만 이루어져 있고, 길이는 100을 넘지 않는다. www.acmicpc.net 접근 이 문제를 완전탐색으로 푼다면 최악의 경우 100!으로 절대 시간안에 풀수없다. 잘 보면 중복연산이 매우매우 많으니 메모제이션을 사용하자!! 풀이방법 이 문제는 주어진 word들이 S를 만들수 있는지 없는지만 판별하면 되는 문제다. 그러므로 dp[string 길이] : -1일땐 아직 탐색안한..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다. 입력으로 주어지는 모든 수는 정수이다. www.acmicpc.net 풀이방법 그냥 냅색 알고리즘이다. dp[가방종류][무게] = 가질수있는 최대가치 이렇게 dp를 설정해두고, dp[i][j] = max(dp[i][j] = max(dp[i][j], dp[i - 1][j - weight] + value) 이 점화식을 이용해 풀면된다. for (int ..

https://www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 풀이방법 이거 그대~로 풀고 메모제이션 사용하면 정답 전체코드 #include #define DIV_NUM 10007 using namespace std; long long nCk[1001][1001]; int N, K; void nCkInit() { for (int i = 0; i N >> K; nCkInit(); cout

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수� www.acmicpc.net 풀이방법 dp문제이며 직전에 푼 쉬운 오르막과 거의 유사한 문제다. 그냥 똑같다고 보면됨. 그러므로 생략하겠습니다.ㅎ 전체코드 #include #include #define DIV_NUM 10007 using namespace std; long long dp[10][1001]; int N; void dpInit() { for (int i = 0; i

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 주의사항 %를 계산시마다 할것!!! 전체코드 재귀 풀이 #include #define DIV_NUM 1000000000 using namespace std; long long dp[10][101]; int N; void dpInit() { for (int i = 0; i n; long long int result = 0; for (int j = 1; j