Two Sum

Two Sum - LeetCode

접근 방법 [필수 작성]

제한조건 확인

1. 각 문제들은 하나의 Solution 만을 가짐 → 즉, 해 구하면 바로 return 가능

1. nums 의 길이가 10^4 이하 이므로, 투포인터 기반 완전탐색을 진행하여도 10^8 의 iteration 반복 → 100,000,000 → 1억번 연산 < 2억
2. 완전탐색 사용하더라도 1초이내 연산 가능
3. 따라서 가장 쉬운 완전탐색방법으로 접근

코드 구현 [필수 작성]

완전탐색으로 구현

소요시간: 5분

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                pred_target = nums[i] + nums[j]
                if pred_target == target:
                    return [i,j]

재귀함수로 구현

소요시간: 20분

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []

        def recur(start):
            if len(ans) == 2:
                if nums[ans[0]] + nums[ans[1]] == target:
                    return ans
                return False
            else:
                for i in range(start, len(nums)):
                    ans.append(i)
                    if recur(i+1):
                        return ans
                    ans.pop()
        
        return recur(0)

결과

완전탐색으로 구현

재귀로 구현

배우게 된 점 [ 필수 X ]

1. 재귀함수 return 은 껍질을 depth 만큼 까고 나와줘야한다.

오류 코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []

        def recur(start):
            if len(ans) == 2:
                ~~if nums[ans[0]] + nums[ans[1]] == target:
                    return ans~~
            else:
                for i in range(start, len(nums)):
                    ans.append(i)
                    ~~recur(i+1)~~
                    ans.pop()
        
        return recur(0)

return 만 해주면 바로 return 값을 반환할 줄 알았는데 return 값이 없어서 헤맸다. depth 가 2인 곳에서 return 이 되었지만, depth 가 1인곳에서 return 값이 없으므로 최종 리턴값이 없었다. 비유하자면, 껍질을 2번 파고 들었으니, 껍질을 2번 까고 나와야한다.

수정코드

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []

        def recur(start):
            if len(ans) == 2:
                if nums[ans[0]] + nums[ans[1]] == target:
                    return ans
                return False
            else:
                for i in range(start, len(nums)):
                    ans.append(i)
                    if recur(i+1):
                        return ans
                    ans.pop()
        
        return recur(0)

2. 같은 O(n^2) 알고리즘이라도 n^2 앞에 붙는 상수값에 따라 연산시간에 차이가 발생하여 테스트 통과여부에 영향을 줄 수 있다.

for 문을 활용한 구현은 통과했지만, 재귀를 활용한 구현은 통과하지 못했다.

( list 원소 삽입,삭제와 스택관리 관점에서 더 복잡하기 때문에 그럴 것으로 예상한다. )

3. 재귀함수 구현할때 기본 형태를 작성하고 하면 편하다.

오랜만에 재귀를 구현하려다보니 시간도 오래걸리고 어떻게 짜야할지 당황스러웠다. 이때, Template 코드, 또는 Skeleton 코드를 활용하면 편하다.

if ~~~~: #basecase
	return ~~~
else:
	a.append()
	recur()
	a.pop()

질문 [ 필수 X ]

질문#1

1주차 5강 완전탐색 27분16초 부분 강의영상 보면 노씨님은 타입힌트 적혀있던걸 일부러 지워서

이런식으로 만드시던데 이유가 따로 있나요?

타입 힌트와 관련된 GPT 답변

첫 번째 코드에서는 함수 선언 시에 타입 힌트를 사용하고 있습니다. 이것은 Python 3.5 버전 이후부터 도입된 기능으로, 함수의 매개변수와 반환값에 대한 타입을 명시적으로 표현할 수 있게 해줍니다. List[int]는 리스트가 정수를 포함한다는 것을 나타내는 타입 힌트입니다. 이는 코드의 가독성을 높이고, 개발 도구에서 코드를 더 잘 이해하고 검사할 수 있도록 도와줍니다.

두 번째 코드는 타입 힌트를 사용하지 않고, 간단히 매개변수의 이름과 타입만을 명시하고 있습니다. 이는 Python 3.5 이전 버전에서 사용되던 방식이며, 현재도 여전히 유효한 문법입니다. 하지만 타입 힌트를 사용함으로써 코드의 가독성과 유지보수성을 향상시킬 수 있습니다.

질문#2

2억번 연산이 통상적으로 1초정도의 연산을 가지는 것으로 알고있는데,

실제 결과에서는 4000ms, 즉, 4초 정도 걸렸습니다.

굉장히 단순한 코드기에 1억번연산정도라고 생각하면 예상값이 500ms 여야 하는데 훨씬 상회합니다.

어떤 이유가 있을 수 있나요?

질문#3

또 노씨님이 28분17초에 작성한 코드와 제 코드가 크게 다르지 않은데, 2배 이상의 연산시간이 차이가 납니다. pred_target 이라는 새로운 변수선언때문에 그런건가 해서 지워보기도 했는데 여전히 3400ms 로 두배정도의 연산시간의 차이가 발생합니다. 리트코드에서 자동으로 배정되는 서버가 달라서 서버의 연산능력 차이때문에 발생하는 걸까요?

어떤 이유가 있을 수 있나요?

피드백 [ 코치 작성 ]

타입 힌트의 경우 가독성을 위한 기능이며 성능에는 영향을 미치지 않습니다.

2번 질문의 경우 cpu의 clock cycle과 cpi(cycles per instruction) 등에 대한 지식이 선행되야 합니다. cpu가 주어진 작업을 처리하기 위해 걸리는 시간을 cpu time이라고 합니다. cpu time은 cpu의 클럭 사이클 횟수인 clock cycle과 한번의 클럭 사이클에 걸리는 시간인 clock cycle time의 곱으로 나타나며 clock cycle은 작업의 명령어의 개수인 instruction count와 한번의 사이클에 처리할 수 있는 명령어의 개수인 cycles per instruction의 곱으로 나타납니다. 즉 Cpu Time = IC CPI ClockCycleTime으로 표현되며 이를 줄이는 것이 작업의 시간을 줄이는 방법입니다.

이제 질문해주신 것에 대한 답변을 드리자면 2억번의 연산이 통상적으로 1초의 시간을 갖는다는 것은 말 그대로 통상적인 컴퓨터의 CPI와 ClockCycleTime에 대해 설명한 것으로 CPI와 ClockCycleTime은 컴퓨터별로 다르기에 위와 같은 차이가 발생하는 것입니다. 또한 1억번의 연산이라고 하신 것도 1억번 이상의 명령어로 구성될 수 있습니다.(+ 연산 한번이라 하더라도 피연산자 레지스터 둘에 값을 로드하고 더한 후 해당 값을 저장하는 것과 같이 여러번의 명령어가 수행될 수 있습니다.) 하지만 이러한 요소는 몇 배 정도의 차이만 발생시키며 수백, 수천배 이상의 차이를 발생시킬 수 있는 요소인 시간 복잡도를 중요하게 고려해야 하는 것입니다.

이 외에도 메모리 접근 방식, OS와 컴파일러 버전 등 다양한 원인이 실행 속도에 영향을 미칠 수 있습니다.

3번 질문의 경우 코딩 테스트 사이트들의 작동 방식에 대해 알아야 합니다. 코딩 테스트 사이트들은 컨테이너 방식(대표적인 컨테이너 관리 오픈소스 프로젝트로 도커가 있죠)으로 작동되며 사용자가 코드를 제출할 시 새로운 컨테이너를 배정해주고 해당 컨테이너에서 코드를 실행하는 방식으로 작동됩니다. 이 때 배정해주는 컨테이너의 자원을 관리해주는 자원 관리 시스템이 유동적으로 자원을 할당해주기에 각각의 제출에 대해 다른 양의 자원을 배정받을 수 있습니다. 이와 같은 이유로 동일한 코드를 여러번 제출해도 각각 다른 런타임이 발생하게 됩니다.

이 외에도 제출 당시 네트워크 상태, 캐시된 데이터 등 다양한 요인이 실행 시간에 영향을 미칠 수 있으며 앞서 설명드렸듯이 이와 같은 요소들 보다 입력 크기, 시간 복잡도 같은 요소가 더 중요합니다.(시간 복잡도가 클 경우 런타임이 크게 나오는 것이 아니라 time limit가 발생하겠죠) 그렇기에 런타임은 지나치게 신경 쓰지 않아도 됩니다.