코딩하는 수학도

위상 정렬 (Topology Sort) 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘이다. 혹은 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것' 이다. 진입차수 (Indegree) 특정한 노드로 들어오는 간선의 개수 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다. 2. 큐가 빌 때까지 다음의 과정을 반복한다. 2-1. 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. 2-2. 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. 이때 모든 원소를 방문하기 전에, 즉 원소가 V번 추출되기 전에 큐가 비어버리면 사이클이 발생한 것이다. 예제 step 0 진입차수가 0인 노드를 큐에 넣는다. 노드 1 2 3 4 5 진입차수 ..

신장트리 (Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 이때 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립조건이기도 하다. 예를 들어 다음과 같은 그래프가 있다고 하자. 위의 그래프에서 가능한 신장 트리는 다음과 같다. (여러개 존재 가능) 다음은 신장 트리가 될 수 없다. 사이클이 존재하기 때문이다. 다음도 신장 트리가 될 수 없다. 노드 2를 포함하고 있지 않기 때문이다. 최소 신장 트리 알고리즘 신장 트리 중에서 최소 비용으로 만들 수 있는 신장트리를 찾는 알고리즘을 말한다. 최소 신장 트리의 간선의 개수는 '노드의 개수 - 1'이다. 대표적인 최소 신장 트리 알고리즘으로는 크루스칼 ..

게임 개발 현민이는 게임 캐릭터가 맵 안에서 움직이는 시스템을 개발 중이다. 캐릭터가 있는 장소는 1 x 1 크기의 정사각형으로 이뤄진 N x M 크기의 직사각형으로, 각각의 칸은 육지 또는 바다이다. 캐릭터는 동서남북 중 한 곳을 바라본다. 맵의 각 칸은 (A, B)로 나타낼 수 있고, A는 북쪽으로부터 떨어진 칸의 개수, B는 서쪽으로부터 떨어진 칸의 개수이다. 캐릭터는 상하좌우로 움직일 수 있고, 바다로 되어 있는 공간에는 갈 수 없다. 캐릭터의 움직임을 설정하기 위해 정해 놓은 매뉴얼은 이러하다. 현재 위치에서 현재 방향을 기준으로 왼쪽 방향(반시계 방향으로 90도 회전한 방향)부터 차례대로 갈 곳을 정한다. 캐릭터의 바로 왼쪽 방향에 아직 가보지 않은 칸이 존재한다면, 왼쪽 방향으로 회전한 다음..