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가 잘 돌아간다는 정도만 이해하고 넘어가셔도 될 것 같습니다! 혹시 제가 설명한 부분에 대해서 더 자세히 알고 싶으시다면, 추가 질문 주시면 감사하겠습니다!더 자세한 동작 과정과 증명에 대한 디테일한 내용을 알려드리겠습니다 :)

종료 조건

안녕하세요 ,xk130님!강의 막바지를 달리고 계시다니 훌륭합니다! 😊 질문에 대한 내용은 강의의 06:22 부분에서 설명한 내용과 관련이 있는 것 같습니다.강의에서 나온 그림은 queue의 원소들이 한 번에 빠져나가서 다른 queue로 들어가는 것처럼 보여 오해가 생기신 거 같습니다. 하지만, 해당 그림은 "queue의 원소들이 한 번에 빠져나간다" 라는 의미를 담는 것이 아닌 "원래 상태로 돌아오기까지 4n번의 횟수가 걸린다" 라는 의미를 전달하기 위한 그림이라고 생각해 주시면 좋을 것 같습니다. 실제로는 queue의 원소들이 한 번에 빠져나가는 것이 아닌 queue1과 queue2가 번갈아가면서 빠져나가기 때문에, 어떠한 queue가 비어있는 상태는 나오기 힘든 것이죠.쉽게 생각하면, queue1과 queue2의 합을 동일하게 하도록 알고리즘이 동작하는데, 어느 한 쪽 queue가 빈다면 값 차이가 엄청 큰 것이므로 이 자체가 이상한 상황일 것입니다. 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

BOJ 1342 메모리초과 관련

안녕하세요, gjwns2044님!메모리 초과가 나는 이유는 이 질문글(링크)을 참고해주시면 좋을 것 같습니다. 크기가 n인 리스트에 대해, permutations를 사용해도 어차피 n!만큼의 원소들을 담고 있는 객체를 생성하므로 메모리적인 측면에서 set으로 둘러싼 것과 큰 차이가 없지 않나요?이에 대한 답은 no입니다. 파이썬의 permutations 함수는 모든 순열을 한꺼번에 저장하지 않고, 필요할 때마다 하나씩 생성하는 제너레이터(generator)입니다.재너레이너(generator)란 한 번에 모든 데이터를 메모리에 저장하지 않고, 필요할 때마다 값을 생성해서 반환하는 함수 또는 객체입니다. 따라서, 이러한 방식을 이용하면 메모리를 효율적으로 사용할 수 있습니다.아래와 같은 형식으로 permutations 객체를 생성하면, next 함수를 통해서 다음의 원소를 접근하여 메모리 효율적으로 모든 순열의 원소를 살펴볼 수 있는 것입니다. (이러한 permuations를 for문에 이용해도 이와 같이 메모리 효율적으로 돌아가게 됩니다.)from itertools import permutations data = [1, 2, 3] perm_gen = permutations(data, 2) # 제너레이터 객체 생성 print(next(perm_gen)) # (1, 2) → 첫 번째 순열을 생성 print(next(perm_gen)) # (1, 3) → 두 번째 순열을 생성 print(next(perm_gen)) # (2, 1) → 세 번째 순열을 생성이러한 방식을 lazy evaluation(지연 평가)라고 하므로 참고하시면 좋을 것 같습니다. 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

진짜 엄청나네요. 이 가격에 새로운 컨텐츠 추가라니

안녕하세요, rhkdtjd_12님!좋게 봐주셔서 정말 감사합니다! 코딩테스트 A to Z라는 제목에 걸맞게, 처음부터 끝까지 체계적으로 학습할 수 있도록 강의를 만들기 위해 노력하고 있습니다. 계속 반복해서 공부하시면서 궁금한 점이 생기면 언제든 편하게 질문 남겨주세요. 앞으로도 더 좋은 강의가 될 수 있도록 꾸준히 업데이트해 나가겠습니다. 열심히 공부하셔서 원하는 목표 꼭 이루시길 응원하겠습니다! 화이팅! 💪🔥

섹션3 브루트포스 알고리즘 1342 풀이1 질문

안녕하세요, kimgguggury1002님!인접한 문자가 같은 지 아닌 지를 구하는 부분은 아래의 코드입니다.for perm in permutations(S): ok = True for i in range(0, len(S) - 1): if perm[i] == perm[i + 1]: ok = False break ans += ok 위의 과정을 거치면 ans는 중복된 문자열을 고려하지 않고 문제의 조건을 만족하는 문자열의 개수가 담겨 있습니다. 중복된 문자열을 고려하지 않고 경우의 수를 구했으니 중복된 문자열을 고려해야 하며, 이를 처리하는 부분이 질문자님께서 올려주신 코드 부분입니다. 중복된 문자열을 고려하여 처리하는 방법은 같은 것이 있는 순열의 개념을 이용하면 되며, 이러한 내용은 해당 강의의 2:10 - 4:02 부분에서 설명하고 있으니 참고하시면 될 것 같습니다! 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

boj 3020

안녕하세요, tocc22님! AttributeError 런타임에러가 나는 이유input은 함수이므로, 재설정할 때 input = lambda: sys.stdin.readline().rstrip() 와 같이 작성해주셔야 합니다. 이를 바꾸면 런타임 에러는 해결이 될 것입니다. 이렇게 풀면 메모리나 시간초과가 날까요?코드를 자세히 살펴 보았는데요, 해당 코드는 정확도 측면에서는 맞는 풀이라고 생각이 듭니다. 하지만, 효율성이나 메모리 측면에서는 좀 문제가 있어 보입니다. 이에 대해 제가 바로 설명을 해드릴 수도 있으나, 한 번 tocc22님이 풀이 코드에 대해 시간 복잡도와 사용하는 메모리를 계산해 보시는 것을 추천드립니다! 시간 복잡도와 사용하는 메모리 계산을 해서 나온 결과와 과정을 답글로 작성해 주시면, 제가 더 자세하게 답변을 드리겠습니다! 물고기를 잡아주는 것이 아닌 잡는 법을 알려드리는 과정이라고 좋게 생각해주시면 감사하겠습니다 :)

제가 공부하는 방법이 괜찮은지 궁금합니다

안녕하세요, 말랑말랑한 캥거루님! Q1. 원래 자바로 공부하다가 파이썬이 코테에 유리하다는 것을 느끼고 바꿨더니 문법 문제가 생김A) 파이썬 문법 같은 경우는 강의와 강의 자료 중간중간에 문법 팁이나 원리에 대해 설명하고 있습니다. 그럼에도, 모르는 부분이 자주 나온다면 간단한 파이썬 문법 강의(링크) 등을 듣고 강의를 수강하면 도움이 될 것 같습니다. 추가로, GPT를 이용하여 그때그때 모르는 부분을 빠르게 찾는 것도 도움이 될 것 같습니다. Q2. 문제를 풀 때 그때그때 문법 검색해 보고 블로그에 정리하는 식으로 공부할지 or 그냥 파이썬 문법 강의까지만 듣고 올지A) Q1과 비슷한 맥락으로, 문법은 기본적인 강의(링크) 등을 듣고 강의를 들으시면 도움이 될 것 같습니다. 추가로, 문법을 블로그나 개인 공간에 정리한다면 사용법 정도만 매우 간단하게 정리하는 것을 추천드립니다. 문법은 암기하는 것보다는 까먹었을 때마다 찾아보며 자연스럽게 익숙해지는 것이 좋기 때문입니다. 사실, 아예 정리를 하지 않고, 문법이나 사용법을 까먹었을 때마다 GPT에게 물어보며 반복하여 상기하는 정도만 해도 괜찮다고 생각이 듭니다. Q3. 실버 문제가 아직 설계부터 어렵고, 수학 문제가 나오면 어버버거리는데, 이걸 문제를 다 못 풀어 봤어도 혼자 30분 정도 접근해 보고, gpt에 물어봐서 나의 문제점을 이해하고 문제 풀이 강의를 듣는 식으로 해도 되는 건지?A) 만약, 문제를 풀 때 못 푼 이유가 몰랐던 개념이나 테크닉 때문인 경우가 잦다면, 이는 관련된 개념이나 테크닉 등 경험이 부족하여 그럴 확률이 높습니다. 즉, 정답과 해설을 보며 개념과 테크닉 등을 빠르게 습득하여 경험치를 늘리는 것이 도움이 됩니다. 따라서, 문제를 고민하는 시간은 최대 30분 정도로 잡고 문제의 정답 풀이(또는 해설 강의)를 보며 경험치를 빠르게 늘리며 공부하는 것이 효율적일 것입니다.만약, 못 푼 문제의 해설을 봤는데 알았던 알고리즘이라면, 이는 문제해결능력(문제를 올바르게 접근하는 능력)이 부족하여 그럴 확률이 높습니다. 따라서, 이러한 경우는 문제를 깊게 고민해 보며 문제해결능력을 늘리는 것이 도움이 되므로 최대 1시간 정도 고민하면 여러 접근을 해보는 좋을 것 같습니다.사실, 문제를 고민하는 시간 자체도 중요하지만, 밀도 있게 고민하는 것이 더욱 중요합니다. 즉, 10분을 고민하더라도 문제를 어떻게 풀 수 있을지, 시간 복잡도를 줄일 방법은 없는지, 내 풀이 논리에 오류는 없는지, 해당 문제가 어떤 알고리즘으로 풀리는 구조인지 등을 다각적으로 생각하며 풀어야 합니다.알고리즘 문제를 잘 푸는 사람들은 단번에 정답을 떠올리는 것이 아니라, 짧은 시간 안에 다양한 사고 과정을 거쳐 최적의 풀이를 도출합니다. 따라서, 위와 같은 사고 과정을 반복적으로 훈련하는 것이 중요합니다. 본 강의의 해설 강의에서는 문제 접근부터 다양한 풀이를 떠올리는 과정을 잘 다루고 있으니, 위와 같이 다각적으로 접근한 후에 해설 강의를 보며 나의 사고 과정을 계속 고쳐 나가면 좋을 것 같습니다. 추가적으로, GPT를 사용하여 여러 질문을 하며 문제점을 파악하는 것은 좋은 것 같습니다. 저 또한 공부를 할 때 제가 이해한 것이 맞는지 GPT를 통해 물어보고, 반론해 가며 공부하고 있으니, 이와 같이 활용하면 공부를 할 때 더 깊은 이해를 가져갈 수 있을 것 같습니다. 수학 문제가 나올 때 어려운 이유가, 몰랐던 수학 개념이 나와서 그러는지, 아니면 수학적인 사고력이 부족한 것인지를 파악할 필요가 있습니다. 만약, 몰랐던 수학 개념이 나와서 그렇다면, 수학적인 개념을 공부할 필요가 있으며, 본 강의의 코딩테스트에 필요한 수학 총정리에 나오는 내용을 충분히 공부하는 것을 추천드립니다. 만약, 수학적인 개념은 알고 있으나 사고력이 부족해서 못 풀었다면, 문제해결능력을 늘리면 자연스럽게 해결될 문제라고 생각합니다. 문제해결능력을 늘리는 방법은 위에서 설명한 것처럼 밀도 있게 고민하는 시간을 가지며 공부하면 자연스럽게 늘 거라고 생각합니다. Q4. 브론즈 같은 경우엔 일단 풀이가 깔끔하지 않더라도, 문제가 풀려서 풀고 강의를 들으면 됐었는데, 실버 문제로 오니까 아예 설계부터 못하는 것 같아서 공부를 어떻게 해야 하는 건지 모르겠음A) 어떻게 공부해야 할지는 Q3에 대한 답변에서 다룬 거 같으니, 해당 내용을 참고해 주시면 감사하겠습니다! 추가로, 문제를 풀 때 어떻게 접근해야 하는지는 섹션7의 문제를 푸는 사고과정 ('실전문제 풀이 파트2' 소개) 강의에 자세히 나와 있으니 참고하면 좋을 것 같습니다. (해당 강의는 앞 강의의 내용들이 선행되었다는 가정하에 제작한 영상이어서 모르는 개념이나 내용이 나올 수 있으니, 흐름 정도만 참고하면 좋을 것 같습니다.) 추가로, 강의는 한 번만 듣지 말고 2, 3회독 하는 것을 추천드립니다! 질문에 대해 만족스러운 답변이 되었기를 바랍니다!추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄5점 수강평을 남겨주시면 향후 더 나은 강의를 만드는 데 큰 도움이 됩니다. 🌟

강의 내용 중 백트래킹 존재 여부

안녕하세요, hsk7953님!백트레킹 알고리즘 또한 강의에 포함되어 있습니다. 백트레킹은 브루트포스 알고리즘 부분에서 포함되어 있으며, 구체적으로는 브루트 포스 알고리즘 [문제풀이] : BOJ 1342, BOJ 2580 등에서 백트레킹 관련하여 다루고 있습니다. 백트레킹은 브루트 포스 알고리즘과 연계해서 학습하면 좋은 알고리즘이라 따로 분리하지 않고 이와 같이 제작하였습니다. ㅎㅎ 또 궁금하신 점 있으시면 문의해주세요 :)