(시간 초과) BOJ 1342 관련하여 질문이 있습니다

안녕하세요, Sung Hyun Hong님! (질문 등록 알람이 안 와서 좀 늦게 답변드렸네요.. 😅) Counter 컬렉션을 이용하면 시간 초과가 나는 이유결론부터 말씀드리면 Counter 객체에서 원소를 조회하는 연산이 Dict 객체에서 원소를 조회하는 연산보다 약간 더(1-3배 정도) 느려서 생기는 현상입니다. Counter 객체에서 원소를 조회하는 연산 또한 내부적으로는 Dict 객체로 구현되어 있지만, 잡다한 연산들(메서드를 호출하는 연산, 키를 검사하는 연산)이 추가적으로 들어가서 살짝 더 느립니다. 그리고 이러한 이유 때문에 Dict로 키를 조회하는 것보다 살짝 더 느린 것이죠. 보통 문제에서는 이러한 차이가 크게 작용하지 않지만, 이번 문제에서는 연산 횟수가 크다 보니 시간 초과 여부를 걸정할 정도로 작용한 것입니다. 정리하자면, Counter 객체에서 원소를 조회하는 연산 또한 내부적으로 Dict를 사용하지만 여러 연산이 더해져 Dict로 원소를 조회하는 것보다 살짝 더 느려 시간 초과가 나는 것입니다. 아래와 같이 Counter 객체를 Dict로 바꿔서 조회하는 방식으로만 바꿔도 통과하는 걸 알 수 있습니다.from itertools import permutations from collections import Counter s = input() def sol(lev): global s, counter, choose, ans # base case if lev == len(s): ans += 1 return # recursive case for k in chars: if counter[k] == 0: continue if (not choose) or (choose[-1] != k): counter[k] -= 1 choose.append(k) sol(lev + 1) choose.pop() counter[k] += 1 counter = Counter(s) chars = tuple(counter.keys()) counter = dict(counter) # 추가된 부분 choose = [] ans = 0 sol(0) print(ans) Python3와 PyPy3 차이점Python3와 PyPy3 모두 파이썬 컴파일러이며, 컴파일하는 방식에 차이가 있습니다. PyPy3는 Python3에 비해 메모리를 더 쓰는 대신에 효율적으로 컴파일하는 특징이 있어 똑같은 코드라도 PyPy3에서 더 빠르게 돌아가는 경향이 있습니다. 하지만 Python3보다 메모리를 더 사용하는 방식으로 작동하니 메모리 제한이 작은 문제에서는 주의해야 합니다. 이 부분 관련해서는 섹션2의 16. 🎁 백준에 파이썬 코드를 제출할 때 주의할 점를 참고하시면 도움이 될 것 같습니다. 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

BFS, DFS

안녕하세요, 석국수님!대부분의 경우 DFS로 풀 수 있는 문제는 BFS로도 풀 수 있습니다. 하지만 일반적인 그래프 탐색 문제에서는 DFS가 다음과 같은 이유로 더 선호됩니다. DFS는 그래프 탐색의 가장 기본적인 구조DFS는 “그래프를 탐색한다”는 목적을 가장 직관적으로 드러내는 알고리즘입니다. DFS로 충분히 풀리는 문제를 굳이 BFS로 구현한다면, 코드를 읽는 입장에서 “최단 거리가 중요한 상황도 아닌데 왜 BFS를 썼지?”라는 의문을 가질 수 있습니다. 따라서 특별한 이유가 없다면 기본적인 탐색은 DFS로 구현하는 것이 자연스럽습니다. BFS 대비 DFS의 메모리 효율성시간 복잡도는 DFS와 BFS 모두 O(V+E)로 동일합니다. 그러나 메모리 측면에서는 DFS가 더 유리한 경향이 있습니다. DFS는 다음 노드를 바로 탐색하는 반면, BFS는 다음 노드들을 모드 큐에 담아 놓아야 하기 때문에 메모리 사용량에서 불리한 경우가 많습니다. 응용 문제로의 확장성그래프 탐색을 응용하는 다양한 문제들은 대부분 DFS 변형으로 해결됩니다. 대표적으로 백트래킹 알고리즘이 이에 해당합니다. BFS로도 구현은 가능하지만, 탐색 경로를 전부 큐에 넣어야 하므로 경우에 따라 DFS보다 훨씬 많은 메모리를 소모할 수 있습니다. 따라서, 특별한 제약이 없다면 그래프 탐색은 DFS로 접근하는 것이 일반적입니다. 반대로 가까운 거리부터 탐색해야 하는 문제(예: 최단 거리, 최소 단계 탐색)라면 BFS가 적합합니다. 문제를 DFS와 BFS 두 가지 방식으로 모두 구현해보고 장단점을 비교하다 보면, 어느 순간 자신만의 선택 기준이 생길 것입니다. :) 추가로 궁금한 사항이 있으면 언제든 편하게 질문 남겨주세요 🙂

이중연결리스트에 관한 수업 내용도 있을까요?

안녕하세요, 재형님!아쉽지만, 말씀하신 이중 연결 리스트에 대한 별도 강의는 이번 커리큘럼에 포함되어 있지 않습니다. 본 강의는 주로 알고리즘과 문제 접근법에 초점을 두고 있어, 자료구조를 직접 구현하는 심화 내용은 다루지 않았습니다.추가로 궁금한 사항이 있으면 언제든 편하게 질문 남겨주세요 🙂

영상에서 설명이 잘못됐고 자막이 맞는 내용이라고 자막에 표기

안녕하세요, 슷파맨님!int 자료형 기준으로 1MB는 25만개의 공간이 맞습니다.영상에서 말한 것이 틀려 자막으로 추가 설명을 적어 놓은 것이라고 생각해 주시면 됩니다.(따라서, 자막에서 하는 말이 맞습니다.)(사진)int 자료형은 4Byte이므로 100만 / 4 = 25만이 맞는 것이죠. 강의 자료에 올바른 내용으로 고쳐 놓았으니 참고하시면 좋을 것 같습니다!(강의 자료 페이지 링크는 영상 설명란에 존재합니다) P.S 말씀하신대로 해당 부분은 더 잘 인지할 수 있도록 수정해 놓도록 하겠습니다!

최대값 int(1e6, 1e7, 1e8) 기준

안녕하세요, Jespy님!강의 후반부에서는 따로 최대값이나 최소값 초기화에 대한 팁이 등장하진 않지만, 최대/최소값은 나올 수 있는 값보다 더 크거나 작게만 설정하면 충분합니다. 예를 들어,최솟값을 구하는 경우에는 → int(1e9) 또는 float('inf')최댓값을 구하는 경우에는 → -int(1e9) 또는 -float('inf')이렇게 설정해두고 시작하면, 이후 로직에서 min, max를 적용할 때 문제 없이 동작합니다.정해진 규칙이 있다기보다는, 문제에서 다룰 수 있는 값의 범위를 보고, 그보다 충분히 크거나 작은 값으로 초기화하는 식으로 하면 됩니다. 몇 가지 주의할 점float('inf')는 float 타입이라서, 정수 연산 위주인 문제에서는 int(1e9)처럼 정수로 처리하는 게 더 안전합니다.1e9가 항상 충분한 값은 아닌 경우도 존재할 수 있습니다. 예를 들어 문제에서 수의 범위가 10^12까지 갈 수 있다면, 이보다 더 큰 수인 1e13과 같이 설정해야 합니다.음수가 나올 수 있는 문제에서 최솟값 = 0으로 초기화하면 최솟값이 제대로 갱신되지 않는 경우가 생길 수 있으니, 이때도 답보다 더 작은 값으로 초기화해야 합니다. 결론적으로는, 매번 문제 조건에 따라 적절한 초기값을 설정하는 게 중요하고, 이 부분은 많이 경험해보시면 자연스럽게 감을 잡을 수 있을 거예요! 🙂

섹션 3 BOJ 1342 //= 연산자 관련

안녕하세요, Sung Hyun Hong님!deno *= S.count(chr(i)) 가 아닌 deno *= fact(S.count(chr(i))) 를 하셔야 합니다.- 이 작업은 중복된 경우를 걸러주기 위한 작업이며, 이는 알파벳의 개수 S.count(chr(i))가 아닌 해당 알파벳이 자리를 바꿀 수 있는 경우의 수 fact(S.count(chr(i)))로 처리해 줘야 합니다. 따라서, 질문에 올려주신 코드를 아래와 같이 변경해 주시면 됩니다.deno = 1 for i in range(ord('a'), ord('z') + 1): deno *= fact(S.count(chr(i))) ans = int(ans/deno) 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

라이브러리 사용

안녕하세요, hgjm1022님!해당 부분은 강의를 제작하면서 고민했던 부분 중 하나인데요. 결론적으로는 아래와 같은 2가지 이유 때문에 직접 구현하는 과정을 강의에 넣었습니다.구현하는 과정을 통해 조합과 순열 알고리즘에 대해 깊게 이해할 수 있기 때문- 조합과 순열 알고리즘을 라이브러리로만 공부하는 경우에 흔히 시간 복잡도 조차 정확히 계산하지 못하는 경우가 종종 있습니다. 이런 경우를 방지하며 해당 알고리즘들이 어떻게 구현되는지 이해할 수 있도록 하기 위해 직접 구현하는 과정을 넣었습니다.조합/순열 알고리즘을 응용해야 하는 경우엔 직접 구현해야 하기 때문- 조합 또는 순열을 이용하는 문제 중에서 백트래킹 유형에 속하는 문제들은 직접 조합/순열 알고리즘을 구현하여 몇몇 부분을 고치는 작업을 해야 합니다. 따라서, 라이브러리에만 의존하는 경우에 이러한 문제를 못 푸는 것이죠. - 즉, 조합/순열의 모든 경우를 살펴보는데 중간중간에 살펴보지 않아도 되는 경우는 생략하며 탐색하는 백트래킹 구조는 직접 구현해야 합니다. (백트래킹 관련 내용은 브루트 포스 알고리즘 [문제풀이] : BOJ 1342 강의 영상을 참고하시면 됩니다.) 실제 문제를 풀 때는 어떻게 해야 할까?실제 문제를 푸실 때는 라이브러리를 사용하는 것을 권장합니다. 파이썬의 경우 조합/순열 라이브러리가 사용하기 편리하며 잘 구현되어 있기 때문에 사용하는 것이 구현의 정확성/속도 측면에서 유리합니다. (실제 강의 또한 초반 부분을 제외하면 라이브러리를 적극 활용합니다.) 다만, 라이브러리를 쓰는 경우에도 시간 복잡도는 정확히 계산할 수 있어야 합니다. 그리고, 백트래킹 관련 문제가 나오면 조합/순열을 직접 구현해야 하는 경우가 있을 수 있기 때문에 로직에 대해서 어느 정도 숙지하는 것을 추천드립니다. 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄5점 수강평을 남겨주시면 향후 더 나은 강의를 만드는 데 큰 도움이 됩니다. 🌟

2번 구현 방법 질문 있습니다.

안녕하세요, eoyeong님!말씀하신 대로 cur = -1인 경우를 따로 예외처리하는 것도 좋은 방법입니다.하지만, 저 같은 경우는 함수 내에서 cur에 대해 처리하는 것이 아닌 함수 밖에서 cur을 처리하는 방식을 선호합니다. 이와 관련한 내용은 아래에 적혀져 있습니다. 매개변수 탐색 더 잘 이용하기일단 매개변수 탐색 형식으로 구현한 경우에 (숫자 K에 대해) 함수의 의미는 "배열의 원소 중에서 K인 값을 찾는다" 라는 의미보단 "배열의 원소 중에서 K보다 작거나 같은 가장 오른쪽 인덱스를 반환한다"라는 의미로 받아들이는 것이 좋습니다.따라서, 저 같은 경우는 매개 변수 탐색 방법을 이용한다면, 예외처리 없이 cur을 반환하게 한 후에 cur을 처리하는 방식을 많이 사용합니다. (아래의 코드 참조)def get_idx(arr, num): # arr[idx] ≤ num인 가장 큰 idx를 반환 cur = -1 step = len(arr) while step != 0: while (cur + step 위의 예시 코드에서 각 케이스 별로 뜻을 적어 놓았습니다. 함수의 의미가 "배열의 원소 중에서 K보다 작거나 같은 가장 오른쪽 인덱스를 반환한다"라는 점을 인지한다면 각 케이스마다 적어 놓은 의미가 당연하다는 생각이 드실 겁니다. 이를 활용하여 문제에 적용하는 더 디테일한 내용이 궁금하시면, 이분 탐색 알고리즘 [문제풀이] : BOJ 3020 강의의 2번째 풀이 코드를 참고하시면 좋을 것 같습니다. 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

브루트 포스 풀이

안녕하세요, eoyeong님!강의를 열심히 듣고 있는 것 같아 보기 좋습니다!특히, 브루트 포스 관련 문제가 아니더라도, 브루트 포스 풀이를 직접 구현해 보는 것은 매우 좋은 학습 방식이라고 생각합니다. 왜냐하면 브루트 포스 접근은 문제 해결 능력을 키우는 가장 기본적인 사고 과정이며, 이를 구현까지 해보는 과정은 자연스럽게 브루트 포스 문제를 푸는 실전 연습으로도 이어지기 때문입니다. 말씀해 주신 것처럼, 브루트 포스 풀이가 시간 초과로 인해 정답 여부를 확인하기 어려울 때가 많고, 인터넷에서도 찾기 힘든 경우도 많습니다. 저도 그러한 점을 고려하여, 강의에 나오는 브루트 포스 풀이 관련해서 코드를 업로드하는 쪽으로 검토해 보겠습니다! 다만 업로드하기까지 시간이 걸리므로, 구현한 브루트 포스 풀이가 맞는지 확인하는 법에 대해 알려드리겠습니다. 제출한 코드가 통과하려면 정확성과 효율성을 통과해야 하는데요. 강의에서 브루트 포스 접근을 하지만 코드를 제공하지 않는 경우엔 정확성은 맞으나 효율성을 통과하지 못하는 경우에 해당합니다.따라서, 백준에 제출하여 시간 초과가 뜬다면 해당 브루트 포스 풀이는 정확성은 맞은 것이니 올바르게 구현했다고 생각할 수 있습니다. 하지만 만약에 틀렸습니다.가 뜬다면 정확성이 틀린 것이니 풀이 코드를 수정할 필요가 있겠습니다!사실, 시간 초과는 보통 정확성은 맞되 효율성이 부족하다는 의미지만, 작은 입력조차 제대로 처리 못하고 오래 걸리는 코드라면 정확성조차 보장되지 않는 코드일 수 있습니다. 따라서, 시간 초과가 뜬다면 작은 입력에 대해서는 답이 빠르게(연산량이 1억 번 연산 이하 정도로) 나오는지 확인해 볼 필요가 있습니다. 문제 접근과 브루트 포스 관련 풀이 구현에 도움이 될만한 내용들문제 접근과 브루트 포스 구현에 대해 더 깊이 이해하고 싶다면, 섹션 7의 문제를 푸는 사고과정 (‘실전 문제풀이 2’ 파트 소개) 영상과 자료를 참고해 보시는 걸 추천드립니다. 특히 해당 영상의 09:14부분에 브루트 포스와 관련된 사고방식을 정리해둔 내용이 있으니, 이 부분을 집중해서 보시면 문제 접근법과 구현에 많은 도움이 될 거라고 생각이 듭니다! 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

다익스트라 음수 간선

안녕하세요 ,xk130님!다익스트라 알고리즘에서 의문을 가질만한 점을 잘 짚어주신 것 같습니다. 강의의 예시 코드는 다익스트라 코드를 좀 더 간략하게 표현한 것이며, 사실은 아래의 코드와 같이 # 추가된 부분을 적어 주는 것이 정석적인 코드입니다. 아래의 코드에서는 음수 간선이 존재하는 경우에 다익스트라를 쓰지 못하는 이유가 이해가실 거라고 생각합니다. 편의상 강의의 예시 코드를 A, 아래의 정석적인 코드를 B라고 부르겠습니다.while not pq.empty(): # pq.queue cur_dist, cur_node = pq.get() if cur_dist > dist[cur_node]: # 추가된 부분 continue for adj_node, adj_dist in adj_list[cur_node]: temp_dist = cur_dist + adj_dist if temp_dist 음수 간선이 존재하지 않는 경우에 #추가된 부분을 작성하지 않은 A코드에서도 다익스트라 알고리즘이 잘 돌아갑니다. 이유: 첫 방문이 아닌 경우에 B코드에서는 cur_dist > dist[cur_node]으로 바로 걸러지지만, A코드에서는 아래의 for문을 돌며 인접한 간선을 둘러보는 작업을 하기 때문에 약간의 연산이 더 걸리게 됩니다. (하지만, for문만 수행할 뿐 최단 heap에 경로의 후보를 넣는 일은 발생하지 않습니다.) 즉, A코드는 B코드보다 상수배 정도 비효율적인 알고리즘이라고 생각하시면 됩니다. A코드와 B코드 모두 잘 돌아가며 시간 복잡도에서도 별 차이가 없지만, A코드는 다익스트라 알고리즘을 이해하기에 헷갈림을 유발할 수 있을 거 같아, B코드로 강의 자료를 업데이트하였습니다. 강의의 예시 코드 A는 음수 간선이 존재할 때 잘 돌아갈까?이제 강의의 예시 코드 A에서는 음수 간선이 존재하는 경우에 제대로 동작하는지 생각해 봅시다.결론부터 말씀드리자면, 쓸 수는 있으나 시간 복잡도가 굉장히 크게 나올 수 있습니다. (즉, 이러한 경우에는 벨만-포드나 플로이드-워셜 알고리즘을 쓰는 게 더 나은 것이죠.) 시간 복잡도가 크게 나오는 이유는 다익스트라 알고리즘에서 어떤 노드가 최단 거리로 확정되는 순간은 그 노드가 heap에서 나오는 시점입니다. 하지만, 음수 간선이 존재한다면 이러한 전제가 틀리게 되는데요.즉, 음수 간선이 존재하는 경우의 A코드(강의의 예시 코드를 의미)는 어떤 노드가 heap에서 나오더라도 그 노드까지의 다른 최단 경로가 존재할 수 있습니다. 이러한 이유 때문에 각 노드의 방문은 최단 거리로써의 방문이 1번이 아닌 여러 번을 할 수 있게 되므로 시간 복잡도가 굉장히 커지게 됩니다. 사실, A코드가 B코드에 비해 상수배 느린지에 대한 증명, A코드가 음수 간선이 존재할 때 잘 돌아간다는 타당성, 음수 간선이 존재할 때 A코드의 최악의 시간 복잡도 등에 대해 정확히 짚고 넘어가는 것이 맞지만 답변이 너무 길어질 거 같아 간단하게 답변을 드렸습니다. 위의 내용이 정확히 이해가지 않더라도 정석적인 코드B가 잘 돌아간다는 정도만 이해하고 넘어가셔도 될 것 같습니다! 혹시 제가 설명한 부분에 대해서 더 자세히 알고 싶으시다면, 추가 질문 주시면 감사하겠습니다!더 자세한 동작 과정과 증명에 대한 디테일한 내용을 알려드리겠습니다 :)