[프로그래머스] 시소 짝꿍 문제. 배열이 길다면 해시를 생각해보자.

서론 프로그래머스 - 시소 짝꿍 https://school.programmers.co.kr/learn/courses/30/lessons/152996 유사한 문제가 자주 나옴에도 불구하고 비슷한 실수를 반복하는 것 같아 기록하고자 글을 작성한다. 해당 문제에서 주어진 제한사항은 배열의 길이가 100,000으로 상당히 탐색에 시간이 많이 소요될 것이다. 이런 경우 완전 탐색으로는 시간 초과가 발생하므로, 이진 탐색, dfs 등 여러 옵션을 생각할 수 있다. 하지만 이렇게 단순 값을 비교하는 문제는 해시부터 시도해보는 것이 좋다. 문제 풀이 1차 시도 - combinations 사용 결과: 시간 초과 from itertools import combinations def solution(weights): ans..

• format_list_bulleted Algorithm
• · 2024. 2. 25.
• textsms

Python의 set() 시간복잡도 고려하기 (feat. 프로그래머스 카카오 보석쇼핑 문제)

서론 프로그래머스 - 2020 카카오 인턴십 보석쇼핑 https://school.programmers.co.kr/learn/courses/30/lessons/67258 해당 문제를 풀었을 때, set를 사용하여 시간을 단축시키려 했으나 효율성 테스트에서 실패했다. 많은 글들을 찾아봤으나 '해당 문제는 배열의 길이가 최대 100,000이므로 탐색 횟수를 줄여야 한다, 그러므로 투포인터를 사용해야 한다'는 설명만 있고, 어떤 방식을 사용해야 탐색 횟수를 가장 많이 줄일 수 있는지에 대한 설명은 없었다. 본 글쓴이는 탐색 시간을 줄이기 위해 투포인터와 set()를 사용했고, 이를 통해 탐색 시간을 어느정도 줄일 수 있었지만, 그것이 Best solution은 아니었던 것 같다. set를 사용해서도 시간을 줄일..

• format_list_bulleted Algorithm
• · 2024. 2. 25.
• textsms

max(), min()은 언제 어떻게 사용하는 게 좋을까?

서론 알고리즘 문제를 풀다보면, 어느 한 문제에서는 사용해야 풀 수 있던 어떤 기능이 다른 문제에선 오히려 그 문제를 푸는데 악영향을 끼치기도 한다. 이번에 논의할 max()와 min()도 바로 그러한데, max()와 min()는 처리되는데 O(n)의 시간이 걸리므로 무턱대고 반복문 내에서 사용했다간 시간을 엄청나게 잡아먹어버린다. 우선 max()와 min()의 시간복잡도를 먼저 알아보고 그 이후 예시와 함께 어떤 문제에서 이 기능을 활용하면 좋을지 살펴보기로 한다. max(), min()의 시간복잡도 max()와 min()함수에는 입력값으로 배열을 넣을 수 있고, 배열을 넣게 되면 해당 함수는 모든 원소의 값을 비교해서 가장 큰 값을 반환해준다. 이렇게 max()와 min()은 함수 내부에서 모든 원소..

• format_list_bulleted Algorithm
• · 2023. 9. 15.
• textsms