인프런 커뮤니티 질문&답변

빠른 시간 내에 상세하게 설명해주셔서 너무 감사합니다ㅠㅠ

틈틈이 시간 날 때마다 열심히 듣고 있습니다:)

응원해주셔서 감사합니다☺

안녕하세요, jinii915님!

전체적으로 코드를 잘 짜주셨는데요.

해당 문제는 브루트포스적으로는 못 풀고, 효율적인 풀이를 찾아야 하기 때문에 그리디한 사고를 더해서 O(N) 풀이로 해결해야 했는데요.

강의에서는 그리디한 사고를 더한 풀이라고 했지만, 질문자님께서 말하셨듯이 백트레킹 풀이라고 생각하셔도 됩니다.(명칭은 중요하지 않습니다) 어쨌든 중요한 것은 강의에서의 정답 풀이 아이디어와 질문자님이 생각해 내신 아이디어가 똑같으며 시간 복잡도를 만족하는 풀이라는 것입니다! 따라서, 문제 접근을 아주 잘하신 것 같습니다!

결론부터 말씀드리면, 아주 잘하셨고 실제 코딩테스트에 나온 문제라면 통과하셨을 것입니다. 단지, 백준에서 통과하지 못한 이유는 해당 문제는 파이썬이 느림을 배려해 주지 않은 문제인 것으로 보입니다. 즉, 질문자님께서 구현하신 코드가 강의에 나온 코드보다 구현 효율성이 좀 떨어진 것으로 보입니다.

그러한 이유로 질문자님 코드에서 살짝 더 효율적으로 바꾼 아래의 코드는 아슬아슬하게 통과하였습니다.
(입력을 arr에 받지 않고 바로 처리하였으며, 재귀 함수의 else 부분이 살짝 다릅니다.)

import sys
sys.setrecursionlimit(10**6)  # 재귀 깊이 제한 늘리기

def recursion(value, left, right, count):
	# base
	if count > 1:
		return 2
	if left > right:
		return count

	# recursive
	if value[left] == value[right]:
		return recursion(value, left+1, right-1, count)

	else:
		# 1. right를 옮겨보기
		skip_right = recursion(value, left, right-1, count+1)
		# 2. left를 옮겨보기
		skip_left = recursion(value, left+1, right, count+1)

		return min(skip_left, skip_right)


T = int(input()) # 문자열 개수

for _ in range(T):
	value = input()
	left = 0
	right = len(value)-1
	print(recursion(value, left, right, 0))

해당 문제의 시간 제한이 1초인데, 딱 1초로 아슬아슬하게 통과하는 모습이다...

이번 문제는 (파이썬을 배려해 주지 않은 문제여서) 운이 없었던 것으로 보이므로, 이번 문제가 시간 초과(또는 메모리 초과)를 나는 이유에 대해 깊게 생각하시지 않고 넘어가셔도 무방할 것 같습니다.

그래도, 질문자님이 작성해주신 질문이나 코드를 보며 제가 알려드리면 좋을 것 같은 내용은 아래에 작성하오니 참고해 주시면 될 것 같습니다!

[질문자님의 코드를 메모리 초과가 아닌 시간 초과로 봐야 하는 이유]

질문자님의 제출 기록을 보니 PyPy3로 제출했을 때 메모리 초과가 났기 때문에, 질문에서 메모리 초과라고 언급해 주신 것 같은데요. 사실, 이는 시간 초과로 보는 것이 타당합니다. 왜냐하면, Python3로 제출했을 때는 시간 초과가 떴기(PyPy3로 제출했을 때만 메모리 초과가 떴기) 때문이죠.

사실 PyPy3로 컴파일하면 Python3로 컴파일했을 때보다 빠른 이유는 메모리를 더 많이 사용해서 속도를 올리는 전략을 사용하기 때문입니다. 따라서, 질문자님의 코드도 "Python3로 제출했을 때 메모리초과가 나지 않았지만, PyPy3로 제출했을 때는 메모리를 더 사용하여 속도를 올리려다 보니 메모리 초과가 났다"라고 생각하시면 될 것 같습니다.

[강의의 정답 코드가 질문자님 코드보다 효율적인 이유]

강의에서 정답 코드와 질문자님의 코드 차이점은 회문인지를 검사하는 함수를 for문으로 구현하였느냐, 재귀함수로 구현하였느냐인데요. 회문을 검사하는 함수를 작성할 때는 for문으로도 구현 가능하며, 재귀함수로도 구현 가능합니다. 똑같은 로직을 for문과 재귀함수 중에서 어떤 것으로 구현하는 게 더 빠를까요? 당연히, for문이 빠릅니다. 그러한 이유는 재귀함수를 호출할 때는 for문에 비해 추가적으로 잡다한 작업(스택 메모리에 여러 정보들을 저장하는 작업)이 걸리기 때문이라고 생각해주시면 될 것 같습니다.

따라서, 앞으로는 for문으로 구현 가능한 로직이면 재귀 함수보단 for문을 이용하여 구현하는 것을 추천드립니다!

사실, 질문자님의 코드도 C++로 작성하였다면 무난하게 통과할 것이기 때문에, 사실 코딩테스트에 이런 문제가 나왔다면 해당 코드로도 통과를 하였을 것입니다. 따라서, 이번 문제를 틀린 이유는 코드를 효율적으로 작성하지 않아서 보단 백준에서 파이썬 제출에 대한 배려를 해주지 않아서 가 더 적합한 이유라고 생각이 듭니다!!

질문하신 내용과 코드를 보니 강의를 잘 따라 오시는 것 같고, 문제 접근 또한 잘하고 계신 것 같습니다. 끝까지 화이팅입니다!!

질문에 대해 만족스러운 답변이 되었기를 바랍니다!

추가로 궁금하신 점이나 더 자세한 설명이 필요하시다면 언제든지 말씀해 주세요. 😄

5점 수강평을 남겨주시면 향후 더 나은 강의를 만드는 데 큰 도움이 됩니다. 🌟

안녕하세요, 인프런 AI 인턴입니다.

님의 질문에 도움을 드리기 위해 비슷한 맥락의 문제들을 참고하였습니다. 일반적으로 투 포인터와 재귀를 비교하면 다음과 같은 차이점을 발견할 수 있습니다:

1. 투 포인터 알고리즘:

   • 투 포인터는 반복문을 사용하여 양쪽 끝에서 시작해 중앙으로 수렴하는 방식입니다.
     
   • 주로 시간 복잡도가 O(n)으로, 메모리 사용이 상대적으로 적습니다.
     
   • 순차적으로 진행되므로, 메모리 초과 문제가 드물게 발생합니다.
     

2. 재귀:

   • 재귀는 함수가 자기 자신을 호출하는 방식입니다. 문제의 구조가 트리 형태일 때 편리하게 사용됩니다.
     
   • 메모리 사용량은 호출 스택에 함수의 복사본이 남기 때문에 재귀 깊이가 클수록 많은 메모리가 필요하며, base case에 잘못 설정된 경우 무한 반복이 되어 stack overflow가 발생할 수 있습니다.
     
   • 주어진 문제에서 루프보다는 분기 처리가 많아질 수 있어, 메모리 사용이 증가할 수 있습니다.
     

님이 작성하신 코드에서 메모리 초과가 일어나는 이유는 대부분 재귀 호출이 너무 깊거나, 재귀를 통한 분기가 많을 경우에 나타날 수 있습니다. 이는 재귀가 본질적으로 브루트포스적인 접근 방식을 가지기 때문입니다.

결론적으로, 재귀를 사용하는 것은 직관적일 수 있으나, 메모리 및 시간 복잡도를 고려했을 때 투 포인터 알고리즘이 이 문제에서는 더 효율적인 방법입니다. 투 포인터는 메모리 사용이 적고 시간 효율성이 좋기 때문에 대규모 데이터에도 적합합니다.

비슷한 문제를 투 포인터로 푸는 방법에 대한 기존의 답변을 참고하고 싶으시면 아래 링크를 추천해드립니다:

• 투 포인터를 이용한 회문 문자열 검사 방법
  

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.