세 수의 합 15.3Sum

오늘부터 알고리즘 주차가 시작되면서 과제를 부여받았다.

내가 맡아서 문제를 공유할 내용에 대해서 작성해보려고 한다.

일단 알고리즘 경험이 거의 ....없다..
(코드업 백준 등 기본문제 몇개 풀어본 정도...? 프로그래머스는 건들지도 못하겠다..)

암튼 거의 기초지식이 없는 상태에서 문제를 접해보고 답지를 보면서 문제풀이도 해보는데

사실 잘 이해가 가지 않는다. 20시에 과제를 제출해야되는데 큰일이다.

암튼..

세 수의 합 문제는 리트코드에 있고 난이도는 별2개다. 아기자기하게 이모지를 붙이고 싶지만 그럴 시간이 없으니 패스...

풀이 과정을 보면서 일단 개념부터 정리해보기로 하고 이후에 문제를 풀게되면 아래에 계속 작성해보려고 한다..

일단은 풀이는 2가지 방식이 있었고,
브루트 포스로 풀이 하는 방법과 투 포인터로 합 계산
이렇게 두가지가 있다.

문제를 보고 되게 막막했는데, 풀이를 보니 더 막막하다...뭐지?

브루트 포스 라는 것도 알아야 했고, 브루트 포스 라는 것을 쓰면 어떤식으로 접근해야되는지도
알 수 있나보다..

일단 위키백과에 있는 브루트 포스 내용을 가져왔다.

브루트 포스(brute force), 키 전수조사(exhaustive key search) 또는 무차별 대입(無差別代入)은 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법이다. 흔히 암호학에서 연구되나, 다른 알고리즘 분야에서도 사용되고 있다.

흔히 수학 문제를 원시적으로 푸는 방법인 '수 대입 노가다'의 학술적 버전이다.

일일이 수를 전부 대입을 해서 코딩을 이용한 노가다인 것 같다.

그래서인지 타임아웃이 될 가능성을 예측하여 접근했다는 점도 이해를 해서 알아내야하는 부분이다.

풀이2 투 포인터 합 계산

두 포인터가 양쪽에서 간격을 좁혀가며 합을 계산한다.

left, right = i + 1, len(nums) - 1
while left < right:
sum =nums[i] + nums[left] + nums[right]
if sum < 0:
left += 1
elif sum > 0:
right -1
else:
results.append({nums[i],nums[left],nums[right]})

 while left < right and nums[left] == nums[left + 1]:
   left += 1
 while left < right and nums[right] == nums[right -1]:
   right -= 1
 left += 1
 right -= 1
return results

sum이 0보다 작다면 값을 더 키워야 하므로 left를 우측으로 이동하고, 0보다 크다면
값을 더 작게 하기 위해서 right를 좌측으로 이동한다,.

sum =0 이면 정답이니, 이 경우에 결과를 result에 추가한다.
이렇게 반복해서 값을 찾아낸다

회고

알고리즘 주차에 들어와서 한 문제도 스스로 풀지 못해서 많은 개념 이해가 필요할 것 같다.
그리고 책을 보면서 이해가 되지 않는 부분들에 대한 TIL을 작성해야겠고
읽어보면서 느낀 것을 간단하게 요약하면, 로직 작성 시 시간복잡도에 따라 고려해야할 것들을
생각하면서 작성해야겠고, 클린코드를 작성하기 위해서 노력해야겠구나 생각했다.

자세한 내용은 유튜브에서 회고하겠다.