[구름톤 챌린지 Week4(2)] 시뮬레이션, 구현시 주의점, 챌린지 마무리

어느덧 챌린지의 마무리!

주의 - 실수값 오차

실수값끼리 == 를 이용해 비교하는 것은 아주 위험하다고 합니다.

생각해보면 컴퓨터는 디지털, 즉 digit 단위이기 때문에 결코 연속적일 수가 없습니다.

실수를 표현할 때는 어쩔 수 없이 오차가 생길 수 밖에 없다는 의미입니다. 따라서 두 실수값의 차이가 어떤 작은값(아주 작은 값, 가령 1e-8 보다 작다면, 같은 값으로 간주하겠다는 의미로 볼 수 있습니다.

다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍은 복잡한 문제를 작은 하위 문제로 나누어 해결하는 방법입니다. 이 방법은 주로 최적화 문제에 사용되며, 하위 문제의 답을 저장하여 불필요한 계산을 줄입니다. 다이나믹 프로그래밍은 주로 표나 배열을 사용하여 문제를 풀며, 이를 '메모이제이션'이라고도 합니다.

 

시뮬레이션 문제

코딩테스트에서 시뮬레이션 문제란, 주어진 규칙이나 알고리즘을 코드로 구현하여 문제를 해결하는 유형입니다. 이러한 문제에서는 요구하는 시나리오를 정확하고 꼼꼼하게 구현하는 능력이 중요하다고 생각합니다.

#### 예시 코드 흐름(18일차)

1. 명령을 `M`번 반복합니다.
2. 각 명령에 대해 시작 위치 `(y, x)`와 방향 `d`를 입력받습니다.
3. 입력받은 `d`에 따라 배열 `arr`을 업데이트합니다.
   • "R": 오른쪽 방향으로 가로선을 그립니다.
   • "L": 왼쪽 방향으로 가로선을 그립니다.
   • "U": 위쪽 방향으로 세로선을 그립니다.
   • "D": 아래쪽 방향으로 세로선을 그립니다.

이렇게 배열 `arr`은 각 명령에 따라 업데이트되고, 최종적으로 어떤 위치에 몇 개의 선이 그어졌는지를 나타낼 것입니다.

 

(20일차)

1. def f(i, j, c):: 함수 f는 2차원 배열 arr에서 (i, j) 위치를 시작으로 DFS를 수행합니다. c는 해당 위치에 채워 넣을 문자입니다.
2. arr[i][j] = c: 시작 위치 (i, j)에 문자 c를 채워넣습니다.
3. stack = [(i, j)]: DFS를 수행하기 위한 스택을 초기화하고, 시작 위치를 스택에 넣습니다.
4. visited = set(): 방문한 위치를 저장하기 위한 집합을 선언합니다.
5. while stack:: 스택이 비어 있지 않는 한 계속해서 DFS를 수행합니다.
6. y, x = stack.pop(): 스택의 마지막 요소를 가져와서 y, x에 할당합니다.
7. if (y, x) in visited:: 이미 방문한 위치면 건너뜁니다.
8. visited.add((y, x)): 방문한 위치를 visited 집합에 추가합니다.
9. for k in range(4):: 현재 위치에서 상하좌우 4개의 방향을 확인합니다.
10. if ny in (-1, N) or nx in (-1, N) or arr[ny][nx] != arr[y][x]:: 탐색하려는 위치가 범위를 벗어나거나, 문자가 다르면 건너뜁니다.
11. stack.append((ny, nx)): 위의 조건을 통과한 위치를 스택에 추가합니다.
12. if len(visited) >= K:: 방문한 칸의 개수가 K 이상이면, 모든 방문한 칸을 "."로 바꿉니다.

 

총 결산

늦게 시작하여 첫날을 놓쳤고, 아직 습관이 되지 않아 둘째 주 하루를 까먹었다. 그 다음부터는 다 채운듯!