방법론 질문 있습니다

세계 대회 진출자가 알려주는 코딩테스트 A to Z (with Python)

BOJ 11054

해결된 질문

작성

101

안녕하세요, 강의를 듣고 계신 여러분!

여러분의 학습을 돕기 위해 질문 안내를 드리고자 합니다.

1. chatGPT를 이용해보기

단순한 의문은 chatGPT를 이용해도 해답을 찾을 수 있는 경우가 종종 있습니다!

2. 강의의 어떤 부분에 대한 질문이고, 어떤 부분이 궁금한지 명확히 알려주세요!

강의의 어느 파트에서 의문을 느끼고, 어떤 부분이 궁금한지를 명확히 제시해 주시면 답변에 도움이 됩니다!
자신은 어떻게 이해했는지 또한 적어주면 좋습니다!

ex) 섹션5의 '그래프 순회 (DFS & BFS) [개념]' 강의에서 DFS와 BFS 모두 그래프의 모든 노드를 탐색하는 알고리즘이라고 하셨고 시간 복잡도 또한 똑같다고 이해했습니다. 그러면 DFS와 BFS 중에서 어떤 알고리즘이 더 효율적인지 구별하는 것은 의미가 없는 것일까요?

어느 파트
- 섹션5의 '그래프 순회 (DFS & BFS) [개념]' 강의
자신은 어떻게 이해했는지
- DFS와 BFS 모두 그래프의 모든 노드를 탐색하는 알고리즘이라고 하셨고 시간 복잡도 또한 똑같다고 이해
어떤 부분이 궁금한지
- DFS와 BFS 중에서 어떤 알고리즘이 더 효율적인지 구별하는 것은 의미가 없는 것일까요?

일단, 강의 내용에서 약간 벗어난 질문이긴 합니다.

백준 11054번 문제를 먼저 풀었는데,

선택하거나 선택하지 않았을 경우를 분리해서

dp1과 dp2를 튜플 쌍으로 갱신해주었는데요,

근데 딱히 필요가 없는데, 하던 대로 하게 된 것 같아서요,,

그래서, 질문은

`구현 없이 생각만으로 타당성을 따져보는 것이

엄밀하고 구체적으로 따져지지 않다보니

생각이 뭔가 추상적이고 편하거나 해오던 방식에서 벗어나지 못하는 것 같습니다.

구체성 있게 따져보는 방법과 정리에 대한 조언 부탁 드려도 될까요??`입니다.

항상 답변 감사합니다.

아래는 참고 코드입니다.

#boj11054
import sys
input = lambda : sys.stdin.readline().rstrip()

n = int(input())
arr = list(map(int, input().split()))
increase = [[0, 0] for _ in range(n)]
decrease = [[0, 0] for _ in range(n)]
total = [0 for _ in range(n)]
for i in range(n):		
	for j in range(i):
		if arr[j] < arr[i]: increase[i][0] = max(increase[i][0], increase[j][0] + 1)
		increase[i][1] = max(increase[j][0], increase[j][1])
for i in range(n, -1, -1):
	for j in range(n - 1, i, -1):
		if arr[i] > arr[j]: decrease[i][0] = max(decrease[i][0], decrease[j][0] + 1)
		decrease[i][1] = max(decrease[j][0], decrease[j][1])
for i in range(n):
	total[i] = max(increase[i][0], increase[i][1]) +  max(decrease[i][0], decrease[i][1])
print(max(total) + 1)

python 코딩-테스트 알고리즘

답변 2

알리 Ally

지식공유자

안녕하세요. zhu님!

모든 문제에 일관되게 적용되는 구체적인 사고과정이나 방법론은 존재하지 않는다는 점을 미리 말씀드리고 싶습니다. 그래서 어려운 코딩테스트 문제를 푸는 것이 쉽지 않은 것은 당연하다고 할 수 있습니다.

실제로, 코딩테스트를 통과하는 대부분의 사람들도 만점으로 통과하는 것은 아니듯이, 코딩테스트에서 어려운 문제의 풀이는 바로 떠올려지는 것이 아닌 기존에 공부했던 지식(알고리즘)과 공부하며 쌓아온 논리적인 사고력(문제해결능력)을 통해서 30분에서 1시간 정도의 고민의 과정을 거쳐 풀이를 떠올린다고 생각하시면 됩니다.

그래서 골드 정도의 문제를 풀 때 풀이가 바로바로 떠오르지 않는다는 것은 코딩테스트 공부을 하는 과정에 있어서 매우 자연스러운 상황이라고 말씀드리고 싶습니다.

물론, 처음부터 잘하는 분들도 존재하나, 그런 분들은 수학적인 사고과정이나 논리적인 사고과정, 컴퓨팅적인 사고과정을 원래 잘했을 가능성이 높습니다.

[문제의 풀이를 떠올리는 데 필요한 것들]

코딩테스트 문제를 풀기 위해선 '알고리즘 개념', '구현력', '문제해결능력'이라고 강의에서 설명드렸는데요. (코딩테스트 공부의 상한선 강의 참조)

이 중에서, 문제의 풀이를 떠올릴 때는 문제해결능력이 중요하다고 할 수 있습니다.

이러한 문제해결능력을 높이는 데에 있어서는 브루트포스, 그리디, DP 알고리즘을 이용한 접근을 많이 연습해보는 것이 도움이 될 수 있습니다.

질문자님처럼 문제를 보고 어떻게 접근해야 할지 감이 안잡하시는 분들은 이 3가지 알고리즘을 통해 문제를 접근하시는 것이 도움이 될 것입니다.

이 3가지 알고리즘을 이용하여 문제를 접근하는 것을 계속 연습하다보면, 문제를 논리적으로(컴퓨팅적으로) 접근하는 과정이 익숙해질 것입니다.

보통 코딩테스트를 어려워 하시는 분들은 논리적이지(컴퓨팅적이지) 않은 사고과정이 습관처런 몸에 베어있는 경우가 많은데요. 이런 분들은 문제를 보고 무의식적으로 나오는 논리적이지(컴퓨팅적이지) 않은 사고과정을 인지하고 바꿔주는 것이 중요합니다.

따라서 위에서 언급한 브루트포스, 그리디, DP 알고리즘을 이용한 접근을 많이 연습하여 논리적인(컴퓨팅적인) 사고과정을 체화하는 것이 중요하다고 말할 수 있습니다.

위에서 언급한 브루트포스, 그리디, DP 알고리즘을 이용한 접근은 필수 알고리즘1 파트와 실전 문제풀이1 파트를 참고하시면 도움이 많이 될 거라고 생각합니다.

더불어 실전 문제풀이2 파트를 통해 실제 코딩테스트 문제를 풀 때 어떻게 접근하여 풀이를 떠올리는지 보시면 좋을 거 같습니다.

[정리]

문제의 풀이를 떠올리는 데는 논리적인(컴퓨팅적인) 사고과정이 중요
대부분의 사람들은 논리적이지 않은 방식으로(느낌적으로) 문제를 접근
논리적인(컴퓨팅적인) 방식으로 문제를 접근하고 푸는 것을 체화할 필요가 있음.
논리적인(컴퓨팅적인) 사고과정은 (강의에 나오는) 브루트포스, 그리디, DP 알고리즘을 이용하여 접근하는 과정을 통해 키울 수 있음.

[추가적으로]

질문자님께서 언급한 구체성 있게 따져보는 방법은 아마 DP Table을 세우고 관계식의 타당성을 판단하는 방법에 대한 질문인 거 같은데요. 자신이 세운 DP 관계식의 타당성을 판단하는 법은 DP Table의 정의에 따른 관계식이 오류가 없다면 DP 관계식이 타당하다고 할 수 있습니다!

예를 들어, dp[n]을 n까지 살펴봤을 때의 최대 길이라고 정의하고 dp[n]을 구하기 위한 관계식을 찾아 봤더니 dp[n] = dp[n - 1] + dp[n - 2] 라는 관계식이 있는 거 같고 실제로 확인해봐도 DP Table 정의인 dp[n]: n까지 살펴봤을 때의 최대 길이라는 것이 맞는 거 같다면 타당하다고 할 수 있습니다.

이렇게 말해도 사실, DP 관계식의 타당성을 판단하려면 어느정도의 사고력이 필요하므로 처음엔 어려운 것이 당연합니다. 따라서, DP 문제들의 풀이 영상들을 보며 DP 관계식의 식이 왜 타당한지를 스스로 코드를 돌려보며 이해하는 과정을 해보시는 것을 추천드립니다. 그렇게 하다 보면, 이후에는 스스로 DP Table을 설계하고 타당한 DP 괸계식 또한 쉽게 찾을 수 있을 것입니다!

또 궁금하신 점 있으시면 언제든 질문 부탁드립니다.

감사합니다. :)

인프런 AI 인턴

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

zhu님의 질문을 확인했습니다. dp를 사용한 문제를 푸는 과정과 생각의 정리 방법에 대해 고민이 많으신 것 같습니다. 단순히 올바른 코드 구현 외에도 문제 해결 접근 방식과 생각 정리 방법에 대한 조언을 원하시는 것 같네요. 관련된 유사한 답변을 찾았습니다.

백준 알고리즘 문제에 대한 조언과 관련된 유사한 질문/답변으로는 다음이 있습니다:

“저.. 시간복잡도 관련 질문입니다.(로직 거의 비슷한 거 같은데, 시간초과가 나서요)”
- 이 질문에는 시간 복잡도 문제 해결에 관한 일반적인 조언이 제공되어 있습니다. 시간 복잡도 및 입력 방법 최적화에 대해서도 언급되어 있습니다.
“시간초과를 자력으로 해결하지 못했습니다 😓”
- 이 질문에서는 스도쿠 문제 해결에 대한 과정에서 시간 초과 문제를 해결하는 방법에 대해 상세히 설명하고 있습니다. 탐색 및 백트래킹 기법의 효율적 사용에 대한 팁도 공유되어 있습니다.

풍부한 설명 추가:

질문에 제공된 코드를 보니 동적 계획법(DP)을 활용해 문제를 푸셨는데, 이 과정에서 구체적인 타당성 검토와 구체성 있는 문제 해결 방안을 원하시는 것 같습니다.

다음 몇 가지 방법을 통해 문제 해결 과정을 조금 더 구체화할 수 있습니다:

문제 정의와 목표 설정:
- 문제를 정확히 정의하고 목표를 명확히 설정하세요.
- 예를 들어, 이 문제의 경우 “최장 바이토닉 부분 수열을 찾는다”가 목표입니다.
입력과 출력을 명확히:
- 입력 구조와 출력 요건을 명확히 이해해야 합니다.
- 예를 들어, 주어진 수열의 길이 n과 수열의 각 요소들이 입력이며, 우리는 가장 긴 부분 수열의 길이를 출력해야 합니다.
하위 문제 정의 및 상태 표현:
- 문제를 더 작은 하위 문제로 나누고 각 상태를 명확히 정의하세요.
- 예를 들어, dp[i]를 i번째 요소를 포함하는 최장 증가 부분 수열의 길이로 정의할 수 있습니다. dp1과 dp2의 역할을 명확히 생각해 보세요.
점화식 세우기:
- 각 상태(즉, dp[i])를 어떻게 이전 상태들로부터 계산할지 점화식을 세워보세요.
- 예를 들어, dp[i] = max(dp[j] + 1) (단, j < i이고 arr[j] < arr[i])
초기 조건과 경계 조건 설정:
- 초기 상태와 경계 조건을 확실히 설정하세요.
- 예를 들어, 모든 dp[i]는 최소 1부터 시작합니다.
구현 후 검증:
- 구체적 예제를 통해 구현한 알고리즘이 올바른지 검증해보세요.
- 예제 수열을 통해 각 단계의 dp값이 어떻게 변하는지 추적해봅니다.

이와 같은 방법론을 통해 문제를 해결하고 생각을 체계화할 수 있을 것입니다. 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

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