섹션4. 3주차 Stack 백준 2493

안녕하세요 zz gg 님 좋은 질문 감사드립니다! 해당 문제 풀이의 경우 말씀해주신대로 시간 초과가 발생하고 있습니다! 해당 코드는 코드는 스택의 기본 개념을 이해하기 위한 학습용 구현이었기 때문에 그렇습니다. 실제로 이 코드는 O(N²) 시간 복잡도를 가져서 큰 입력값에서는 시간 초과가 발생할 수 있습니다! 따라서, 시간 복잡도를 개선하려면 다음과 같이 스택을 좀 더 효율적으로 활용할 수 있습니다def get_receiver_top_orders(heights): stack = [] # [인덱스, 높이]를 저장 answer = [0] * len(heights) for i in range(len(heights)): while stack and stack[-1][1] 이 방식의 핵심 아이디어는 다음과 같습니다.스택에 [인덱스, 높이]를 함께 저장하여 나중에 다시 순회할 필요를 없애기현재 탑보다 작은 탑들은 스택에서 모두 제거 (어차피 앞으로도 쓸모없음)남아있는 스택의 top이 수신 가능한 가장 가까운 탑이렇게 하면 각 탑이 최대 한 번씩만 스택에 들어갔다 나오므로 O(N) 시간 복잡도로 문제를 해결할 수 있습니다. 이에 대한 풀이 방법은 추가적으로 문서에 서술해두도록 하겠습니다! 좋은 아이디어 주셔서 감사합니다 🙇

1-5 알고리즘과 친해지기 (2)

안녕하세요 수빈님!! 좋은 질문 감사드립니다!! 수빈님의 관점에서 또 너무 좋은 내용을 공유해주신 것 같습니다!! 해당 코드에서 발생하는 혼란스러운 부분에 대해 제 기준에서 정리해보면 다음과 같습니다.반복되지 않는 첫 번째 알파벳을 찾는 문제에서, '첫 번째'라는 기준이 모호합니다. 이는 두 가지 관점에서 해석될 수 있기 때문입니다:알파벳 순서상 첫 번째 (a -> b -> c -> d ...)입력된 문자열에서의 등장 순서상 첫 번째예를 들어 "abadabac" 문자열에서:반복되지 않는 문자는 'c'와 'd'입니다알파벳 순서로는 'c'가 'd'보다 먼저입니다문자열 등장 순서로는 'd'가 'c'보다 먼저 나옵니다현재 구현된 코드는 알파벳 순서를 기준으로 동작하도록 되어 있습니다. 이는 not_repeating_character_array를 만들 때 알파벳 순서대로 검사하기 때문입니다.두 가지 접근 방식 모두 유효한 해결책이 될 수 있으며, 문제의 요구사항에 따라 선택하면 됩니다. 다만 이런 경우에는 어떤 기준을 사용했는지 주석이나 문서에 명확히 명시해주는 것이 좋습니다.따라서 해당 내용에 대해서는 문서를 기준으로 추가적으로 작성해두도록 하겠습니다강의가 더 자세해질 수 있도록 좋은 질문해주셔서 넘넘 감사드립니다!!

3주차 병합정렬 해결방법

오 발견했습니다 viktor 님!!! 당장 변경했습니다발견해주셔서 넘넘 감사드려요 ㅎㅎㅎ감사의 의미로 커피 기프티콘을 드리고 싶습니다 아래 카카오톡 오픈 링크로 연락 부탁드립니다!!https://open.kakao.com/me/ding_coding_co감사합니다

멜론 베스트 앨범 알고리즘 시각화 궁금중

그리고 감사의 의미로 커피 기프티콘을 드리겠습니다 아래 카카오톡 오픈 링크로 연락 부탁드립니다!!https://open.kakao.com/me/ding_coding_co감사합니다

멜론 베스트 앨범 알고리즘 시각화 궁금중

안녕하세요 sonjs 님!! 좋은 질문 넘넘 감사합니다 1. "장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록한다" 조건 처리에 대해질문하신 대로, 인덱스 순서대로 처리되는 이유는 이미 for 루프와 sorted 함수의 특성 때문입니다.코드를 다시 살펴보면:sorted_genre_index_play_array = sorted( genre_index_play_array_dict[genre], key=lambda item: item[1], reverse=True ) 여기서 sorted 함수는 reverse=True로 재생 횟수를 기준으로 내림차순 정렬하고 있습니다.하지만 재생 횟수가 동일한 경우에는, Python의 sorted 함수는 안정 정렬(stable sort)을 사용하기 때문에, 원래 입력 순서(즉, 인덱스 순서)를 유지합니다.즉, genre_index_play_array_dict[genre] 리스트는 처음에 인덱스 순서대로 저장되었으므로, 동일한 재생 횟수를 가진 노래는 자연스럽게 인덱스가 낮은 순서대로 정렬됩니다.2. 질문자의 생각이 맞는지 확인네, 질문자님께서 생각하신 내용이 정확합니다!이미 for 루프에서 데이터를 genre_index_play_array_dict[genre]에 추가할 때 인덱스 순서대로 저장되었으므로, sorted를 적용해도 안정 정렬 특성상 인덱스가 낮은 것이 먼저 오게 됩니다.예를 들어:genre_index_play_array_dict["classic"] = [[0, 150], [2, 150], [3, 800]] 여기서 sorted를 적용하면, 재생 횟수를 기준으로 정렬된 결과는:[[3, 800], [0, 150], [2, 150]] 이런 식으로 정렬되며, 재생 횟수가 동일한 항목의 경우 인덱스 순서를 유지했을 것입니다.3. 왜 정답으로 인정되는지프로그래머스에서 제출된 코드가 정답으로 처리되는 이유는:재생 횟수를 기준으로 정렬하는 로직은 명확히 구현되어 있고,동일한 재생 횟수의 경우 안정 정렬의 특성상 인덱스 순서대로 처리되기 때문입니다.이로 인해, 문제의 조건(재생 횟수 같을 경우 인덱스가 낮은 순서)이 자연스럽게 만족됩니다.따라서 sonjs7554 님의 생각이 맞습니다! 이미 for 루프와 sorted 함수의 안정 정렬 특성으로 인해, 재생 횟수가 동일한 경우 인덱스 순서가 유지됩니다. 이 내용에 대해 설명이 추가적으로 작성되면 더 좋을 것 같습니다!!감사드립니다 덕분에 더 좋은 강의를 만들 수 있을 것 같습니다!! 좋은 하루 보내시고 새해 복 많이 받으세요

해시 충돌에서 링크드 리스트말고 해시테이블을 이용해서 구현하지 않는 이유가 있을까요?

안녕하세요 세일님!! 좋은 질문 넘넘 감사합니다!!질문하신 내용을 보면, 해시 충돌 해결을 위해 링크드 리스트 대신 내부적으로 해시 테이블을 또 사용하는 방식을 제안하셨는데요, 이를 실제로 구현하지 않는 이유를 함께 살펴보겠습니다.1. 시간 복잡도의 차이해시 테이블 내부에서 또 다른 해시 테이블을 사용하는 경우, 이론적으로는 각 충돌 체인의 검색 시간 복잡도가 O(1)로 줄어들 수 있습니다.하지만 이 O(1)은 "해시 함수가 완벽히 동작하고 충돌이 전혀 없는 경우"에만 성립합니다. 현실적인 시스템에서는:내부 해시 테이블에서도 충돌이 발생할 가능성이 있으며, 충돌을 해결해야 하므로 시간 복잡도가 O(1) * O(1)로 단순히 떨어지지 않습니다.충돌 발생 시 다시 충돌 해결 전략(체이닝, 오픈 어드레싱 등)을 도입해야 하므로 복잡성이 증가할 수 있습니다.2. 공간 효율성 문제해시 테이블을 또 사용하는 방식은 다음과 같은 문제가 있습니다:각 슬롯마다 새로운 해시 테이블을 생성하면 메모리 사용량이 급격히 증가합니다.특히, 충돌이 적은 경우에도 불필요한 해시 테이블이 생성되어 공간 낭비가 발생합니다.링크드 리스트는 간단히 메모리를 동적으로 할당하여 필요한 만큼만 사용하므로 공간 효율성이 훨씬 높습니다.3. 구현 복잡성해시 테이블 내부에 또 해시 테이블을 사용하면:이중 해시 함수 설계가 필요합니다.외부 해시 테이블과 내부 해시 테이블이 각각 다른 해시 함수를 사용해야 합니다.이를 설계하고 관리하는 비용이 추가됩니다.링크드 리스트는 단순히 노드를 연결하기만 하면 되지만, 이중 해시 테이블 구조는 더 복잡한 로직이 요구됩니다.4. 실제 성능 차이링크드 리스트를 사용하는 체이닝 방식은 충돌이 적은 경우 성능이 매우 뛰어나며, 충돌이 많아지는 경우에도 구현과 관리가 상대적으로 간단합니다.반면, 내부에 해시 테이블을 사용하면 충돌이 많아질 경우 해시 충돌 해결 전략 자체가 다시 성능 병목이 될 수 있습니다.결론링크드 리스트를 사용하는 체이닝 방식은:충돌 해결을 위한 간단하고 효율적인 방법입니다.메모리 사용량을 최소화하면서 구현 복잡성을 낮추는 데 적합합니다.해시 테이블 내부에 또 다른 해시 테이블을 사용하는 방법은 이론적으로 흥미로운 접근이지만, 메모리 사용량과 구현 복잡성, 충돌 가능성 등의 현실적인 문제 때문에 일반적으로 사용되지 않습니다.좋은 질문 덕분에 저도 다시 한 번 생각해볼 기회를 가졌습니다! 추가적인 궁금증이 생기시면 언제든 편하게 질문 주세요

3주차 병합정렬 해결방법

안녕하세요 viktor님!! 좋은 질문 남겨주셔서 감사합니다 제가 코드 부분과 영상 부분에 merge 함수에 return 이 빠진 부분을 찾아봤습니다 우선 코드 내에서는 이렇게 되어있고,def merge(array1, array2): result = [] array1_index = 0 array2_index = 0 while array1_index 영상(3-4. 정렬 - 3 의 7:44)내 에서도 return 문이 있는것으로 파악했습니다 혹시 어떤 부분에 return 이 없는지 알려주실 수 있을까요? 꼭 개선하겠습니다 __3-4. 정렬 - 33-4. 정렬 - 3

병합정렬 문제에서 조건이 하나 빠진 것 같습니다

안녕하세요 WonDollar 님! 좋은 질문해주셔서 감사합니다 ㅎㅎㅎ 매우 열심히 공부해주시는 모습에 넘넘 감사드립니다!! 제가 수업때 작성했던 코드가 다음과 같은데, 원달러님의 코드로도 동일하게 동작이 가능합니다!while array1_index 예를 들어서 [1, 1, 3] [1, 1, 3] 이라는 배열이 입력되었을 때를 가정해보겠습니다.제가 작성한 코드의 동작방식은 다음과 같습니다:두 배열의 첫 번째 요소를 비교합니다.두 배열 모두 첫 번째 요소가 1이므로, else 절이 실행됩니다.result 배열에 1이 추가되고, array2_index가 증가합니다.다시 비교를 진행합니다.첫 번째 배열의 첫 번째 요소(1)와 두 번째 배열의 두 번째 요소(1)를 비교합니다.동일하게 else 절이 실행되어 result 배열에 1이 추가되고, array2_index가 또 증가합니다.세 번째 비교에서는 첫 번째 배열의 첫 번째 요소(1)와 두 번째 배열의 세 번째 요소(3)를 비교합니다.첫 번째 배열의 값이 더 작으므로, if 절이 실행되어 result 배열에 1이 추가되고, array1_index가 증가합니다.이 과정을 반복하면 최종적으로 result 배열에는 [1, 1, 1, 1, 3, 3]이 저장됩니다.원달러 님의 코드는 동일한 값을 모두 넣기 위해 else 절에서 두 값을 각각 추가하도록 설계되었습니다.이 경우에도 동일한 입력을 처리했을 때 result 배열은 [1, 1, 1, 1, 3, 3]이 되지만, 코드 동작 방식이 약간 다릅니다.원달러 님 코드에서는 동일한 값을 만날 때 두 값을 각각 한 번씩 추가하고, first_array_index와 second_array_index 모두 증가시키기 때문에 두 배열에서 중복된 값이 있을 때 모든 경우를 명시적으로 추가하는 결과를 얻을 수 있습니다.이 방식은 명확하게 동일한 값 처리 로직을 작성하려는 의도에 적합하며, 특정 상황에서 더 직관적일 수 있습니다.결론적으로, 두 코드 모두 결과는 동일하지만, 작성 목적과 의도에 따라 선택할 수 있습니다! 😊다시 한 번 열심히 공부해 주셔서 감사드리며, 추가적으로 궁금하신 점은 언제든 질문 주세요! 💙

2019-라인 나잡아봐라 문제

안녕하세요 민규님! 좋은 질문 감사합니다 말씀주신 내용이 정확합니다!!!!일반적인 BFS의 경우에는 재방문할 필요가 없는지 여부를 파악하기 위해서 visited 를 사용하지만, 이 문제의 경우 말씀해주신대로 현재 시간대에 방문할 수 있는 경우의 수만 파악하면 되는 문제이기 때문에 visited 배열이 필요하지 않습니다. 각 시간대는 독립적으로 후보군을 찾아나가야 하고, 그 위치가 현 시점 코니의 위치와 일치하는지만 파악하면 되기 때문입니다 강의 설명의 오류를 찾아주셔서 넘넘 감사드립니다!! 시일 내에 강의 영상과 교재에 올바르게 업데이트해두겠습니다!! 그리고 감사의 의미로 커피 기프티콘을 드리겠습니다 아래 카카오톡 오픈 링크로 연락 부탁드립니다!!https://open.kakao.com/me/ding_coding_co감사합니다

1-10강 문제풀이중...

안녕하세요 Hello World님! 좋은 질문 감사합니다.내장함수를 이용해서 새로운 풀이방법을 고민해보시는 점 너무 좋습니다!!충분히 알고리즘적인 생각이고, 좋은 접근법입니다! 다만, 시간 복잡도 적인 면에서 아쉬운 점이 있습니다.string.count(char)를 사용하면, 사실상 문자열 전체를 매번 순회하게 됩니다. 따라서 각 문자마다 문자열을 전부 탐색하므로 시간 복잡도는 O(N) * N, 즉 O(N²)가 되어 매우 비효율적입니다.for char in string 에서 O(N) 만큼, string.count(char) 에서 O(N) 만큼 소요하게 되어서 2중 반복문의 형태로 O(N²)의 시간이 소모되게 되는 것입니다. 반면, 아스키 코드를 활용하면 한 번의 순회로 빈도를 계산할 수 있어 O(1) * N, 즉 O(N)의 시간 복잡도로 훨씬 효율적입니다. 파이썬을 하다보면, 이처럼 내장함수라서 매우 간단해보이지만 생각보다 시간복잡도가 높은 함수들이 몇개 존재합니다. 따라서 이런 것들을 주의하면서 코드를 작성해야 할 것 같습니다좋은 질문 감사합니다 새해 복 많이 받으세요!!