potato's devlog

🟠 문제 https://www.acmicpc.net/problem/15656 15656번: N과 M (7) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 🟠 첫번째 풀이 - 시간초과 (ㅂㄷㅂㄷ) 해당 문제도 마찬가지로, 앞에서 풀었던 것들과 동일한 문제이다. 단지, 입력을 받은 수로 수열을 출력해달라는,,,, 이것과 똑같은 문제는 N과 M(3) 이다. 아래 풀이를 올려놨다. (이때도 시간초과가 났엇네? ㅋㅋㅎㅎ) https://didu-story.tistory.com/374 [백준] (Swift) 15651번 - N과 M(3) (..

🟠 문제 https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 🟠 나의 풀이 이 풀이는 또,,, 모든 것을 N과 M(1)을 기반으로 풀이가 이루어지고, 그 내부에서 입력만 달라진다. 돌아가는 방식은 오름차순으로만 이루어지고 현재 돌아가는 수보다 더 큰 수가 수열내부에서 올 수 있기 때문에 매개변수로 +1 해준 값을 넘겨주면 된다. 자세한 풀이는 아래 링크를 보자.. 전체적인 자세한 풀이를 보고싶다면 (1)으로 https://didu-stor..

🟠 문제 https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 🟠 나의 풀이 N과 M (1)번문제와 아예 똑같은문제이다. 그냥 입력받은 수로 수열을 출력하는 것일뿐!! 해당 포스팅은 아래 남겨 놓겠다. 저기에 더 자세한 풀이가 나와있다. 이거 그냥 문제도, 코드도 외우겟다 ;; 얼른끝내야지 N과 M시리즈,,,, 이렇게 반복하면서 재귀를 풀다보니 DFS 재귀로 돌리는 방식은 완전히 이해할 것 같다! 화이팅 https://didu-story.t..

🟠 문제 https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🟠 내가 푼 풀이 N과 M문제 세트가... (8)까지 있었던것 같은데,,, 이틀 정도만 얼른 더 풀고 끝내야지,,, 재미가 없다 재미가!! 이것은 N과 M(2)번과 가장 흡사하다. (2)번은 (1)번 기준으로 오름차순으로 된 수열들만 출력하는 것이었는데 (4)번은 (3)번에서 오름차순으로 이루어진 수열들만 출력하면 된다. ... 그대로 똑같은 풀이를 이용하고, 범위만 살짝 바꿔주고! s..

🟠 문제 https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🟠 나의 풀이 이전에 N과M(1), (2)번 문제와 기본적인 풀이 방식은 같다. (N과M(1) 풀이, N과 M(2)풀이) 자세한 DFS, 백트래킹의 과정을 보려면 (1)번 풀이를 보면 된다. 1번과 다른점은 바로, 중복된 값들도 허용해서 출력한다는 것이다. 이 의미는 즉, '방문처리'를 하지 않는 다는 뜻으로 해석할 수 있다. 방문처리가 되지 않은 모든 수들을 순회하면서 출력한다는 뜻!..

🟠 문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🟠 내가 푼 풀이 앞서 풀었던 N과 M(1) 과 비슷하다. [1,2]와 [2,1]을 다르게 취급햇던 (1)번 문제와는 달리 (2)번 문제는 [1,2] 하나만, 즉 오름차순으로 이루어진 답 하나만 취급해야한다. 어제 DFS관련해서 헤맸던게 나름 충격이었어서 머릿속에 몇번이고 기억하면서 넣었었다. 그래서 코드는 쉽게 짤 수 있었다. 이제 오름차순으로 이루어진 것들만 뽑아내는 것인데,,, 내..

🟠 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 🟠 내가 푼 풀이 처음에 문제를 보고 감을 잡지 못했다. 완전탐색으로 방문 여부를 탐색해서 출력해주어야하나? 고민했다. (코테스터디에서 풀었던 문젠데 전혀 기억이 나질 않았다.) 결국 어떤 알고리즘을 사용했는지 힌트를 얻고자 인터넷을 조금 찾아보았다. DFS와 백트래킹 개념을 이용하는 것으로 보였다. 문제를 풀어보면, 왜 DFS로 푸는지는 이해가 되는데, 백트래킹 개념이 들어간게 맞는지..

🟠 문제 https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 🟠 나의 풀이 아직 dp에 대한 감이 없어서 이 문제를 보고, 아 dp 문제다! 라는 생각이 들지 않았다. (이것이 가장 큰 문제다,, dp만 한번 크게 조져야하나,,,) 그래도 어쨌든,,, 아래 문제 분류에서 dp 로 분류해놓은 것을 보고 힌트를 얻었다. dp 배열 내부에, 1을 만들 수 있는 경우의 수는 dp[1]에 , 2를 만들 수 있는 경우의 수는 dp[2]에 ... 이렇게 넣을 예정이다. 규칙성을 찾기 위해서 일단 아이패드로 그려보면서 생각햇다. (에전에 알고리즘 스터디를 할때..

🟠 문제 https://www.acmicpc.net/problem/1748 1748번: 수 이어 쓰기 1 첫째 줄에 N(1 ≤ N ≤ 100,000,000)이 주어진다. www.acmicpc.net 🟠 나의 풀이 그냥 N입력을 받아서, 1부터 N까지 단순하게 for문으로 증가시켜주면서 해당 글자가 몇글자인지 판단해서 answer로 더해주려고 했다. 누구나 생각하는,, 그런 1차원적인 방식으로 그런데, 해당 문제에서 주어진 시간은 0.15초 였고, 최대로 주어질 수 있는 N은 1억이었다. 백준에서 한 연산이 돌아갈때 1억번돌아가는데 1초가 걸리기 때문에, 이렇게 풀면 무조건 시간초과가 나겠다는 판단이 섰다. 그럼 어떻게 줄일 수 있을까? 예전에 풀어본 문제들에 의하면, 자릿수를 판단할때 " % 10" 을 ..

🟠 문제 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 🟠 첫번째 풀이 - 틀렸습니다 var n = Int(readLine()!)! for _ in 0.. Int { return m == 0 ? n : gcd(m, n%m) } gcd 메서드를 만들어서 최대공약수를 먼저 구해준다음, 두 수의 곱을 최대공약수로 나눠준 것이 최소공배수가 되는 성질을 이용해서 maxYear을 구했다. 이렇게 푸니까, 시간초과가 났다. 어쨌든 나의 코드는 year에 +1..