11653번: 소인수 분해, 나의 잘못된 접근법과 내가 놓친부분

https://www.acmicpc.net/problem/11653

11653번: 소인수분해

 

소인수 분해를 문제를 풀면서 두가지 접근 방법을 생각하였다

 

1) 재귀

2) 단순 반복문

 

우선 문제를 파악해보자

 

문제 : 정수 N이 주어졌을때 소인수분해하는 프로그램을 작성하시오

 

입력 : N(1<= N <= 10000000)이 주어진다

 

출력 : N의 소인수 분해 결과를 한 줄에 하나씩 오름차순으로 출력한다. N이 1인 경우 아무것도 출력하지 않는다.

 

예제 입력 

72

예제 출력

2

2

2

3

3

예제 입력 

3

예제 출력

3

 

결론적으로 말하면 입력된 수에 대해서 소인수 분해 과정을 출력하라는 의미가 된다.

 

처음에 재귀를 통해서 접근했을때는 다음과 같이 코드를 작성하였다.

 

import sys

numb = int(input())
nbs = list()
div = 2

def divide(n,div):
    if n  == 1:
        return
    elif n == div:
        nbs.append(div)
        return 
    elif n // div == 1:
        nbs.append(n)
        return 
    elif (n % div) == 0:
        nbs.append(div)
        return divide(n // div,div)
    else:
        return divide(n,div + 1)


if __name__=='__main__':
    sys.setrecursionlimit(10000000)
    divide(numb,div)

    for e in nbs:
        print(e)

 

파이썬은 기본적으로 재귀를 1000회로 제한하고 있다. 처음에 재귀 횟수 제한을 조정하지 않았을때는 

 

RecursionError: maximum recursion depth exceeded in comparison

 

라는 에러가 떴었다. 특정 테스트 케이스에 의해서 재귀 횟수가 1000번이 넘었고 그로 인해 코드가 멈춘것이다. 재귀 제한을 조정 후에는 '세그먼테이션 오류'가 났다. 세그멘테이션 오류가 나는 이유를 간단하게 정리해보면 아래와 같다

 

지역변수, 함수 호출 정보는 스택 영역이라는 곳에 만들어준다. 스택 영역은 변수, 함수 호출이 쌓인 후 함수 종료시 사라져 가는 원리이다. 이 스택 영역은 제한이 되어있는데(리눅스 8mb) 이 8mb를 넘어버리고 stack overflow가 발생해 버린것이다.그로 인해 세그멘테이션 오류가 발생한 것이다. 

 

재귀함수를 통한 접근법이 잘못되었던 이유가 바로 이 지속적인 함수호출로 인한 스택 메모리 영역과 관련되어 잘못되었다고 생각이 든다. 또한 재귀함수의 문제점중 하나는 자신을 다시 호출하면서 생성하는 변수는 새로 생성하는 변수인데, 이는 메모리 문제를 발생시키는 원인중 하나인데, 알고리즘 문제에는 '메모리 제한'이라는 것이 있다. 그렇기 때문에 이 문제가 아니더라도 재귀에 의해 메모리 제한에 걸릴수도 있다는것을 다시 깨달을 수 있었다.

 

그래서 다른 방법으로 접근해본것이 함수 호출없는 단순 반복문이었다.

 

numb = int(input())
#입력된 수가 1인 경우 아무것도 출력하지 않는다.
divisor = 2
while numb != 1:
    if numb % divisor == 0:
        print(divisor)
        numb = numb // divisor
    else:
        divisor += 1

 

함수호출 없이 단순히 반복하면서 조건에 만족하는 경우만 검사하는 방법이다. while문의 조건문 numb != 1을 한 이유는 문제에서 주어졌듯이 1일경우에는 아무것도 출력하지 말라고 한데 이유가 있다. 단순 반복문을 통해 해결한 결과 문제의 정답이 되었다.