JJ_blog

수열 문제를 풀다 보니 4,5번까지 오게 됐다! 14002, 14003은 앞선 문제들(12015, 12738)과 다르게 부분 수열의 최대 길이뿐만 아니라 부분 수열도 출력을 해야 한다. 물론 Dp 방식으로 문제를 풀면 14002는 해결할 수 있지만 14003은 범위 때문에 시간초과로 해결하지 못한다. 이번 문제에서도 아래 문제에서 풀 듯이 이진탐색을 섞어서 풀었다. [백준] 12015, 12738 가장 긴 증가하는 부분 수열 2,3 11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000..

11053, 12015, 12738 모두 같은 입력 같은 출력을 하지만 범위만 다르다! 11053 12015 12738 수열A 크기 1 ~ 1,000 1 ~ 1,000,000 1 ~ 1,000,000 수열 A 요소의 범위 1 ~ 1,000 1 ~ 1,000,000 -1,000,000,000 ~ 1,000,000,000 [백준] 11053 가장 긴 증가하는 부분 수열 DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf( hj39-develop.tistory.com 11053을 공부할때 Dp로 푸는 방법과 이진 탐색을 이용해서 푸는 방법을 공부 했었다..

이번 문제는 11053과 다르게 가장 긴 수열의 길이를 찾는 게 아닌 증가하는 수열들 중에서 가장 큰 합을 가지는 부분 수열을 찾는 문제이다. 11053에서 찾은 새로운 방법(이진 탐색)으로 합을 찾아보려고 했지만.. 할 수 없는 건지 실력이 부족한 건지 풀 수가 없었다. ㅠㅠ 더 공부한 후에 다시 도전해 봐야지 그래서 결국 DP를 이용하여 문제를 해결했다. 11053에서 DP를 이용한 방법과 아주 유사하다. 앞선 문제에서는 dp 배열에 길이를 저장했다면 이번 문제에서는 dp 배열에 원소의 합을 저장해 주면 된다. □ 소스코드 void best11055(){ int n; scanf("%d",&n); int array[1001] = {0}; int dp[1001] = {0}; for(int i=1;i

DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf("%d",&n); int dp[1001] = {0}; int array[1001] = {0}; for(int i=1;i

이름은 쉬운데 문제는 전혀 쉽지가 않다.. 계단 형식으로 된 숫자들을 찾는 건데 DP 문제라 규칙을 찾는 것이 가장 중요하다!! 하지만 규칙을 찾으려고 자리 수별로 숫자도 세보고,, 자리 수의 첫 번째 자리, 마지막 자리만 떼서 규칙을 찾아봤지만 이런거로는 규칙을 찾을 수 없었다.. ㅠㅠ 도움을 받은 블로그..! https://yabmoons.tistory.com/22 [ 백준 10844 ] 쉬운 계단 수 (C++) 백준의 쉬운계단수(10844) 문제이다.( 문제 바로가기 ) [ 문제를 다시 푸는 과정에서 보다 구체적인 설명을 해 놓은 글을 다시 포스팅 하였습니다. 아래의 글을 읽더라도 무관하지만 , 보다 구체적 yabmoons.tistory.com 해당 블로그 해설을 보고 이해 한 후에 문제를 풀었다...

DP 문제들은 문제를 풀 수록 어렵네; 점화식 찾기가 너무 어려워ㅓㅓ 최대값을 구하는 방법으로 입력받은 값 array[i]과 이전까지의 값(dp[i-1])을 비교하여 큰 값을 dp[i]에 저장하면 된다. #include using namespace std; void yeun1912(){ int n; scanf("%d",&n); int array[100'001]; int dp[100'001]; for(int i=0;i

9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net /* num = 1 MARK: => 1 num = 2 MARK: => 1 num = 3 MARK: => 1 num = 4 MARK: => 2, P(1) + P(2) num = 5 MARK: => 2, P(2) + P(3) num = 6 MARK: => 3, P(3) + P(4) num = 7 MARK: => 4, P(4) + P(5) num = 8 MARK: => 5, P(5) + P(6) num = 9 MARK: => 7, P(6) + P(7) num = 10 MA..

문제를 읽었을 때 문제가 이해가 되지 않아서 3번 정도 읽고, 머리로는 이해했지만 이게 이진탐색이라고.?라는 생각이 곧바로 들었다. 이전 실버 난이도 문제에서는 이진탐색을 이용하겠네 라는 생각이 들고 그 생각을 가지고 살짝 응용한다면 골드 문제부터는 이진탐색을 적용해야 하는 mid, start, end 기준을 스스로 생각하여 정해야 풀 수 있는 문제들인 것 같다. 어렵.. mid 기준만 정하는 게 가장 큰 난관이다.ㅠㅠ import Foundation func findMaxOfMinimum(arr: [Int], start: Int, end: Int, c: Int) -> Int{ var start = start var end = end while start

해당 문제는 나무를 자른 나머지를 더할 때 total 값이 21억~~~(C++기준)을 넘어갈 까봐 Int32로 했지만 런타임 에러 발생.. 그래서 인터넷에 찾아보니 Swift 기본 자료형 Int는 엄청 범위가 넓다;; 괜한 걱정을 했네..; import Foundation func binarySearchCutTree(arr: [Int], M: Int, start: Int, end: Int) -> Int{ var start: Int = start var end: Int = end var result: Int = 0 while start = mid{ total += data - mid } } if total >= M{ start = mid + 1 result = mid } else{ end = mid - 1..

C++을 풀었을 때와 로직은 같지만 Swift에서 지원해주는 라이브러리들이 편리해서 코드를 간결하게 작성할 수 있는 것 같다. import Foundation func binarySearchCutLan(arr: [Int], start: Int, end: Int, target: Int) -> Int{ var start = start var end = end var result = 0 while(start = mid{ total += data / mid } } if total >= target{ start = mid + 1 result = mid } else { end = mid - 1 } } return result } func cutLan(){ let input = readLine()!.split(sep..