대부분의 IT 회사가 채용 과정에서 코딩 테스트 시험을 봅니다. 그러다 보니 취직이나 이직을 준비하시는 분들은

프로그래머스나 백준 등의 온라인 코딩 테스트 사이트에서 이런저런 코딩 문제를 풀면서 실력을 키우려고

노력하죠. 그런데 연습 삼아 코딩 문제를 풀 때 놓치기 쉬운 부분이 하나 있는데요. 제가 느끼기엔

적지 않은 분들이 코딩 문제를 풀고 나서 그게 통과되면 OK, 이건 풀었고 그럼 이제 다음 문제, 이렇게 바로

다음 문제로 넘어가시는 것 같아요. 그런데 실제 기술 면접에서는 코딩 테스트 문제를 풀었다고 끝이

아닐 수 있습니다. 문제를 잘 풀었다고 해도 여기서 더 개선할 여지가 없는지 물어볼 가능성이 있는데요. 보통 처음 짠 코드에는

시간적인 성능 면에서 개선할 여지가 있기 마련이라 면접관 눈에는 그게 보이기 때문에 이걸 좀 더 개선할

수는 없는지 물어보게 되는 거죠. 그러면 평소에 이 훈련이 잘 안되어 있다면 멘붕이 올 수 있습니다. 어

요구조건대로 동작하게끔 짰는데 여기서 더 계산을 하라고 이렇게 당황하게 되는 거죠. 사실

계산의 여지가 있는지를 물어보는 이 질문은 시간 복잡도와도 관련이 있는 질문인데요. 그래서 오늘 영상은 예제를

통해서 내가 짠 코드를 어떻게 개선해 나갈 수 있는지 설명드리도록 하겠습니다. 자, 여기 이렇게 문제가 하나 있어요. 이 문제는 어떤 문제냐면

list에 있는 서로 다른 두 정수의 합이 타겟 넘버와 같다면 True를 반환하는 함수를 구현하는 겁니다. 그래서 예를 들어서 이 nums라는 이름의

리스트에 이렇게 데이터가 있고 타겟 넘버가 7이라고 한다면 지금 이 리스트 상황에서는 1과 6을 더하면 7을 만들 수 있잖아요

그러면 이런 경우에는 리턴 트루를 해줘야 되는 거고요 그런데 만약에 타겟 넘버가 10이라면 그러면 이

리스트에서는 어떤 서로 다른 두 개의 정수를 고른다 할지라도 그 두 개의 합이 10을 만들 수는 없기 때문에 그러면 이때는

리턴 폴스를 해야 되는 겁니다 자 그러면 이런 문제를 코딩 테스트 사이트에서 만났다고 해 볼게요 그러면 보통

테스트 사이트에서는 이런 식으로 함수의 시그니처 부분을 제공을 합니다 지금 얘 같은 경우에는 파이썬 코드인 건데 이런 식으로 파이썬 코드의

시그니처를 주게 되면 그 바디 부분을 이제 구현을 하면 되는 거예요 그러면 여기서 이 넘스라는 파라미터는 리스트를 의미를 하는 거고요 이

타겟이라는 것은 타겟 넘버를 의미하는 겁니다. 그러면 보시는 분들도 각자 이 문제를 어떻게 풀 수 있을지

잠시 생각을 해보시는 것도 좋을 것 같아요. 자, 이 문제를 풀기 위해서 이런저런 고민을 해본 뒤에

어떤 아이디어가 떠올라서 이런 형태로 구현했어요. 자, 그러면 얘가 어떤 식으로 동작하는

코드인지를 이 넙스라는 이름의 list와 함께 설명을 드리도록 하겠습니다. 지금 파이썬 코드로 되어 있지만 파이썬 문법과 함께 자세히 설명하지는

않을 거구요. 이 코드가 어떻게 동작하는지 그 방식 위주로 설명하도록 하겠습니다. 자, 그러면 이 코드는 바깥쪽에 for 루프가 하나가 있고요.

안쪽에도 for 루프가 하나가 있습니다. 얘는 어떤 친구로 동작을 하는 거냐면 바깥쪽 for 루프를 통해서 여기에 i를

잡고 이 아이를 하나하나씩 증가시킵니다 그러면 이렇게 하나하나씩 증가시킬 때마다 이 안쪽 포르프에서는 제의를

통해서 그때마다 배열에 있는 모든 데이터를 한 번씩 접근을 하는 겁니다 그래서 예를 들어서 아이가 이렇게 처음 시작을 하게 되면 아이가 여기를

가리키는 동안에 j가 이렇게 전체를 한번 훑게 되는 거고요 그 다음에 또 아이가 하나 증가하게 돼서 여기를 가리키게 되면

체인은 또 다시 한번 전체를 이렇게 훑게 되는 겁니다 그래서 이 이중 포르프가 이런 식으로 동작을 하게

되는 거고요 그러면 이 안쪽에 바디 부분을 살펴보면 일단 지금 이 코드는 어떤 코드냐면 이 문제의 조건이 리스트에 있는

서로 다른 두 정수의 합이라고 했기 때문에 지금 이렇게 아이가 가리키는 값과 j가 가리키는 값은 같으면 안

되는 거잖아요 그래서 그렇게 i와 j가 같으면 컨티뉴를 하라는 그런 코드인 거고요 그 다음에 그 밑에 있는 코드는

뭐냐면 이렇게 i가 가리키고 있는 값이 없고 그 다음에 또 그 밑에서 j가 이렇게 루프를 돌면서

j가 가리키고 있는 값이 있을 텐데 그렇게 i가 가리키는 값과 j가 가리키는 값을 더해서 그 더한 값이 타겟과 같은지 이렇게 비교를

하는 겁니다 그래서 만약에 같으면 바로 트루를 리턴하는 거고요 만약에 같지 않으면 계속해서 루프를 도는

거예요 그래서 이 i가 주루룩 증가를 해서 이 끝까지 다 왔고 그 다음에 그 안쪽 루프에서 제일로 다 이렇게

순회를 했는데 그래서 모든 데이터에 하나씩 다 접근을 했는데 그럼에도 불구하고 이 조건을 만족하는 경우를

찾지 못했다면 그러면 최종적으로는 리턴 폴스를 하게 되는 겁니다 자 그러면 이런 식으로 구현한 코드는 실제로 제대로 동작하는 코드입니다

그래서 코딩 테스트 사이트에서 이렇게 적어준 내용을 제출을 하게 되면 얘는 통과를 하게 될 겁니다 그런데 이제 여기서 이렇게 통과를

했다고 아 나 문제 풀었어 그러면 다른 문제 풀러 가야지 이렇게 하지 마시고 일단 테스트는 통과했지만

여기서 더 계산할 부분은 없을까 반드시 생각을 해보자는 거예요 사실 지금 이 코드는 계산할 여지가 있거든요 그래서

동작하게끔 만드는데 목적을 두는 것이 아니라 당연히 제대로 동작하는 것은 중요하고 거기에 플러스해서 좀 더 나은

성능으로 동작하게 만들 수는 없는지 그것을 같이 고민을 해보는 게 중요하다 이것을 말씀드리고 싶은 겁니다 자

그러면 이제부터 저는 이 코드를 개선을 할 건데요 보시는 분들도 한 번에 쭉 보시지 마시고 중간에 멈춰가면서

나라면 어떻게 개선할 것 같다 이렇게 생각을 해보시면서 따라 오시는 것을 추천을 드립니다 자 그러면

계산할 포인트를 확인하기 이전에 이 코드의 시간 복잡도를 한번 구해 보도록 하겠습니다 보시면은 이 바깥쪽 for 루프 같은 경우에는 이 리스트에 있는

모든 데이터들을 한 번씩 다 접근을 하는 거기 때문에 만약에 이 리스트의 데이터가 n개가 있다면 이 바깥쪽 for 루프는 이 안쪽에 있는 부분을

총 n번 수행을 하게 될 겁니다 그 다음에 안쪽 for 루프를 살펴보면 얘도 마찬가지로 이 리스트에 다 한

번씩 접근을 하는 방식이기 때문에 이 안쪽에 있는 부분을 총 n번을 수행하게 될 겁니다 그러면 안쪽에 있는 이 코드는

언제나 상수 시간으로 일정하게 처리가 되기 때문에 이것을 시간 복잡도 개념에서는 O(1)이라고 표시를 하잖아요

그러면 최종적으로 시간 복잡도를 구해보면 이 안쪽 루프를 통해서 O(1)으로 동작하는 이 코드를 총 n번

수행을 하는 거니까 곱하기가 될 거고요 이 안쪽 루프를 다시 또 바깥쪽 루프를 통해서

m번 수행을 하는 거기 때문에 얘도 이 부분에 대해서 곱하기를 해줘야 됩니다 그러면 최종적인 시간 복잡도는

O(n 제곱)이 되는 거죠 그래서 지금 이 코드의 시간 복잡도는 O(n 제곱)이라는 것 이것을 확인을 했구요

이제부터 그럼 본격적으로 시간적인 성능을 개선을 해 보도록 하겠습니다 지금 이 코드는 어떤 비효율적인 측면이 있냐면 자 이

바깥쪽 루프를 통해서 이렇게 아이를 잡고 하나하나씩 증가를 한다고 했잖아요. 그러면 그때마다 안쪽 루프에서는

제이를 잡고 전체적으로 이렇게 다 아이가 하나씩 증가할 때마다 전체적으로 이렇게 한 번씩 모두 접근한다라고 했습니다.

그러면 예를 들어서 타겟 넘버가 100이라고 해보겠습니다. 그러면 맨 처음에 아이가 여기서부터 시작을 하면 아이가 지금 1을 가리키고 있을

때 이렇게 전체적으로 루프를 돌면서 j가 하나하나 하나하나씩 이렇게 확인을 하면서 아이가 가리키는 값과

j가 가리키는 값을 지금 이 코드에서 이렇게 더한 다음에 그 값이 타겟 넘버인 100이랑 동일한지 확인을 할

거잖아요. 그런데 이렇게 주조적 확인을 했는데 100이랑 같은 경우를 찾지를 못했어요. 그러면 이제 아이가 한 단계 증가해서

이번에는 2를 가리키게 되겠죠. 그렇게 2를 가리키게 되면 j는 다시 또 처음부터 이렇게 데이터를 하나하나씩 접근을 하게 돼요.

그러면 지금 i가 이렇게 2를 가리키고 있는데 다시 j는 1부터 가리키면서 이 코드 부분을 확인을 하게 되는 거잖아요.

그런데 사실 지금처럼 1과 2를 대상으로 이 조건을 확인하는 것은 이 i가 맨 처음 여기 가리키고 있을 때 이미 수행을 한 거예요.

그런데 지금 i가 이 부분을 가리키게 되면서 다시 한번 반복적으로 이 1과 2에 대해서 이 코드 부분, 요 부분을 확인을 하고 있는 거죠.

그러니까 같은 작업을 중복해서 또 수행을 하고 있는 그런 비효율성이 있는 겁니다. 아, 그러면 이 부분을 계산을 해야 되겠다 이런 생각이 들어서 이 코드를 조금 수정을 했어요.

그래서 어떤 부분이 바뀌게 되냐면 지금요

부분하고 그 다음에 이 부분이 바뀌게 되는데요 잘 보세요 어떻게 바뀌냐 이런 식으로 수정을 해준 겁니다 지금

보시면은 원래 이렇게 컨티뉴 했던 코드는 아예 사라졌고요 그 다음에 지금 이 부분이 이렇게 바뀐 건데

문법을 자세히 설명하기보다는 개념적으로 어떤 식으로 바뀌었는지 설명을 드리면 원래는 바깥쪽 루프를 통해서 i가

이렇게 돌고 그 다음에 안쪽 루프를 통해서 저희가 이렇게 돌고 있어서 i가 이렇게 하나 있으면 저희가

전체 순환하고 또 i가 하나 증가하면 다시 한번 j가 전체적으로 이렇게 순환하고 이런 식으로 동작을 했었던게 이전 코드였었잖아요

그런데 지금 코드는 i가 여기를 가리키면 j는 이렇게 데이터를 접근을 하는 겁니다 그리고 또 i가 한 단계

증가하면 j는 또 이렇게 접근을 하는 거예요 다시 한번 아이가 한 단계 증가하면 j는 또 이렇게 접근을 하는 거예요

그래서 앞선 코드와는 다르게 이렇게 접근했던 부분들이 다 사라지게 되는 겁니다 그러니까 더 이상 이런 접근 자체는

아예 하지 않게 되는 거죠 그만큼 시간적으로 비용을 줄이게 돼서 시간적인 성능도 개선이 되는 겁니다 이해가 되시죠 이제 그러면 이 코드의

시간 복잡도를 구해 보겠습니다 만약에 이 리스트에 데이터가 n개가 있다면 이 바깥쪽은 이 안쪽에 있는 부분을 총 n번 수행을 하게 될

거예요 그 다음에 이 안쪽 부분을 보면 얘는 사실은 아이가 이렇게 증가를 할 때마다 접근하는 데이터 숫자가 하나씩

줄어들게 되는 거잖아요 그래서 이 포 루프가 맨 처음에는 m-1번 접근하고 그 다음에는 m-2번

접근하고 그 다음에 n-3번 이런 식으로 점점 하나하나씩 접근하는 숫자가 줄어들게 될 겁니다 그러면

결국은 얘가 주욱 주욱 해서 최종적으로는 한 번만 접근하게 될 거고 이때의 시간 복잡도를 구해보면

이렇게 전체적으로 접근 횟수를 다 더해주면 이 시간 복잡도를 구할 수 있거든요 그러면 얘네들을 다 더해준다는 것은

결국은 등차수열의 합의 공식을 따라서 구해주면 되는 거고 그렇게 구해진 등차수열의 합에 대해서 시간 복잡도는 최고차항만 염두를 하는

거잖아요 그 최고차항만 확인을 해보면 예의의 시간 복잡도 또한 비고 n 제곱이 됩니다 그래서 바로 앞에서의 코드와 시간 복잡도는 동일해요 하지만

시간적인 성능 자체는 실제적으로는 개선이 된 겁니다 그래서 여기서 우리가 한 가지 배울 수 있는 점은 뭐냐면 시간 복잡도가 동일하다고 해서

두 코드의 성능이 항상 동일하다고 그렇게 볼 수는 없는 거죠. 왜냐하면 시간 복잡도라는 개념 자체가 시간의

경향성을 보려고 하는 거라서 어느 정도 추상화돼서 표현을 하는 방식이기 때문에 시간 복잡도가 같다라고 해서

성능 자체도 완전히 동일하다 이렇게는 볼 수가 없는 겁니다. 자 그러면 지금 이렇게 계산을 했어요. 여기까지 계산을

했는데 이에 대해서 이렇게 하나하나씩 증가를 하면서 이 안쪽 루프를 통해서 이렇게 확인을 하는 거잖아요.

그러면 이때 이 값은 현재 i가 가리키고 있는 값이 되는 겁니다. 여기서는 1이 되겠죠. 그러면 아까 이 타겟이었던

8에서 1을 뺀 7을 찾고 있는 거니까. 그러면 이 의미는 뭐냐면 결국 이렇게 루프를 순환을 하면서 이

7이 여기 이 부분에 있는지 확인을 하는 과정인 겁니다. 만약에 여기서 이렇게 끝까지 다 찾았는데 실이 없었다면 아이가 하나 더

증가를 하겠죠. 이번에는 아이는 2가 됐으니까 8에서 2를 빼면 6이 되는 거고 이제 안쪽 포 루프를

통해서 이렇게 순환을 하면서 이 안에서 6이 있는지 찾게 되는 거예요. 그래서 이렇게 여기서 6을 발견을 하게 되면

결국 얘가 이제 6이 되는 거니까 얘와 얘가 같아서 이 조건이 2가 되게 되고 최종적으로 그래서 바로 리턴

트루를 하게 되는 겁니다. 이해가 되시죠? 그러면 이렇게 바뀐 코드를 기준으로 정리를 하면 이렇습니다. 이 코드는 어떻게 동작을 하냐? 이 바깥쪽 포 루프를

사용해서 i가 이렇게 하나씩 증가를 할 때마다 이 안쪽으로 아이 다음번에 있는 그 데이터부터 끝까지 하나하나씩

접근을 해요 그렇게 접근을 한 뒤에 이 조건을 만족하는지 즉 타겟에서 아이가 가리키는 값을 뺀

극값, 극값이 이 안에 있는지 제의를 통해서 이렇게 접근하면서 하나하나씩 확인을 하는 거죠 그렇기 때문에 아이가

이 위치에 있으면 j는 이 부분을 루프를 돌면서 이 값이 있는지 확인을 하는 거고요 그래서 있으면 바로 리턴을 하는 거고

만약에 없으면 아이를 하나 증가시킨 뒤에 다시 한번 이 값을 계산하고 그 값이 이 안에서 존재하는지 하나하나씩

TwoSum 문제를 풀면서 배우는 내가 짠 코드의 성능을 개선하는 과정!! (feat. 코딩 테스트)

8년차 백엔드 개발자가 배워서 남주려고 만든 채널이에요

알기 쉽게 설명합니다

함께 성장했으면 좋겠어요 :)


#컴공맛집 #백엔드전문채널
