potato's devlog

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 나의 풀이 먼저 규칙을 찾는데 시간이 조금 걸렷다. 과연 이렇게 푸는게 앞에꺼가 세개 반복되지 않고 구하는게 맞나? 싶었던 의심이 들었었다. 하지만 점화식을 생성하면서, 두번 연속 나온건 제외하고 점화식을 세워주면 되는 거였다. (이게무슨말이지,, 말로표현이 안되네 ㅠㅠ) 어쨋든 풀이는 아래와 같다. 예시로 준것 처럼, 포도주가 6개 주어졌따면, 위와 같이 구할 수 있다. 최대가 될 수 ..

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 IDEA 이렇게 발견한 점화식은 아래와 같다. 여기서 dp 는 위에 그림으로 나타낸 최대값들을 저장하는 배열이고, arr 는 우리가 입력받은 스티커들의 가격이 명시되어있는 배열이다. dp[0][i] = max(dp[1][i-1] + arr[0][i], dp[1][i-2] + arr[0][i]) dp[1][i] = max(dp[0][i-1] + arr[1][i], dp[0..

문제 링크 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 풀이 IDEA 사자가 어디 위치에 오느냐에 따라 새로 들어오는 사자들의 위치가 달라진다. 하지만 이 이전에 단순한 숫자규칙이 있는지 찾아보았다. 예시가 N = 4 일때가 주어졌으니, N=1,2,3 을 찾아보았다. N=1 일때 3, N=2 일때 7, N=3일때 17이 되었고, N=4일때는 41이 된다고 했다. 이 숫자들을 통해 규칙을 찾아보면, n-1번째 숫자에 2를 곱하고, n-2번째 숫자를 더해주면 n일때의 값이 나온다는 단순한 숫자규칙이 존재한다. 이처럼 dp 문제에서는 규칙을 찾는 것이 매우 중요하다. 소스코드 -..

안녕하세요, 감자입니다! (왜..오랜만에 인사하는것 같지..) 일주일만에 돌아온 공식 문서 정리입니다.. 이번주 내내 프로토콜 관련해서만 정리한 것 같아요. 그리고 애플아카데미의 시작으로 시간이 너무너무 부족하네요 ㅠㅠ 그래도 지치지도 않고 프로토콜 정리내용을 가져왔습니다. 내용이 너~~~~~무 많아서,, 모든 내용이 다 머릿속에 들어오진 않은 것같아요 ㅠ 더 읽어보고, 실무에서 접해보는 방법 뿐이겟죠? 그럼 즐거운 마음으로 시작해봅시다! gogo Swift Document chap.22 Protocols (프로토콜) 바로가기 Protocols — The Swift Programming Language (Swift 5.6) Protocols A protocol defines a blueprint of m..

문제링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 IDEA 우선, 문제를 읽어보면 조건이 세개 나 달려있지만, 다 같은 말이다. 그저 집의 색상은 앞뒤 집과 겹치지 않아야 한다는 하나의 조건일 뿐인 것이다. 1번집이 빨간색이면, 2번집은 파랑이나 초록이면 되고, 50번째 집이 빨강이라면, 49번집과 51번집은 빨강이 아니면 된다. 나는 이문제를 보고 바로 이 문제(click!!)를 풀었던 경험을 생각했다. 마지..

문제 링크 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 idea 아니 풀다보니, 1,2,3 더하기 관련한 시리즈 문제를 몇개 풀어봤으므로, 더 복잡해야되는데 이게 규칙이라고? 하면서 애매모호하게 풀었던 문제였다. 근데 아니나 다를까 1,2,3더하기 (백준 9095번) 문제랑 그냥 동일한 문제였다. ㅋㅋㅋㅋ 괜히 쫄았네... https://didu-story.tistory.com/225 [백준] (Swift) 9095번 - 1,2,3 더하기 (스위프트 다이나믹 프로그래밍 풀이) 문제 링크..

문제 링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA 규칙을 찾다가 2차원배열로 풀어야한다는 생각을 미처 하지 못해서 인터넷을 참고했다. dp 도 다양한 유형을 풀며 어떤 상황일 경우 어떻게 접근해야하는지 감을 익혀야하는 것 같다. 규칙찾기가 힘들었다. 이런 문제가 나오면 2차원으로 풀자. k개를 더해서 n을 만드는 경우의 수를 배열로 넣으면 된다. 2차원 배열일 경우 표를 그리면서 규칙을 찾아나서면 된다. 생각보다 간단한 규칙이 있다. dp는 무조건 규칙부터! 규칙을 설명해보겠다. 우선 위에서 적은것 처럼 k개의 수를 더해서 n을 만들자! 라는 맥락..

문제링크 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 문제 풀이 IDEA 우선 dp 문제를 만나면, 규칙을 파악하기 쉽게 모든 경우의 수를 수기로 써본다. 이렇게 작성해보았다. 문제의 규칙이 보일듯, 보이지 않았다. dp 배열에 1일때 항의 수 1, 2일때 항의 수 2, 3일때 항의 수 3, 4일때 항의 수 1.. 이렇게 넣으려고 하는 건 알겠다. 근데 이제 어떻게 점화식을 만들어야할까? 우선 나는 아..

문제 링크 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 풀이 idea 앞에서 풀던 dp 문제와 다를 것 없는 문제! 앞에서부터 더해주고 max값으로 바꿔주면 돼. 왜냐면!! 어차피 가장 큰 값을 찾는거라 계쏙 max 값으로 업데이트 되기 때문이다. 소스코드 let n = Int(String(readLine()!))! let arr = readLine()!.split(separator: " ").map{Int(String($0))!} var dp ..

문제 링크 https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 IDEA 우선 해당 문제는 LIS를 구현한 이후에, LIS 부분 수열을 출력하는 문제이기 떄문에 아래 두 개의 포스팅을 모두 이해해야 해당 문제를 수월하게 풀 수 있다. ▷ LIS 란? https://didu-story.tistory.com/236 [알고리즘] (Swift) 최강 증가 부분 수열..