효율을 높이는 방법 - 반복되는 규칙

나의 습관(사족)

나는 알고리즘을 풀 때 문제에서 주어진 과정 그대로 따라 푸는 방식을 선호한다. 그래서 효율성을 요구하는 문제에서 자주 막히게 된다. 사실 이러한 문제는 알고리즘 자체보다는 문제 해결 논리 자체에 대한 센스를 평가하는 경우가 많다. 그래서 내가 푼 코드에서 사용한 자료구조를 바꾼다거나 약간의 알고리즘을 변경한다고 해서 풀리는 경우는 거의 없다.(재귀 -> 큐 또는 스텍의 경우 풀리는 경우가 많다.)

 

또 자료구조나 알고리즘을 평가하는 문제같은 경우 풀면서 감이 잡히고 비슷한 유형을 보면 바로 해결할 수라도 있지만 효율성 문제들의 경우 유형이 정해진 것이 아니라서 매번 풀 때마다 늘 새로움을 느낀다.

 

사실 위의 말은 내 핑계일 수도 있지만 내게 어려운 걸 어렵다고 얘기하는 게 잘못된 것은 아니지 않은가. 어쨌든 이런 나지만 효율성 문제도 유형이 있다고 생각한다. 앞으로 다양한 효율성 문제들을 보면서 거기서 쓰인 논리를 바탕으로 정리해 나가면 더 빠르게 문제를 해결할 수 있지 않을까 싶어 정리해보려 한다. 재밌기도 하고......

 

묶어서 생각

비효율적인 코드 예시

for i in range(n):
    if i % 2:                 
        print('-', end='')
    else:
        print('+', end='')

위의 코드는 0부터 n-1까지 짝수이면 '-'를 홀수이면 '+'를 출력하는 코드이다. 만일 이와 같은 문제였으면 나는 십중팔구 이렇게 풀었을 거다. 하지만 아래의 효율적인 코드를 보자.

효율적인 코드 예시

for _ in range(1, n // 2 + 1):
    print('+-', end='')
    
if n % 2:
    print('+', end='')

위의 코드는 '+-'를 동시에 출력하고 마지막 원소(n-1)가 짝수이면 '+'를 한번 더 출력한다.

우선 0부터 n까지의 수는 짝수와 홀수를 반복한다. 이를 이용해서 매번 짝수인지 홀수인지 검사를 할 필요없이 그저 몇번 반복하는 지만 알면된다.

 

위의 예시에서 알 수 있듯이 문제에서 어떠한 규칙을 찾고 또 이 규칙이 반복되는 것이라면 효율적인 코드를 다시 생각해 볼 수 있다. 내가 반복되는 규칙이라고 부제목을 붙인 이유가 바로 여기에 있다. 끄읕

참고

http://www.yes24.com/Product/Goods/91219874

Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편 - YES24