구름톤 챌린지 Week 4 - Day 18

https://level.goorm.io/exam/195700/중첩-점/quiz/1

이번에도 여김없이 나온 '틀린 카테고리 문제'다. 무슨 소리냐고? 그래프에서 DP 문제를 냈다는 이야기이다.

3주차 그래프 문제를 4주차에 내고, 4주차 이 문제를 3주차에 내면 되는 거 아닌가... 자꾸 생각이 든다.

문제를 처음 보고 나서 "이게 DP인가?"라는 생각을 했다.

그냥 가로 세로 선 개수를 센 다음에 곱해서 더하면 끝 아닌가...? 브루트 포스 아닌가?

그래서 생각나는 대로 우선 코드를 짰다.

 

import sys
input = sys.stdin.readline


def DrawLine(x, y, dir):
    global square
    x -= 1
    y -= 1
    
    if dir == "U" or dir == "D":
        nx = dx[dr.index(dir)]
        
        while (0 <= x and x < length):
            square[x][y][0] += 1
            x += nx
        
    else:
        ny = dy[dr.index(dir)]
        
        while (0 <= y and y < length):
            square[x][y][1] += 1
            y += ny


length, half_line = map(int, input().split())
square = [[[0, 0] for _ in range(length)] for _ in range(length)]  # horizontal, vertical

# UP, DN, LFT, RGT
dr = ["U", "D", "L", "R"]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

for _ in range(half_line):
    startX, startY, dir = map(str, input().split())
    
    DrawLine(int(startX), int(startY), dir)
    
answer = 0
for x in range(length):
    for y in range(length):
        answer += square[x][y][0] * square[x][y][1]
        
print(answer)

ㅇㅇ

 

# UP, DN, LFT, RGT
dr = ["U", "D", "L", "R"]
dxy = [-1, 1, -1, 1]

dxy를 선언해주었다. 방향에 따른 값을 이용하기 위해 dr을 선언해주었다.

U, D, L, R 중 하나의 방향을 dr에서 index로 찾는다. 그리고 index에 맞춰 dxy를 변경한다.

이때 dx, dy로 선언하지 않고, dxy의 0이 없는 list를 선언한 이유는 간단하다.

가로 선과 세로 선은, 다른 한 축이 움직이지 않기 때문이다.

가로가 움직일 때는 세로가 가만히 있고, 세로가 움직일 때는 가로가 가만히 있는다.

이동을 할 때 둘 중 하나만 이동해주면 되기 때문에 한 번에 선언해도 상관이 없다.

 

if dir == "U" or dir == "D":
    nx = dxy[dr.index(dir)]

    while (0 <= x and x < length):
        square[x][y][0] += 1
        x += nx

else:
    ny = dxy[dr.index(dir)]

    while (0 <= y and y < length):
        square[x][y][1] += 1
        y += ny

sqaure는 사각형의 3차원 list이다. 2차원으로 가장 먼저 크기에 맞춰 선언한다.

그 다음 각 요소를 가로 선과 세로 선을 각각 저장한 하나의 list로 선언한다. 결과적으로 3차원이 된다.

세로 선을 0번째 index 값으로, 가로 선을 1번째 index 값으로 취급한다.

현재 위치부터 시작하여 범위 내에 있다면  while문으로 해당 직선에 1을 더해준다.

U와 D의 경우 x값만 바뀌는 것이기에 x += nx 연산만 해주면 된다.

L과 R의 경우 y값만 바뀌는 것이기에 y += ny 연산만 해주면 된다.

 

answer = 0
for x in range(length):
    for y in range(length):
        answer += square[x][y][0] * square[x][y][1]
        
print(answer)

DrawLine() 함수 연산 이후, 각 sqaure 칸은 가로 세로 선의 개수가 있다.

그럼 모든 경우에 두 값을 곱한 뒤, 더해주면 정답이다.

 

하지만 의문이 들었다.

선을 어떻게 그리는지 정보가 주어지고, 그대로 따라가 선을 그려준다. (값을 업데이트한다.)

그런 다음 모든 칸에 대해서 돌면 DP가 아니라 Brute force가 아닌가?

하여 정해 코드에 대해 이것이 왜 DP인지 질문해보았다.

구름은 어떤 측면에서 DP라고 생각하는 걸까?

 

질문에도 썼지만, DP의 핵심은 caching이다.

그것이 memoization이든 tabulation이든 어쨋든 같은 연산을 방지하기 위한 저장이다.

구름은 모든 선을 그려 미리 값을 저장하는 것 자체를 caching으로 본 거다.

 

구름 입장에서 Brute force가 되려면 모든 경우를 하나하나 탐색해야 한다고 한다.

선 정보를 모두 저장한 다음, 이중 반복문으로 모든 칸을 순회한다.

순회하면서 그때그때 선 정보를 확인하여 중첩 점이 몇 개인지 확인한다.

그럼 특정 반직선에 대해 여러 번 계산하는 경우가 생길 것이다. 이것이 Brute force라는 거다.

이런 같은 연산을 방지하고, 값을 저장하여 해답에 접근했으니 DP라는 것이다.

 

이 부분에 대해서 약 1시간가량 친구와 토론을 했다.

DP란 결국 무엇인가,  저것은 단순한 추상화(의사 코드; 개념을 그대로 코드로 옮긴 것)는 아닌가,

접점의 개수를 구하기 위해 저장한다는 것을 어떤 측면에서 바라보아야 하는가,

특정 상황에서 문제를 해결하기 위한 알고리즘을 이분법으로 분류할 수 있는가,

과거의 상태를 불러왔다고 말할 수 있는가, 내가 옳다고 생각한 것이 정말로 옳은가,

알고리즘의 시시비비를 확인하기 전 이 문제에서 본질(핵심)은 과연 무엇인가.

 

장황하지만, 요약하자면 '코에 걸면 코걸이 귀에 걸면 귀걸이'다.

'문제'라는 것은 '정답을 구하기 위해 책에 있는 잘 정리된 정보' 만 있는 게 아니다.

일상생활에서 다툼일 수도 있고, 누구도 해결하지 못한 어려움일 수도 있다.

또한, 다양한 이해관계가 얽힌 상황일 수도 있으며, 생각보다 간단한 기본일 수도 있다.

즉, 용어에 함몰되어 이게 맞는지?를 아는 것보다 이 상황의 문제는 뭐지?를 아는 것이 중요하다.

우리에게 주어지는 '문제'는 알고리즘 분류만으로 표기할 수 없는 경우가 태반이다.

 

본인이 옳다고 믿는 것을 옳지 않다고 생각할 의지가 필요하다.

다양한 문제를 해결하고 발전하기 위해서는, 각양각색의 의견을 경청해야 한다.