런타임 에러: 메모리

안녕하세요. 타이거님! 공유주신 코드는 잘 짜셨으나, n이 0인 경우를 고려하지 않으셨습니다. 다음과 같이 n이 0인 경우를 처리하는 조건을 추가해주시면 정답 처리 됩니다. import sys input1 = int(sys.stdin.readline()) def fibo(n, n_1, n_2): if n == 0: return n_2 if n == 1: return n_1 else: return fibo(n-1, n_1+n_2, n_1) result = fibo(input1, 1, 0) print(result) 또 궁금하신 점 있으시면 언제든 질문 부탁드립니다. 감사합니다. :)

조합과 순열 개념

안녕하세요. Taejin Kim님! 조합과 순열 알고리즘은 개념과 구현 모두 중요하다고 할 수 있습니다. [개념적인 부분] 문제의 풀이를 떠올리는 데에 있어서 조합과 순열의 개념적인 부분이 필요합니다. 모든 경우를 살펴보며 답을 구하는 브루트포스를 이용한 풀이를 활용할 때 많이 쓰이는데요. 모든 경우를 살펴보는 과정이 조합의 모든 경우 또는 순열의 모든 경우를 살펴보는 형태로 많이 나오기 때문에 이러한 경우에 조합과 순열의 개념적인 부분을 통해서 문제의 풀이를 설계할 수 있습니다. 조합과 순열의 개념적인 부분이라는 것은 조합과 순열의 정의 및 공식 , 조합과 순열의 차이에 대해 인지하는 것 , 문제에서 제시하는 상황을 조합(또는 순열)으로 해석하는 것 등을 의미합니다. [구현적인 부분] 구현적인 부분은 조합과 순열 알고리즘을 코드로 구현하는 과정을 의미하는데요. 풀이가 모든 경우의 수를 살펴보며 답을 구하는 풀이이고 그 형태가 조합이나 순열의 형태를 띤다면, 이때 조합 알고리즘(조합의 모든 경우를 살펴보는 코드)이나 순열 알고리즘(순열의 모든 경우의 수를 살펴보는 코드)을 구현하여 코드를 짤 수 있어야 합니다. 정리하면, 모든 경우를 살펴보며 답을 구하는 경우에 그리고 그 형태가 조합이나 순열의 형태를 띤다면 조합 알고리즘이나 순열 알고리즘을 이용해서 해당 문제를 풀 수 있습니다. 참고로, 조합 이나 순열 과 마찬가지로 모든 경우를 살펴볼 때 자주 쓰이는 개념/알고리즘으로 부분 수열 과 중복 조합 등이 있으며, 이러한 내용 또한 강의 중간중간에 모두 담겨 있습니다. 또 궁금하신 점 있으시면 언제든 질문 부탁드립니다. 감사합니다. :)

1912번 DP테이블 N에서 끝나는, N까지 살펴 봤을 때 질문입니다.

안녕하세요. lee님! Q. DP 테이블을 생성할 때, N에서 끝나는 , N까지 살펴봤을 때 로 보통 접근한다고 하셨는데, 모든 DP풀이에 해봄직한 생각이라고 보면 될까요? A. 그렇게 해도 될 거 같습니다! - DP는 재귀적인 구조를 찾고, 중복된 계산을 줄임으로써 효율적으로 답을 구할 수 있는 알고리즘입니다. 재귀적인 구조는 N일 때 를 이전에 구한 값들 (보통 N-1, N-2, ..., 1일 때의 값들 을 의미)을 통해서 구하는 구조 등을 의미합니다. 따라서, DP Table은 N일 때의 어떠한 정보를 담고 있는 값이며, 보통 N까지 살펴봤을 때 , 또는 N까지 살펴봤을 때 라는 의미로 많이 쓰이는 경향이 있습니다. Q. knapsack 같은 DP세우는게 쉽지 않던데, 어려운 DP문제들은 어떤 부분을 주목해서 DP테이블을 세우려고 집중하면 될까요? A. DP Table을 세울 때는 문제에서 주어지는 변수들 (knapsack 문제의 경우는 N, K, V에 해당)과 문제에서 무엇을 구해야 하는지 를 기준으로 세우면 됩니다. - knapsack 문제를 예로 들어 설명하겠습니다. knapsack 문제에서 변수는 N, K, V에 해당 하며, 구해야 하는 것은 물건들의 가치합의 최대값 입니다. - 구해야 하는 것이 가치합의 최대값이므로 DP Table이 몇 차원으로 만들어야 할지는 아직 모르겠지만 담고 있는 의미가 ~ 가치합의 최대값 으로 하면 좋겠다는 생각은 할 수 있을 것입니다. - 그리고 3개의 변수로 DP Table의 구조를 결정하면 되는데요. N은 물건들, K는 무게, V는 가치를 의미 하는 변수입니다. 우리가 구해야 하는 것은 가치합(변수 V에 대응하는 정보)의 최대값이므로 DP Table의 의미 dp[] 를 가치에 대한 정보 로 지으면 좋지 않을까라는 생각을 할 수 있을 것입니다. 즉, 물건들(변수 N에 대응하는 정보)과 무게(변수 K에 대응하는 정보)에 따른 가치(변수 V에 대응하는 정보)를 구하는 형식으로 설계를 하는 것이죠. - 그러면, dp[n][k] 는 n과 k에 따른 가치합의 최대값 이라는 느낌으로 DP Table을 정의할 수 있으며, 좀 더 구체적으로 n은 물건들의 개수, k는 무게들의 합과 관련된 정보 이므로, dp[n][k] 를 물건들을 n까지 살펴보고 무게의 합이 k이하 일 때 가치합의 최대값 으로 세우면 되지 않을까라는 생각을 할 수 있습니다. 이렇게 세우면 답은 DP Table의 정의 따라서 DP[N][K]를 출력 하면 됩니다. - 이렇게 DP Table의 구조와 정의를 내렸다면, DP Table 전체를 완성하기 위한 재귀적인 구조(관계식)를 찾아야 합니다. 관계식을 찾을 때의 팁은 이전 것들이 다 구해져 있다고 생각하고 현재를 어떻게 구할 수 있을지 생각 하는 것입니다. 즉, 파란색 지점인 dp[n][k] 를 구할 때 노란색 부분은 이미 다 구해져 있다고 생각하는 것입니다. (사진) 위와 같은 사고과정을 통해서 DP Table을 답을 구할 수 있게 설계할 수 있으며, 관계식 또한 찾을 수 있는 것입니다. 처음에는 이러한 과정이 어색하고 어려운 것이 자연스러운 현상이며 계속 반복하면서 익숙해지면 점차 DP Table을 설계하는 것이 쉬워질 것입니다! 보통, DP Table을 정의할 때는 문제에서 주어진 직접적인 변수들을 통해서 만들면 되지만 가끔 그러한 변수를 스스로 찾아야 하는 경우가 있습니다! ( BOJ 7579 강의를 참고) 하지만, 그러한 경우는 많지 않으므로 기본적인 마인드는 문제에서 주어진 직접적인 변수들을 통해서 DP Table을 세워보는 것 을 추천합니다. 또 궁금하신 점 있으시면 언제든 질문 부탁드립니다. 감사합니다. :)

방법론 질문 있습니다

안녕하세요. zhu님! 모든 문제에 일관되게 적용되는 구체적인 사고과정이나 방법론은 존재하지 않는다는 점을 미리 말씀드리고 싶습니다. 그래서 어려운 코딩테스트 문제를 푸는 것이 쉽지 않은 것은 당연하다고 할 수 있습니다. 실제로, 코딩테스트를 통과하는 대부분의 사람들도 만점으로 통과하는 것은 아니듯이, 코딩테스트에서 어려운 문제의 풀이는 바로 떠올려지는 것이 아닌 기존에 공부했던 지식(알고리즘) 과 공부하며 쌓아온 논리적인 사고력(문제해결능력) 을 통해서 30분에서 1시간 정도의 고민의 과정을 거쳐 풀이를 떠올린다고 생각하시면 됩니다. 그래서 골드 정도의 문제를 풀 때 풀이가 바로바로 떠오르지 않는다는 것은 코딩테스트 공부을 하는 과정에 있어서 매우 자연스러운 상황이라고 말씀드리고 싶습니다. 물론, 처음부터 잘하는 분들도 존재하나, 그런 분들은 수학적인 사고과정이나 논리적인 사고과정, 컴퓨팅적인 사고과정을 원래 잘했을 가능성이 높습니다. [문제의 풀이를 떠올리는 데 필요한 것들] 코딩테스트 문제를 풀기 위해선 '알고리즘 개념', '구현력', '문제해결능력'이라고 강의에서 설명드렸는데요. ( 코딩테스트 공부의 상한선 강의 참조) 이 중에서, 문제의 풀이를 떠올릴 때는 문제해결능력 이 중요하다고 할 수 있습니다. 이러한 문제해결능력을 높이는 데에 있어서는 브루트포스, 그리디, DP 알고리즘을 이용한 접근 을 많이 연습해보는 것이 도움이 될 수 있습니다. 질문자님처럼 문제를 보고 어떻게 접근해야 할지 감이 안잡하시는 분들 은 이 3가지 알고리즘을 통해 문제를 접근하시는 것이 도움이 될 것입니다. 이 3가지 알고리즘을 이용하여 문제를 접근하는 것을 계속 연습하다보면, 문제를 논리적으로(컴퓨팅적으로) 접근하는 과정이 익숙해질 것입니다. 보통 코딩테스트를 어려워 하시는 분들은 논리적이지(컴퓨팅적이지) 않은 사고과정이 습관처런 몸에 베어있는 경우가 많은데요. 이런 분들은 문제를 보고 무의식적으로 나오는 논리적이지(컴퓨팅적이지) 않은 사고과정을 인지하고 바꿔주는 것이 중요합니다. 따라서 위에서 언급한 브루트포스, 그리디, DP 알고리즘을 이용한 접근을 많이 연습하여 논리적인(컴퓨팅적인) 사고과정을 체화하는 것이 중요하다고 말할 수 있습니다. 위에서 언급한 브루트포스, 그리디, DP 알고리즘을 이용한 접근 은 필수 알고리즘1 파트와 실전 문제풀이1 파트를 참고하시면 도움이 많이 될 거라고 생각합니다. 더불어 실전 문제풀이2 파트를 통해 실제 코딩테스트 문제를 풀 때 어떻게 접근하여 풀이를 떠올리는지 보시면 좋을 거 같습니다. [정리] 문제의 풀이를 떠올리는 데는 논리적인(컴퓨팅적인) 사고과정이 중요 대부분의 사람들은 논리적이지 않은 방식으로(느낌적으로) 문제를 접근 논리적인(컴퓨팅적인) 방식으로 문제를 접근하고 푸는 것을 체화할 필요가 있음. 논리적인(컴퓨팅적인) 사고과정은 (강의에 나오는) 브루트포스, 그리디, DP 알고리즘을 이용하여 접근하는 과정을 통해 키울 수 있음. [추가적으로] 질문자님께서 언급한 구체성 있게 따져보는 방법 은 아마 DP Table을 세우고 관계식의 타당성을 판단하는 방법 에 대한 질문인 거 같은데요. 자신이 세운 DP 관계식의 타당성을 판단하는 법은 DP Table의 정의에 따른 관계식이 오류가 없다면 DP 관계식이 타당하다고 할 수 있습니다! 예를 들어, dp[n] 을 n까지 살펴봤을 때의 최대 길이 라고 정의하고 dp[n] 을 구하기 위한 관계식을 찾아 봤더니 dp[n] = dp[n - 1] + dp[n - 2] 라는 관계식이 있는 거 같고 실제로 확인해봐도 DP Table 정의인 dp[n]: n까지 살펴봤을 때의 최대 길이 라는 것이 맞는 거 같다면 타당하다고 할 수 있습니다. 이렇게 말해도 사실, DP 관계식의 타당성을 판단하려면 어느정도의 사고력이 필요하므로 처음엔 어려운 것이 당연합니다. 따라서, DP 문제들의 풀이 영상들을 보며 DP 관계식의 식이 왜 타당한지를 스스로 코드를 돌려보며 이해하는 과정을 해보시는 것을 추천 드립니다. 그렇게 하다 보면, 이후에는 스스로 DP Table을 설계하고 타당한 DP 괸계식 또한 쉽게 찾을 수 있을 것입니다! 또 궁금하신 점 있으시면 언제든 질문 부탁드립니다. 감사합니다. :)

2110번 문제 ispossible 함수 내부에서 조건문이 궁금합니다

안녕하세요. kje010907님! 공유해주신 코드 모두 채점 결과 정답처리 되는걸로 확인됐습니다. 질문에 남겨주신 말씀대로 두 코드의 차이점은 isPossble 부분인데, 그 중에서도 if(cnt==C) return true; 와 return C 의 차이라 볼 수 있습니다. 여기서 cnt==C 에 도달하지 못한다면 C보다 적은 개수만 설치할 수 있으니 false를 리턴 한다는 점에서 두 코드의 논리는 동일하다고 볼 수 있습니다. 다시 한 번 채점해보시고, 여전히 오답으로 뜨거나 궁금하신점 있으시면 추가 질문 남겨주세요. 감사합니다. :)