분류 전체보기 198

[백준] 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,000,000 ~ 1,000,000,000 [백준] 11053 가장 긴 증가하는 부분 수열 DP 배열을 푸는 방법을 알고 있다면 엄청 어렵지 않게 해결할 수 있다. 1~n까지 반복문을 돌면서 이전에 받았던 값들을 다시 탐색하면서 찾아가는 방식으로 문제를 해결했다. □ DP 이용 int n; scanf( hj39-develop.tistory.com 11053을 공부할때 Dp로 푸는 방법과 이진 탐색을 이용해서 푸는 방법을 공부 했었다..

알고리즘/DP 2023.04.16

[백준] 11055 가장 큰 증가하는 부분 수열

이번 문제는 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 2023.04.15

[백준] 10844 쉬운 계단 수

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

알고리즘/DP 2023.04.13

[백준] 9461 파도반 수열

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..

알고리즘/DP 2023.04.08

Result Type

Result 타입은 Gerneric Enumeration으로 선언되어 있고 연관된 값의 성공과 실패를 나타낸다. 말만 들으면 뭔가 헷갈린다. 정의의 윗부분만 가져와 보았다. @frozen public enum Result where Failure : Error { /// A success, storing a `Success` value. case success(Success) /// A failure, storing a `Failure` value. case failure(Failure) enum 타입으로 구성되어 있고 각 case에 연관된 값을 표현한다 where 문법에 의해 failure의 경우에는 Error 타입만 입력받는다. 뭔지 잘 모를 땐?! 예시를 보면 이해를 쉽게 할 수 있다. enum P..

iOS/Swift 상식 2023.03.25

Some

Swift에서 Some 키워드는 리턴 타입을 자동으로 빠르게 추론할 수 있는 기능이다. 예를 보면서 이해하면 빠르게 이해할 수 있다. protocol Shape{ func describe() -> String } struct Square: Shape{ func describe() -> String { return "I'm Square" } } struct Circle: Shape{ func describe() -> String { return "I'm Circle" } } Shape 프로토콜 내부에 describe() 함수를 선언하고 구조체 Square, Circle을 생성하고 Shape 프로토콜을 상속받는다. 그러면 각 구조체에서 describe() 함수는 오버라이딩할 수 있게 된다. func make..

iOS/Swift 상식 2023.03.25

백준[2110] 공유기 설치 (Swift)

문제를 읽었을 때 문제가 이해가 되지 않아서 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

알고리즘/탐색 2023.03.19

백준[2805] 나무 자르기 (Swift)

해당 문제는 나무를 자른 나머지를 더할 때 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..

알고리즘/탐색 2023.03.19