이모스 관련 질문

Question

안녕하세요. 선생님! 백준 17611번 코드를 아래와 같이 작성했는데, 계속 고쳐봐도 "틀렸습니다"만 돌아와서 질문 남깁니다... 코드가 너무 더러워서 최대한 주석을 달아봤는데.. 이해하시는 데 도움이 됐으면 하는 마음입니다 ㅠㅜ from collections import defaultdict import sys input = sys.stdin.readline # input n = int(input()) arr = [] min_x, min_y = sys.maxsize, sys.maxsize dicH, dicV = defaultdict(list), defaultdict(list) for _ in range(n): x, y = map(int, input().split()) # 꼭지점 입력 dicH[x].append(y) # 수평으로 선분을 위치한다고 생각하고 그래프를 시계방향으로 90도 돌렸을 때 높이마다 존재하는 선분의 양 꼭지점을 모아둔 리스트 dicV[y].append(x) # 수직으로 선분을 위치한다고 했을 때, 높이마다 존재하는 선분의 양 꼭지점을 모아둔 리스트 min_x, min_y = min(min_x, x), min(min_y, y) # 높이마다 꼭지점을 정렬 for key in dicH: dicH[key] = sorted(dicH[key]) for key in dicV: dicV[key] = sorted(dicV[key]) # 누적합을 할 리스트 생성 prefixX, prefixY = [0 for _ in range(1_000_001)], [0 for _ in range(1_000_001)] # 이모스 적용 for key in dicH: length = len(dicH[key]) # 각 높이마다 꼭지점의 개수를 구하고 temp = 0 while temp < length - 1: # 꼭지점을 두 개씩 짝지어 1과 -1 추가 prefixY[dicH[key][temp] - min_y] += 1 # 누적합 리스트에 값을 올바른 위치에 추가하기 위해 min_y를 빼 시작점이 0이 되도록 함 prefixY[dicH[key][temp + 1] - min_y] -= 1 temp += 2 # 완료하면 두 칸 이동 for i in range(1, 1_000_001): prefixY[i] += prefixY[i - 1] for key in dicV: length = len(dicV[key]) temp = 0 while temp < length - 1: prefixX[dicV[key][temp] - min_x] += 1 prefixX[dicV[key][temp + 1] - min_x] -= 1 temp += 2 for i in range(1, 1_000_001): prefixX[i] += prefixX[i - 1] h = max(prefixY) v = max(prefixX) print(max(h, v))

코딩 센세 · Answer

제 정답 코드입니다!   참고 부탁드립니다! # https://www.acmicpc.net/problem/17611 # 관찰 : # 수직이동, 수평이동이 반복된다. # 위로 기둥이 나오면, 이어서 아래로 기둥이 나온다. # 가장 우측 지점에 도달하면 suffix로 변경된다. ( 하지만 무시해도 계산된다. ) # 개똥벌레 문제랑 동일한 로직이지만, 수직 + 수평 2번 반복된다. # 아이디어 : # 먼저 횡이동을 무시하고 모든 기둥을 나열해서 카운팅 해준다. # -500,000 ~ 500,000 hn = [0]*1001000 wn = [0]*1001000 # 입력을 먼저 받는 방법(o) # 입력을 받으면서 하는 방법 height = [] width = [] for n in range(int(input())): x, y = map(int, input().split()) y = y + 500000 x = x + 500000 width.append(x) height.append(y) maxW = max(width) minW = min(width) maxH = max(height) minH = min(height) #마지막줄은 계산하지 못하기 때문에 미리 더해주고 빼준다. a1, b1 = width[0],width[-2] a2, b2 = height[0],height[-2] wn[min(a1,b1)] += 1 wn[max(a1,b1)] -= 1 hn[min(a2,b2)] += 1 hn[max(a2,b2)] -= 1 #반복문을 돌려서 프리픽스를 하기 위해 1과 -1을 더해준다 for i in range(n-1): # 홀수는 무조건 x값은 동일, y값만 변경된다. # if i % 2 == 0: a = min(height[i], height[i+1]) b = max(height[i], height[i+1]) if a != b: hn[a] += 1 hn[b] -= 1 # 짝수는 반대다! # if i % 2 == 1: c = min(width[i], width[i+1]) d = max(width[i], width[i+1]) if c != d: wn[c] += 1 wn[d] -= 1 #프리픽스 배열을 만든다. prefix_h = [0]*1001000 prefix_w = [0]*1001000 # 정답을 출력한다. # answer = 0 for h in range(minH-2, maxH): prefix_h[h+1] = prefix_h[h] + hn[h+1] # print("h",prefix_h[h+1]) # answer = max(answer, prefix_h[h+1]) for k in range(minW-2, maxW): prefix_w[k+1] = prefix_w[k] + wn[k+1] # print("k",prefix_w[k+1]) # answer = max(answer, prefix_w[k+1]) print(max(max(prefix_h),max(prefix_w)))

인프런 AI 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. kyg8821님, 백준 17611번 문제에서 &ldquo;틀렸습니다&rdquo;가 뜨는 원인을 함께 찾아보겠습니다. 주어진 코드를 분석해보면 이모스 알고리즘을 사용하여 문제를 해결하고자 하셨네요. 이모스 알고리즘은 많은 구간에 대한 누적합을 효율적으로 계산할 때 유용한 방법입니다. 이를 통해 구간별로 선분의 개수를 찾아내 최대를 구하는 문제 해결 방식을 채택하셨습니다. 코드 내에서 각 꼭지점을 수직, 수평 선분 리스트에 추가하고, 누적합 리스트(prefixX, prefixY)를 생성하여 이모스 알고리즘을 적용하고, 각각의 누적합 배열에서 최댓값을 구하여 그 중 더 큰 값을 결과로 출력하고 있습니다. 문제의 조건에 따라 이 같은 풀이 방식이 적합할 수 있으나, &ldquo;틀렸습니다&rdquo; 결과가 나타나는 것은 코드 내에 논리적 오류가 존재할 가능성이 있습니다. 오류를 찾기 위해 다음 사항들을 확인해볼 수 있습니다. - 입력받은 선분 정보가 정확하게 처리되고 있는지, - 선분의 시작과 끝을 표시할 때 짝지어 처리하고 있는 부분이 올바르게 구현되었는지, - 누적합을 구할 때 모든 필요한 범위를 고려하고 있는지, - 수평과 수직 선분의 누적합을 구하는 과정에 예외 사항 없이 올바르게 구현되었는지 확인해보시기 바랍니다. 또한, 테스트 케이스를 몇 가지 예외적인 상황으로 추가하여 제대로 동작하는지 살펴보시고, 선분 정보를 입력받을 때 조건에 맞게 처리하는 부분이 있는지도 재검토해볼 필요가 있습니다. 위 사항들을 면밀히 점검하시고, 그래도 문제를 찾지 못할 경우 해당 강의의 커뮤니티 질문&답변 게시판을 통해 질문하신다면 강사님께서 더욱 상세한 답변을 제공해 주실 수 있을 것입니다. 도움이 필요하시면 언제든 문의해주시고, 앞으로도 알고리즘 공부에 많은 성취가 있기를 바랍니다!