Algorithm/Beakjoon

https://www.acmicpc.net/problem/1325 > n >> m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i > m; for(int i = 0; i > a >> b; vec[b].push_back(a); } for(int i = 1; i

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 1. Logic - 처음엔 dp테이블을 2차원이라고 생각했지만 인덱스 갯수가 1500000이기 때문에 dp table이 2개가 아닌 한개라고 생각했다. - 부분문제를 쪼개봤다 1. 해당 날짜의 상담을 할때 - idx + 상담에 필요한 시간 + 상담으로 받은 상담비용 2. 해당 날짜의 상담을 안할때 - 상담을 안하고 다음 인덱스로 넘어가기 2. Code #include using namespace std; int n; vector vec; int dp[1500001]; int solve(int cur) { if(cur == n) ret..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 1. Logic - Topdown 방식으로 풀이 현재 index에서 갈 수 있는 방향이 한정되어있기 때문에 아래의 좌우 로 한개씩 보내주고 리턴되는 값 중 최댓값을 대입한다. DP table : dp[몇번째 층인지][몇번째 숫자인지] 재귀를 타고 내려가면서 층수를 한개 올려주고 현재 노드의 인덱스와 같은 인덱스 한개 + 1한 인덱스 한개를 재귀로 보내줫다. 2. Code #include using namespace std; int n; int dp[501][501]; ..

https://www.acmicpc.net/problem/15903 15903번: 카드 합체 놀이 첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다. 두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, www.acmicpc.net 1. Logic - 카드를 최소한의 점수로 합체하기 위해서는 가장 작은 값끼리 묶어서 합쳐야 하기 때문에 우선순위 큐를 사용해서 가장 앞에 오는 두개의 수를 가지고 계산을 돌려준다! 2. Code #include using namespace std; priority_queue pq; int main() { long long n, cnt; cin >> n >> ..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 1. Logic - 해당 문제는 주어진 배열을 앞에서 부터 풀이하게 될 경우 최댓값까지 배열을 돌고 또 최댓값을 구해서 배열을 돌아야해서 이중 for문을 사용하게 되어 시간복잡도가 O(n^2)이지만 뒤에서부터 풀이하게되면 다음값을 보고 최댓값인지 알 수 있기 때문에 O(n)으로 풀 수 있다. 최악의 경우를 생각 해 봤을 때 10000 *999999 곱하게되면 int 의 범위를 훨씬 넘..

https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 1. Logic 1. 주어진 정수 X를 조건대로 검사하며 조건에 맞게 재귀함수에 넣어 계산 한 후 임시 변수 next에 담는다. 2. 다음에 나올 값이 현재의 dp에 담긴 값보다 작아야 연산을 최소로 하기 때문에 해당 next값과 현재 ret 즉 지금의 dp[num]값과 비교를 해서 next값이 더 작다면 dp와 나중에 path를 출력해줄 before 배열을 갱신시켜준다. 2. Code #include using namespace std; int n; const int INF = 987654321; i..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. Logic - 처음에 구현한 방식은 DP테이블을 세우고 재귀함수로 문제를 풀었었다. 동전의 sum 값과 얼마짜리 동전을 사용했는지를 표기하는 DP테이블을 구성했고 dp[10001][101]로 구성했다 이렇게 되면 n * k만 해도 4MB가 넘어가므로 당연하게도 메모리초과가 났다. 이 다음 생각한 방법으로는 상향식으로 흔히 점화식을 세워서 푸는 방법으로 풀었다. 항상 재귀로 풀으려고해서 점화식을..

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 1. Logic - 분기가 +, -로 이루어지기 때문에 2개의 재귀를 들어가야한다. - DP Tabel을 생성할때 처음 인자는 sum의 범위, 두번째 인자는 몇번째 인덱스를 돌고있는지 체크한다. 2. Code #include using namespace std; int n; vector vec; long long dp[30][101]; long long solve(int sum, int c..

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 1. Logic 1. 인접한 두 칸에 있는 사탕을 서로 바꿔야하기 때문에 swap함수를 사용해서 값을 변경해 준다. 2. 같은 색의 사탕을 먹어야 하기 때문에 현재칸과 그 다음칸을 비교하면서 진행하며 cnt를 올려준다. 3. 최댓값을 갱신해준다. 2. Code #include using namespace std; vector vec; int n; int calc() { // 가로 int ans = -92735; for(int i = 0; i < n; i++) { int cnt = 1; for(int j = 0; j..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 1. Logic 2가지 상황으로 분할해 볼 수 있다. 1. n이 99이하인 경우 2. n이 100이상인 경우 - 1 ~ 99까지의 수는 항상 등차수열을 이루기 때문에 99이하의 숫자가 나오게되면 즉시 숫자를 리턴한다! - 100이상의 숫자는 어짜피 999까지 비교하면 되기 때문에 3부분으로 나눠서 100자리 10자리 1자리 숫자를 각각 비교한다. 2. Code #include using namespa..