Doby's Lab

https://www.acmicpc.net/problem/2407 2407번: 조합 n과 m이 주어진다. (5 ≤ n ≤ 100, 5 ≤ m ≤ 100, m ≤ n) www.acmicpc.net 이번 문제는 (https://jaimemin.tistory.com/682)을 참고한다. 개념 학생 때 배웠던 nCr 개념이 등장한다. 정확히는 n Combination r이라고 부른다. 이와 같이 따라오는 게 nPr로 이는 n Permutation r이라고 부른다. 이 둘은 조합론으로 둘 다 공식이 존재한다. 솔루션 1 (실패) 이 공식을 활용하여 두 개의 팩토리얼 함수를 구현하여 풀려고 했다. [조금 다른 방식의 팩토리얼 함수] 각각 n!, (n - r)!, r! 은 시간이 오래 걸릴뿐더러 숫자까지 너무 커질 ..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이번 문제는 TC를 보고 나서 점화식을 어떻게 짜야할지 혼란을 가져다주는 문제였다. 하지만, TC를 간단하게 생각해보면 쉽게 풀 수 있었다. 솔루션에 도달하는 과정 5 50 10 100 20 40 30 50 70 10 60 다음 TC가 문제를 다시 생각해보게 했었다. 그 전의 코드는 이렇다. #include #include using namespace std; int T; int cac..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 아무 생각 없이 풀었다가 TLE가 나왔다. [첫 시도] 각 행에서 누적합을 temp에 저장해 두고 명령을 내리면 합을 구하게끔 했지만 이마저도 TLE가 나온다. >> TLE가 나온 이유는? 각 행의 누적합을 구해놓는다 한들 m이 가지는 최댓값이 100,000 표의 크기로 주어질 수 있는 최댓값이 1024로 1~1024행까지 구하는 명령이 100,000번 ..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 이번 문제는 개인적으로 너무 아쉬웠다. 각 항의 관계성까지 파악하고, 이런 비슷한 문제가 있었던 걸 기억하여 비슷하게 구현해보려 했는데 구현이 되지 않아서 거의 90%까지 왔지만 결론적으로는 풀지 못 한 문제다. [기억했던 비슷한 문제] https://draw-code-boy.tistory.com/51?category=963936 [알고리즘] 백준 1149번: RGB거리 (C++), 점화식... '점화식을 어떻게 세울 것인가'가 큰 관건이었다. '큰 문제를 작은 문제로 나누자'라는 키워드는 이제 금방 떠오르고, 나눌 수 있었지만 ..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 요즘 블로그 임시저장 기능을 너무 많이 사용하는 거 같아서 조금 정리 차원에서 글을 쓴다. 핑계를 덧붙이자면 임시저장 글 중에 '가장 긴 증가하는 부분 수열 (LIS)'도 있는데 그 문제 포스팅하기 전에 이거 먼저 해두면 좋을 거 같아서 먼저 포스팅한다. 우선 기본적으로 나오는 점화식은 cache[i] = cache[i - 1] + arr[i]; 다음과 같다. 하지만, 무작정 더하면 최댓값을 도출하지 못한다..

https://www.acmicpc.net/problem/4150 4150번: 피보나치 수 피보나치 수열은 다음과 같이 그 전 두 항의 합으로 계산되는 수열이다. 첫 두 항은 1로 정의된다. f(1) = 1, f(2) = 1, f(n > 2) = f(n − 1) + f(n − 2) 정수를 입력받아, 그에 해당하는 피보나치 수를 출력 www.acmicpc.net 이 문제는 저번에 풀었던 문제와 똑같다고 생각했다. (https://www.acmicpc.net/problem/10826) 당연히 포인트도 똑같이 수를 문자열로 바꾸어 합을 구하는 함수를 구현하는 게 포인트라고 생각했다. 똑같은 풀이를 제출했으나 '메모리 초과'라는 오류를 받는다. 메모리가 크게 발생할 곳은 배열 밖에 없다고 생각했지만 배열을 안 ..

아직도 DP의 문제를 푸는 데에 있어서 어려움을 겪는다. 그래도 전보다 나아진 것은 다음과 같다. 1. 작은 문제는 무엇이며 이 작은 문제들이 모여서 어떠한 큰 문제를 풀어야 하는지 탐색하려 한다. 2. 작은 문제들의 관계성에 중심을 두고 있다. 3. 어느 정도 코드의 구조를 알게 되었다. (감각의 관점) 그래서 이번 문제는 각 정수의 합을 나타낼 수가 몇 개가 있는지 적어보며 관계성을 파악하려 했다. 하지만, 규칙은 알 수가 있어도 어떠한 관계인가?라는 질문에는 정확한 대답을 내놓을 수 없었다. 풀이를 찾아보다가 다음의 풀이를 발견하게 되었다. https://blog.naver.com/PostView.nhn?blogId=vjhh0712v&logNo=221470862600 백준 알고리즘 9095번 문제풀..

DP의 접근 방법이 꽤 어려웠다. 아무래도 점화식을 어떻게 세우는지 접근을 하지 못 했다. (BFS로 풀릴 거 같아서 BFS로 푼 풀이는 맨 아래에 첨부해두었다.) 그래서 다른 사람의 코드를 참고했다. (Bottom-Up 방식) #include #include #include using namespace std; int cache[100001] = { 0, }; int main() { int n; cin >> n; for (int i = 2; i > n; bfs(n); sort(answer.begin(), answer.end()); cout