potato's devlog

문제 링크 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 문제 풀이 IDEA 초반에 도대체 이게 무슨 소리야, 그냥 오름차순이면 수열이 되는거임? 라고 생각하며 의아했지만, 바로 그게 잘 이해한 거였다. 최장 증가 부분 수열 (LIS, Longest Increasing Subsequences) 라는 개념인데, 주어진 배열에서 오름차순으로 이루어진 수열 중, 가장 긴..

최장 증가 부분 수열 (LIS,Longest Increasing Subsequence) 이란? 어떤 임의의 수열이 주어질 때, 이 수열에서 몇 개의 수들을 제거해서 부분 수열을 만들 수 있다. 이때 만들어진 부분 수열 중 오름차순으로 정렬된 가장 긴 수열을 "최장 증가 부분 수열"이라고 한다. - 나무위키 🌳 ▷ 예시를 들어보자. [ 3, 5, 7, 9, 2, 1, 4, 8] 다음과 같은 수열이 있다고 하자. 이 수열에서 몇 개의 수를 제거해서 부분수열을 만들 수 있다. 몇 개의 수를 제거해서 오름차순으로 이루어진 수열을 최장 증가 부분 수열이라고 하였는데, 즉, '공차'가 존재하지 않아도 부분수열이라고 본다는 것이다. (규칙적이지 않고 오름차순이면 된다는 뜻) 따라서 위 수열에서 도출될 수 있는 부분수..

문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 풀이 IDEA N=2 부터 규칙을 찾아보니까, 이전에 풀었던 동적계획법 문제와 비슷하게 끝자리에 따라서 경우가 나뉘었다. 아래와 같이 점화식을 도출할 수 있다. 이를 코드로 구현하면 아래와 같다. let n = Int(readLine()!)! var dp = [[Int]](repeating: Array(repeating: 0, count: 2), count: n+1) if n..

문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA dp를 꾸준히 풀다보니, 어떤게 2차원으로 풀어야할지, 어떤게 일반 dp 1차원 배열로 풀어야할지 감이 잡혔다. 올레! 해당 문제는 N=1 부터 경우의수를 하나씩 따져가며 그림을 그려보니, 규칙이 눈에 보였다. 찾은 규칙은 아래와 같다. 위 그림을 보면, 맨 뒷자리수가 0과 9인 경우에는 한가지씩 늘어날 수 있고, 1~8 이라면 두가지의 경우로 늘어날 수 있다는 규칙을 찾아낼 수있다. 이를 dp 경우의수에 맞게 도식화 하면 아래와 같다. 현재 N에서, 0을 맨 뒷자리로 가지려면, N-1..

안녕하세요, 감자입니다. 오늘은 Extension에 대해서 공부해본 내용을 정리했어요. 그럼 시작! Swift Document chap.21 Extension 바로가기 Extensions — The Swift Programming Language (Swift 5.6) Extensions Extensions add new functionality to an existing class, structure, enumeration, or protocol type. This includes the ability to extend types for which you don’t have access to the original source code (known as retroactive modeling). Exten..

문제 링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 IDEA (DP 어렵다 .. 나중에 코딩테스트 문제를 연습할때 dp 부분을 집중적으로 공략할 것이다 ㅠㅠ ) 먼저 풀었던 "백준 9095번 1,2,3 더하기" 와는 다르게, 더해지는 숫자의 "순서!!"를 생각해야한다는 점이 어려웠다. 9095번 4를 만들기 위한 경우의 수 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 같은 수 중복 가능 15990번 (지금 문제) 4를 만들기 위한 경우의 수 1+2+1 1+3 ..

안녕하세요, 감자입니다. 오늘은 공식문서 20번째 챕터 중첩 타입에 대해서 공부한 글을 정리해보려고 합니다. 아직 앱개발을 막 해본 경험이 없어서 해당 중첩타입에 대해서도 약간 애매모호하게 이해가 되는 감이 없지 않아 있네요. 차차 잘 알게 되겟죠? ㅎㅎ 일단 기초 빡세게 잡아봅시다. Swift Document chap.20 Nested Types 바로가기 Nested Types — The Swift Programming Language (Swift 5.6) Nested Types Enumerations are often created to support a specific class or structure’s functionality. Similarly, it can be convenient to de..

문제 링크 https://www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 IDEA 이전 문제 "카드 구매하기"를 먼저 풀어보면 바로 알 수 있는 문제이다. (복습한다는 생각으로 다시 풀이 아이디어를 적어보자) 구매를 원하는 카드의 수를 n , 카드 팩 각각의 가격을 배열 p 에 입력을 받을 것이다. dp 배열을 생성하여 조건 범위 밖의 수인 99999 를 n+1 크기만큼 넣어준다. 가장 큰 수 999999를 넣는 이유는, 우리는 min 값을 구할 것이다. ..

안녕하세요, 지치지 않고 돌아온 공식문서 정리 포스팅입니다. 요즘 애플 디벨로퍼 아카데미도 붙었다, 스터디도 한다, 하면서 개인공부를 조금 소홀히 하고 있는데, 정말 반성하는 의미로다가 오늘은 좀 공부도 아침 일찍 시작해봤어요... 갓생 살아보자아ㅏ아... 갓생산다고는 하는데, 언제나 만족스러운 갓생을 살아본적은 아직 없는 것같아요. 언제쯤, 제 기대치에 만족할만한 공부의 양을 채우고 하루를 정말 알차게 살 수 잇을까요? 흠흠흠... 노력해봅시다 모두 화이팅 그럼 공식문서 정리 시작! Swift document chap.19 Type Casting 바로가기 Type Casting — The Swift Programming Language (Swift 5.6) Type Casting Type casting..

안녕하세요, 감자입니다. 오늘은 WWDC21 에서 등장한 동시성에 대해서 공부했어요.. 넘 어렵더군요 ㅠㅠ 그래서 조금 더 참고하고 이해가 필요할 것 같아요.. 흑흑.. 그래서 공식문서 맨 마지막에 참고해서 더 공부해볼 자료를 첨부해두었어요. 모두 가서 읽어보고 제대로 된 이해를 해봅시다 ㅠㅠ 아직 갈길이 멀군요.. Swift documents chap.18 Concurrency 보러가기 Concurrency — The Swift Programming Language (Swift 5.6) Concurrency Swift has built-in support for writing asynchronous and parallel code in a structured way. Asynchronous code c..