🐝 코딩테스트 🍯팁 - Python편

코딩테스트를.. 기업에서 본다고 한 후 오늘부터 제대로 공부하는 중...
왜 이렇게 문제가 어려울까??? 하지만, 차근차근 공부하다보면 언젠가 웬만한 문제들을 풀 수 있는 경지에 오르지 않을까?
그렇게 되기까지 매일 공부하자구! 👍

1. 정렬 후 앞에서부터 선택하면 최적이 되는 경우

• 최대한 많은 개수를 선택해야 하는 문제
• 조합을 모두 고려할 필요가 없고, 작은 값부터 선택하는 것이 최적일 때

[코드]

복잡도 O(N log N)

d.sort()  # 작은 값부터 정렬
total_budget = sum(d[:mid])  # 앞에서 mid 개만 선택해서 합산

[문제 예시]

🤑 예산문제 - 프로그래머스

위와 같이 특정 값에 부합하도록 조합을 완성해야할 때 사용하면 좋음

[문제 풀이]

처음에 combinations O(2^N) 로 풀었다가, 시간 초과로 나가리 됐다 😂
그래서 GPT에게 물어보니 이 방법을 추천해주었다.

def solution(d, budget):
    answer = 0 
    
    left, right = 1, len(d)

    d.sort()
    total_budget = []
    while left <= right:
        mid = (left + right) // 2  
        
        total_budget = sum(d[:mid])   
        
        if total_budget > budget:  
            right = mid - 1 
        else: 
            answer = mid 
            left = mid + 1  

    return answer

2. 리스트에서 특정 값을 찾을 때는 in 쓰기 전에 set 사용!

리스트에서 특정값을 찾는 경우가 은근 많은데, 그럴 때마다 리스트에서 in을 쓰지말고 set으로 타입을 변경한 후 in을 쓰면 해시테이블을 사용해서 검색 속도가 O(N) -> O(1)로 훨씬 빨라짐

arr = [3, 5, 1, 7, 9]
target = 7

if target in arr:
    print("찾았다!")  

위 코드 보다

arr_set = set(arr) ## 이렇게 한 번 타입을 바꿔주고 진행
if target in arr_set:
    print("찾았다!")

3. 최소값과, 최댓값을 찾아야 한다면? list <<< heap

-- 추후 업데이트 되는대로 계속 추가아아