알고리즘 - 연속된 수의 합

def solution(num, total):
    start = -1000
    end   = 1000
 
    while start <= end:
        mid = (start + end) // 2
        r = [x for x in range(mid, mid + num)]
        s = sum(r)
        if s == total:
            return r
        if s < total:
            start = mid + 1
        else:
            end = mid - 1

• 내가 푼 답은 위와 같음.

논리 전개 과정

• 어디부터 시작하는지 어떻게 알지?
• 하나하나 기계적으로 맞춰보자
• -1000부터 1000까지 대입해보면 맞겠지
• 비효율적임.
• 이진탐색으로 하면 최악이어도 log2000이니까 11번안에 맞춘다.
  • [[KnowledgeBase/Zettelkasten/Permanent(퍼미넌트)/개발에서 log 계산]]
  • 풀만함

포인트

• start, end 범위
  • 처음에 -total ~ total 로 했는데 그렇게하면 -음수의 범위는 더 커질수도 있어서 잘못될 수 있음.
• mid 구하는 공식 -> 너무 직관적으로 생각해서 잘못 구했음
  • start + (start / 2) 이렇게 구했는데 틀렸음.
    • 이런 문제에서는 가지고 있는 변수를 다 가져다 썼어야함.
  • mid를 구하고 +1, -1을 생각하지 못함
    • 조건문으로 특정 조건마다 +1, -1을 하려고했는데 이건 나쁜 생각이었음.

더 좋은 방법

def solution(num, total):
#     등차수열
    offset = num * (num - 1) // 2
#     남은 값
    n = total - offset
#     남은 값을 num에 분배
    r = n//num
        
    return [x for x in range(r,r+num)]

• 애초에 num, total, result 는 반복문 없이 구할 수 있음.
• num으로 total을 구하기 위해서는
  • num이 명확하게 정해져 있으므로
    • 등차수열 공식 (num * (num - 1)) // 2 을 구하고
    • total에 위 값을 뺌
    • 위 값을 빼면 남은 값은 각 number에 할당을 해야함.
      • 예를들어 total = 12, num = 3 이면
        • 등차수열(offset)로 0+1+2 = 3, total-offset 하면 12-3 = 9
        • 9는 num이 3이므로 3개의 요소에서 공평하게 가져가야함.
        • 즉 9/3 = 3
        • 그럼 3부터 시작
      • 2번째 예시
        • num = 4, total 14
        • offset = 6
        • total - offset = 8
        • 8/4 = 2
        • 2부터 시작(2,3,4,5)
      • 3번째 예시
        • num = 5, total = 5
        • offset = 10
        • total - offset = -5
        • -5 / 5 = -1
        • [-1, 0, 1, 2, 3]
  • 이렇게 해결하는것이 훨씬 간단함

최종 정리

• 아래와 같은 구조로 문제를 풀 수 있음.
  • 식 세우기
  • 상수항 분리
  • 미지수 해 구하기
• 미리 알고 있어야 하는 것
  • 등차수열 합 공식
• 휴리스틱으로 풀어야 하는 경우
  • 이진트리 사용방법
    • mid 사용방법
    • start, end 사용 방법
    • 시간복잡도 계산 방법