potato's devlog

🟠 문제 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 🟠 나의 풀이 문제를 같은 부류끼리 모아 풀어서 그런가, 확실히 문제를 보고 어떻게 풀지 딱 떠올랐다. 예전에는 안그랫는데,,, 역시 한 분야만 죽어라 파고, 그 분야에 익숙해질때까지 문제들을 눈에 넣는게 중요한것 같다. 일단, 이 문제의 핵심은 다음과 같다. 오름차순으로 출력되어야하기 때문에, 오름 차순으로 정렬된 배열을 이용해야하고, 앞에 지나왔던 배열요소들은 보지 않도록 만들어주어야한다...

🟠 문제 https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net 🟠 내가 푼 풀이 처음 보고 완전 참색에 DFS를 사용하면 되겠구나! 까지는 생각이 났다. (이전에 반복해서 푼 N과 M문제 덕분..)... 근데,,, 이제 그 후에 어떻게 해야할것인지 고민이 필요했다. 문제를 요약하면 다음과 같다. 2차원 배열을 입력받는다 (세로 N 가로 M) 배열 내부에서 K개의 숫자를 뽑아서 합을구할 건데, 그 합이 최대가 되어야 한다. K개를 뽑을때 인..

🟠 문제 https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 🟠 나의 풀이 중복을 허용해줘야하기 때문에 if !stack.contains 부분을 빼서 방문확인을 안해주었고, 해당 수보다는 작거나 큰 수가 옆에 올 수 있기 때문에 매개변수로 현재 방문하고 있는 i 값을 넘겨주었다. 똑같은 문제는 N과 M(4)번! https://didu-story.tistory.com/375 [백준] (Swift) 15651번 - N과 M(4) (feat. ..

🟠 문제 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로 푸는지는 이해가 되는데, 백트래킹 개념이 들어간게 맞는지..