알고리즘 코딩 테스트 문제 풀이 시 반드시 알아야할 것 (꿀팁, 속도, 성능, 최적화, 개발자, 취업, 신입, 경력, 이직, 코테 준비)

 

👋 

안녕하세요~ 위대한 개취비입니다!

오늘은 제가 한달이 넘는 시간동안 꾸준히 알고리즘 문제를 브론즈 난이도부터 현재 골드 난이도까지 풀면서 알게된 점에 대해서 공유하려고 합니다.

 

기준 언어는 알고리즘 문제 풀이에 가장 많이 쓰이는, 파이썬입니다.

 

많은 분들이 표준 자료구조, 표준 라이브러리가 있다는 것은 알고 계실텐데요.

 

있다고 알고 있음에도 이를 활용하지 않으시는 분들이 많다는 것도 알고 있습니다.

저 또한, 이를 활용하지 않고 있었는데요... 😅

 

표준 라이브러리

저는 보통 순열이나 조합, 팩토리얼 등 기본 알고리즘, 로직들을 직접 구현해서 푸는 편인데요.

근데, 이렇게 풀면 성능이 너무 구려요. 구현하는 시간도 더 오래 걸리구요.

 

1. 간단한 예시

1-1. sum 직접 for문을 돌리며 계산

A = [1, 2, 3, 4, 5]
Sum = 0

for n in A:
    Sum += n

print(Sum)

 

1-2. 내장함수 sum 활용

A = [1, 2, 3, 4, 5]
Sum = sum(A)

print(Sum)

 

위 두 코드 중 어떤 것이 빠를까요?

• 위처럼 요소의 수가 적을 때는 그 차이가 크지 않을 수 있어요.
• 즉, 난이도가 쉬운 문제에 대해서는 그냥 계산을 해도 아무런 문제가 없어요.
• 하지만, 난이도가 어려운 문제일수록, 요소의 개수가 많아질수록 성능 차이가 매우 커져요.

 

2. 개취비가 깨달음을 얻은 예시

2-1. 누적합 직접 for문을 돌리며 계산

A = [1, 2, 3, 4, 5]
Sums = [0]

for n in A:
    Sums.append(Sums[-1] + n)

print(Sums)

 

2-2. 표준 라이브러리 itertools - accumulate 활용

import itertools
A = [1, 2, 3, 4, 5]

Sums = list(itertools.accumulate(A, initial=0))
print(Sums)

 

위 두 코드 중 어떤 것이 빠를까요?

• 당연히 itertools를 활용하는 것이 훨씬 빠릅니다...
• 구현을 하는 것도 훨씬 쉽구요! 😎

 

표준 자료구조

저는 보통 자료구조는 어떤 것이든 기본 Array( [ ] )로 구현하는 편인데요.

근데, 문제의 난이도 및 레벨이 올라갈수록 이렇게 풀면 안되겠다는 것을 절실히 깨닫고 있어요.
기본 배열로 풀면 시간초과가 나지만, 표준 자료구조를 사용하면 풀리는 문제가 나오기 시작했거든요...! 😭

 

개취비가 깨달음을 얻은 문제 : 토마토

• BFS 문제이다.
• BFS에는 기본적으로 Queue 자료구조가 필요하다.
• BFS 문제를 풀 때 보통 기본 배열로 구현했었다. 이번에도 그렇게 풀었다.
• 시간초과가 난다. (물론, 내 로직에도 개선점이 있긴 하겠지만...)
• 그런데, 자료구조 하나만 queue.Queue()로 바꿨을 뿐인데 문제가 풀린다.

 

결론

• 문제를 풀 때 표준 라이브러리와 표준 자료구조를 활용하는 게 맞는 것 같다.
• 문제 자체도 그렇게 설계가 되어 있는 것 같다.
• 쉬운 문제라면 어떻게 풀어도 풀리지만, 어려워질수록 이미 누군가 잘 최적화하여 설계한 표준 라이브러리, 표준 자료구조를 활용하는 게 내 심신 안정에 도움이 된다.
• 하지만, 기본 원리를 먼저 알고 적용해야 응용력이 뒷받침된다!

 

👏

자, 이렇게 표준 자료구조와 라이브러리에 대한 저의 깨달음을 공유드려봤습니다... 여러분들은 저와 같은 시행착오 없이 바로 표준 자료구조와 라이브러리에 대해 공부하고 적용하셨으면 좋겠다는 마음으로 이렇게 공유 드려봅니다.

 

코딩테스트 준비를 조금이라도 더 즐기면서 하는 방법에 대해서도 작성해둔 포스트가 있으니 참고해주세요!

https://gatchbee.tistory.com/40

알고리즘 코딩 테스트 즐기면서 준비하는 방법 (백준, solved.ac)

 

더 많은 도움을 얻고 싶으시다면! 아래 단톡방으로 찾아와주세요!

https://open.kakao.com/o/gbuVErVf

LG CNS 현직자 Q&A 2024