당니의 개발자 스토리

2주차 개념 #9. 깊이우선탐색(DFS, Depth First Search) 오늘은 깊이 우선 탐색(DFS, Depth First Search)에 대해서 얘기를 해보도록 할게요. DFS는 그래프를 탐색할 때 쓰는 알고리즘이고요. 어떤 노드부터 시작해서 인접한 노드들을 재귀적으로 방문하며, 방문한 정점은 다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 노드까지 탐색하는 알고리즘 입니다. 만약에 이런 그래프가 있다고 할게요. 우리가 BFS를 배우지 않았지만, BFS라면 이런 식으로 탐색을 하거든요. level별로 탐색을 해요. 이런 식으로 방문하면서 정점들을 탐색해 나가는 게 BFS인데, DFS는 이렇게 탐색을 하지 않고요. 어떻게 탐색하냐? 바로 이런 식으로 탐색해요. 이렇게 이 노드를 방문하고 ..

보호되어 있는 글입니다.

2주차 개념 #8. 연결된 컴포넌트(connected component) 오늘은 연결된 컴포넌트, connected component 라는 것에 대해서 얘기를 해보도록 할게요. 연결된 컴포넌트는 연결된 하위 그래프를 얘기를 하고요. 연결된 하나의 덩어리다 라고 보시면 돼요. 1번, 2번, 3번, 4번, 5번, 6번, 7번 이런 정점과 간선의 집합을 그래프 라고 했죠. 그래프 밑에 하위 그래프가 있는 거예요. 그러니까 지금 보시는 것처럼 1번과 2번이 서로 연결되어 있고 3, 4, 5번이 서로 연결되어 있고 6번, 7번은 서로 연결되어 있죠. 뭔가 이렇게 덩어리 세개로 나눠질 것 같다 라고 보시면 되죠. 연결된 컴포넌트가 뭐냐면 이렇게 연결된 하나의 덩어리이고요. 이 덩어리는 연결된 컴포넌트에 속한 "모든..

2주차 개념 #7. 맵과 방향벡터(direction vector) 우리가 지금까지 그래프라는 걸 표현한다고 했을 때 인접행렬과 인접리스트 라는 걸 배웠죠. 사실은 그래프를 표현한다고 했을 때 이 두 가지 밖에 없어요. 근데 문제에서 이런 것들이 아니라, Map으로 주어지는 경우가 있거든요. 이런 식으로 N 곱하기 M 크기의 배열로 표현되는 미로가 있다. 이렇게 맵으로 주어지는 경우가 있어요. 이 경우에 어떻게 해야 되는지를 얘기를 해보고자 합니다. 뭐냐면 주인공이 이 좌표에 있어요. 이 Map은 1과 0으로 이루어진 지도예요. 여기서 1은 갈 수 있는 곳이고 0은 갈 수 없는 곳이에요. 문제에서 주인공은 한 칸씩 이동할 수가 있대요. 그래서 '주인공이 갈 수 있는 모든 좌표를 출력하라' 이런 문제가 있다..

2주차 개념 #7. 맵과 방향벡터(direction vector) 우리가 지금까지 그래프라는 걸 표현한다고 했을 때 인접행렬과 인접리스트 라는 걸 배웠죠. 사실은 그래프를 표현한다고 했을 때 이 두 가지 밖에 없어요. 근데 문제에서 이런 것들이 아니라, Map으로 주어지는 경우가 있거든요. 이런 식으로 N 곱하기 M 크기의 배열로 표현되는 미로가 있다. 이렇게 맵으로 주어지는 경우가 있어요. 이 경우에 어떻게 해야 되는지를 얘기를 해보고자 합니다. 뭐냐면 주인공이 이 좌표에 있어요. 이 Map은 1과 0으로 이루어진 지도예요. 여기서 1은 갈 수 있는 곳이고 0은 갈 수 없는 곳이에요. 문제에서 주인공은 한 칸씩 이동할 수가 있대요. 그래서 '주인공이 갈 수 있는 모든 좌표를 출력하라' 이런 문제가 있다..

2주차 개념 #6. 인접행렬과 인접리스트의 차이 저희가 지금까지 인접행렬과 인접리스트를 배워봤어요. 그러면 이 둘 중에 뭘 써야 될까? 그 차이를 배워보도록 하겠습니다. 첫번째는 공간 복잡도예요. 인접행렬은 O(V^2), 인접 리스트는 O(V + E)만큼이 필요하다는 거예요. V는 vertex, E는 edge라고 했죠. 여러분 인접행렬은 뭐라고 했죠? 인접행렬은 단순무식하게 vertex가 만약에 100개라면 100개씩 이렇게 2차원 배열을 만든다 라고 했죠. 이게 인접 행렬이에요. 그렇기 때문에 인접 행렬의 공간 복잡도는 O(V^2)이 필요한거죠. '아니 근데 선생님 인접 리스트는 각 정점마다 연결 리스트를 만들어서 정점을 집어넣는다 라고 한거 아닌가요? 인접행렬이 O(V)까지는 이해를 하겠는데, 인접 ..

2주차 개념 #6. 인접행렬과 인접리스트의 차이 저희가 지금까지 인접행렬과 인접리스트를 배워봤어요. 그러면 이 둘 중에 뭘 써야 될까? 그 차이를 배워보도록 하겠습니다. 첫번째는 공간 복잡도예요. 인접행렬은 O(V^2), 인접 리스트는 O(V + E)만큼이 필요하다는 거예요. V는 vertex, E는 edge라고 했죠. 여러분 인접행렬은 뭐라고 했죠? 인접행렬은 단순무식하게 vertex가 만약에 100개라면 100개씩 이렇게 2차원 배열을 만든다 라고 했죠. 이게 인접 행렬이에요. 그렇기 때문에 인접 행렬의 공간 복잡도는 O(V^2)이 필요한거죠. '아니 근데 선생님 인접 리스트는 각 정점마다 연결 리스트를 만들어서 정점을 집어넣는다 라고 한거 아닌가요? 인접행렬이 O(V)까지는 이해를 하겠는데, 인접 ..

2주차 개념 #5. 인접리스트(adjacency list) 오늘은 인접 리스트에 대해서 배워보도록 하겠습니다. 저희가 앞서서는 인접행렬에 대해서 배웠죠. 인접행렬은 2차원 배열을 기반으로 그래프를 표현한다고 했죠. 그런데 인접 리스트는 2차원 배열이 아니라, 연결 리스트를 여러 개 만들어서 그래프를 표현하는 방법이다. 라고 보시면 됩니다. 예를 들어서 이런 그래프가 있어요. 이걸 어떻게 연결 리스트로 표현할까? 정점마다 연결 리스트를 만드는 거예요. 정점이 몇 개? 4개죠. 이 4개의 정점마다 연결 리스트를 만들어요. 그리고 여기다가 연결된 정점들을 다 집어넣어요. 그러니까 각 정점마다 연결 리스트를 만들고, 그 연결 리스트에다가 연결되어 있는 정점만 집어 넣는 거예요. 연결되지 않은 정점은 신경 쓰지 ..