JJ_blog

이름은 쉬운데 문제는 전혀 쉽지가 않다.. 계단 형식으로 된 숫자들을 찾는 건데 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..

swift로 백준 문제를 풀 때는 시간초과를 항상 고려해야한다. 처음에는 C++에서 풀었던 방식으로 배열을 정렬하고 해당 요소의 첫 번째 인덱스와 마지막 인덱스를 구해서 빼려고 했지만 곧바로 시간초과.. ㅠ dictionary를 이용하면 배열을 도는 그런 시간을 아낄 수 있기에 dictionary를 사용하여 문제를 해결하였다. import Foundation func numberCard2(){ let _ = readLine()! var arryM = readLine()!.split(separator: " ").map({Int($0)!}) let _ = readLine()! let arryN = readLine()!.split(separator: " ").map({Int($0)!}) var dict = [..

해당 문제는 백준[1654] 랜선 자르기와 매우 흡사한 문제이다. 재귀함수를 이용하면 코드가 간결해져서 쉽지만 시간초과가 날까 봐 재귀함수를 사용하지 못하겠다ㅜ #include int findMaxBranches(vector &arr, int M, int start, int end){ int result = 0; while(start= M){ result = mid; start = mid + 1; } else{ end = mid - 1; } } return result; } void cutTree(){ int N,M; scanf("%d%d",&N,&M); vector arr; for(int i=0;i

이분 탐색을 살짝 응용한 문제인데 Cpp 라이브러리를 찾다가 이분탐색을 쉽게 사용하는 함수가 있었다.! upper_bound 이분 탐색을 수행하여 원하는 값의 마지막 주소값을 반환 lower_bound 이분 탐색을 수행하여 원하는 값의 첫 번째 주소값을 반환 위 함수를 이용하면 이분탐색을 손쉽게 할 수 있다. #include void numberCard2(){ int N; scanf("%d",&N); vector arrN; for(int i=0;i

이분탐색을 이용하면 쉽게 해결할 수 있는 문제이다. scanf와 printf를 대신 cin, cout을 사용하면 시간초과가 날 수도 있다. #include int recursiveFindNumber(vector &arr, int target, int start, int end){ if(start > end) return 0; int mid = (start + end) /2; if( arr[mid] == target) return 1; else if (arr[mid] > target) return recursiveFindNumber(arr, target, start, mid-1); else return recursiveFindNumber(arr, target, mid+1, end); } void findN..