potato's devlog

🟠 문제 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..

나는 해당 문제를 완전탐색으로 풀었다. 감히 DFS는 생각해내지도 못함,,, 완전 탐색으로 모든 모양에 대한 함수를 따로 작성하고 풀어서 코드가 무려 287줄이나 나왔다. ㅋㅋㅋㅋ(주석포함) 구현실력도 중요하지만, 오답노트는 꼭 DFS로 해보자.👊🏻 🟠 문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 🟠 나의 풀이 이것도 예전에 스터디할 때 한 번 봤던 문제다. 그래서, 모든 경우를 다 살펴봐야한다는 사실을 알고 있었다. (완전탐색(브루트..

🟠 문제 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 🟠 나의 풀이 먼저 문제가,,, 일단 골드라는 것에 덜컥 겁이 났지만,, 예전에 한번 풀어봤던 문제이기에 조금씩 기억이 났다. 알고리즘 문제 풀면서 이거 백프로 다음에 기억못함 ㅋㅋㅋ 이러고 풀지만, 은근히 기억이 난다! 우선, 위와 같은 경우에는 세가지의 방법으로 채널을 이동할 수 있다. 1. +, - 버튼으로만 완벽하게 이동 2. 숫자버튼이 고장나지 않아서, 숫자버튼으..

🟠 문제 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net 🟠 첫번째 풀이 - 틀렸습니다 보자마자, 나눠서 몫과 나머지를 이용하면 쉽게 풀리겠다! 라는 생각이었다. 그래서 생각해낸게, return 값으로 나오는 값에 각각 15, 28, 19로 나눠주면, 예제입력값이 나온다는 것이다. 그리고, 문제 조건에서 '최소'값을 찾아주면 되기 때문에, 모든 경우의수를 다 for문으로 돌려줘도 문제가 없어 보였다. 그리고 시간제한도 2초로 생각보다 길었다. 지난번..

🔖 TIL - swapAt(_ i: ,_ j: ) 배열 내부에서 두 개의 원소의 자리를 바꿔야할 때가 있다. 그럴때 물론 아래와 같은 방법으로도 변경이 가능하다. temp라는 임시 변수에 현재 위치의 값을 저장해둔 후, 바뀐 자리에 temp를 넣어주는 방법이다. var array = [1, 2, 3] for i in 0..

🔖 TIL - for 문 앞에 이름붙여서 다중포문 탈출하기! 예전에 풀면서도 공부했었던 것인데, for 루프에 이름을 붙여준 후, 다중 포문에서 '특정 포문'을 탈출 할 수 있다. for i in 0..

아아 아직도 시간초과와 싸우는중,, 지금은 '시간초과 날거같은데..'하면서 코드를 갈겨 쓰고있다. 하지만,,,,,,,, 애초에 문제 풀이 시작할때부터 시간초과에 대한 생각을하고 알고리즘을 짜는게....맞다..백번 맞다. 내가 잘못하고 있는것이다 ㅠㅠ 하나씩 해결해나가면서 시간초과의 원인을 찾아 나서면, 점차,, 익숙해지겠지..? 🟠 문제 https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 🟠 첫번째 풀이 - 역시나 시간초과 ..