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

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

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

1. chatGPT를 이용해보기

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

   

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

• 강의의 어느 파트에서 의문을 느끼고, 어떤 부분이 궁금한지를 명확히 제시해 주시면 답변에 도움이 됩니다!

• 자신은 어떻게 이해했는지 또한 적어주면 좋습니다!

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

• 어느 파트

  • 섹션5의 '그래프 순회 (DFS & BFS) [개념]' 강의

• 자신은 어떻게 이해했는지

  • DFS와 BFS 모두 그래프의 모든 노드를 탐색하는 알고리즘이라고 하셨고 시간 복잡도 또한 똑같다고 이해

• 어떤 부분이 궁금한지

   

  • DFS와 BFS 중에서 어떤 알고리즘이 더 효율적인지 구별하는 것은 의미가 없는 것일까요?

안녕하세요!

강의 잘 듣고 있습니다.

백준 1461 그리디 마지막 문제에 대한 질문이 있는데요.

보기 전에 풀어보긴 했는데,

두더지 잡다가 어떻게 된 느낌이긴 해요..

음,, 아직 습관이 안 고쳐지기는 했는데 정의하고 분석하고 따져보고 그려본 다음에 해야 하는데,,

그 제가 처음 푼 방식은

리스트 요소를 지워가며 해결하는 방식인데요

1. 양/음수가 m으로 떨어지지 않는 나머지 경우를 먼저 따져 합계에 더하고, 제거한 뒤

2. 먼 데부터 다녀오는데, 최댓값을 계속 갱신해서

3. 가장 먼 거리를 나중에 빼주는 방식으로 했어요..

m으로 나누어 떨어지지 않는 경우에 대한 처리를 나중에 추가했는데요

선생님의 코드가 어떻게 그 경우도 잘 처리하는 지 분석이 잘 안되어서..

설명 부탁 드려요..

아! 저번 설명 너무 감사합니다

• 더불어 약간 공부하는 루틴?이랄까? 그런 것도 말씀해 주실 수 있는 게 있다면 혹시 말씀 부탁드려요..(코테 공부도 그렇고 다른 것도 그렇고..)

아래는 제가 처음 정답 받은 코드입니다.

(코드가 지저분함에 죄송해요..)

import sys
input = sys.stdin.readline

# 방향을 결정하고 상자 들고 다음에 처음 갈 책 위치를 반환합니다.
def getPos(arr):
	global direction
	maximum = max(map(abs, arr))
	if maximum in arr: 
		if len(arr) > m:
			direction = False
			if min(arr) >= 0: 
				direction = True
				return 0
			for i in range(len(arr) - 1, -1, -1):
				if arr[i] < 0: return i
		else:
			direction = True
			for i in range(len(arr)):
				if arr[i] >= 0: return i
	else: 
		if len(arr) > m:
			direction = True
			if max(arr) < 0:
				direction = False
				return len(arr) - 1
			for i in range(len(arr)):
				if arr[i] >= 0: return i
		else:
			direction = False
			for i in range(len(arr) - 1, -1, -1):
				if arr[i] < 0: return i
	return -1

n, m = map(int, input().rstrip().split())
arr = list(sorted(map(int, input().rstrip().split())))

cnt = 0; direction = True; reach = 0; plusCount = 0; minusCount = 0

#양수/음수 따로 헀어야 좋았는데, 하다보니 개수 세는 걸 만들었어요..
def count():
	global plusCount, minusCount
	for i in arr:
		if i >= 0: plusCount += 1
		elif i < 0 : minusCount += 1

count()

#양수 m으로 나누어 떨어지지 않을 경우에 대한 처리입니다.
if plusCount % m != 0:
	mini = min(i for i in arr if i >= 0)
	idx1 = arr.index(mini)
	idx2 = min(arr.index(mini) + (plusCount % m), len(arr))
	reach = arr[idx2 - 1]
	for i in range(idx1, idx2):
		arr.remove(arr[idx1])
	cnt += reach * 2

#음수 m으로 나누어 떨어지지 않을 경우에 대한 처리입니다.
if minusCount % m != 0:
	maxi = max(i for i in arr if i < 0)
	idx1 = arr.index(maxi)	
	idx2 = max(arr.index(maxi) - (minusCount % m), -1)
	far = abs(arr[idx2 + 1])
	for i in range(idx1, idx2, -1):
		arr.remove(arr[idx2 + 1])
	cnt += far * 2
	reach = max(reach, far)

# 이럴 필요 없는데, 돌면서 먼 데 구하고 그 안쪽? 지우는 방식으로 했어요..
while arr:
	pos = getPos(arr)
	far = abs(arr[min(len(arr) - 1, pos + m - 1) if direction else max(0, pos - m + 1)])

	for i in range(m):
		if not arr: break
		arr.remove(arr[pos])
		if not direction or pos == len(arr): pos = max(pos - 1, 0)
	cnt += far * 2
	reach = max(reach, far)

print(cnt - reach)