백준에서 queue.PriorityQueue() 사용 시 런타임에러가 납니다.

안녕하세요, ksi2564님!(질문 등록 알람이 안 와서 좀 늦게 답변드렸네요.. 😅) BOJ 1753 최단경로 문제를 PyPy3 + PriorityQueue로 제출할 경우 런타임 에러가 발생하는 이유는,백준에서 제공하는 PyPy3 채점 환경이 queue.PriorityQueue를 정상적으로 지원하지 않기 때문입니다. PyPy3 자체는 PriorityQueue 모듈을 포함하고 있지만, 백준의 PyPy3 실행 환경에서는 PriorityQueue 내부 동작 과정에서 예외가 발생하여 프로그램이 실행 도중 종료되는 문제가 확인됩니다. 따라서 동일한 코드라도 Python3에서는 통과하지만 PyPy3에서는 런타임 에러가 발생할 수 있습니다. 이와 같은 이유로, 실제 문제 해결 시에는 heapq를 우선적으로 사용하는 방식을 추천드립니다. 추가로, 이번 기회에 알아본 내용인데 queue.PriorityQueue는 원래 멀티스레드 환경을 위한 동기화 큐로 설계되어 있어 락(lock) 처리 등 부가적인 오버헤드가 존재합니다. 반면 heapq는 가볍고 빠른 최소 힙 기반 구현으로, 문제 풀이나 코딩 테스트 환경에서 더 효율적으로 동작합니다. 강의에서는 사용법의 직관성을 위해 PriorityQueue를 예시로 들었지만, 실전에서는 말씀하신 대로 효율성을 고려하면 heapq를 기본 우선순위 큐로 사용하는 방식이 더 안정적이고 적합합니다. 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

DP 알고리즘 index 0 이유?

안녕하세요, 김가람님!DP Table을 만들 때 보통 0-index 방식 또는 1-index 방식을 사용합니다.0-index 방식: 인덱스를 0부터 사용하는 방식1-index 방식: 인덱스를 1부터 사용하는 방식 문제 설명에서 보통 '첫 번째 집', '1번부터' 처럼 1부터 시작하는 경우가 많아, 저 같은 경우에 DP Table을 만들 때 기본적으로 1-index 방식을 사용하는 걸 선호합니다.인덱스 0인 부분을 사용하지 않는 경우에도, 문제 설명과의 일치를 중요하게 생각하여 1-index를 사용하는 편입니다. (이번 문제 포함) 아마 DP 관련 강의를 이어서 수강하다 보면, DP Table을 만들 때 (0-index보다) 1-index를 기본으로 하는 게 직관적이라는 것을 느끼실 수 있을 겁니다!문제에서 설명하는 번호와 일치하게 코드 작성 가능 (즉, dp[i]는 i번째 집과 관련된 정보를 의미)초기값 처리를 하지 않을 경우에, 인덱스 0인 부분에 특정 값을 넣어 둬야 함. (아래 이미지는 BOJ 1149 자료의 관련 설명 부분을 캡처한 사진입니다)(사진) 결론적으로, 이번 문제만 봤을 때 질문자님이 말씀하신 대로 0-index 기반으로 사용하여 풀어도 무방합니다. 이후에 강의를 들어도 0-index가 편하시다면 그렇게 코드 스타일을 잡아도 무방합니다! 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

(시간 초과) 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번째 풀이 코드를 참고하시면 좋을 것 같습니다. 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄