당니의 개발자 스토리

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

2주차 개념 #4-2. 인접행렬(adjacency matrix) 문제를 풀어보면서 배워보도록 할게요. 한번 생각해본 다음에 답을 보셔야 합니다. 쉽죠? 이건 뭘까요? 간단하죠? 연결되어 있다, 인접해 있다 이걸 그냥 1 또는 0 이렇게 표현하는 거예요. 이건 뭘까요? 이렇게 만들어야 겠죠. 물론 20보다 큰 수를 담을 수가 있어요. 뭐냐면 정점의 개수가 20개가 있으면, 이렇게 해도 할 수가 있어요. 그러니까 20개 이상이면 되는 거예요. 우리가 표현해야 되는 건 뭐? 정점의 개수가 20개일 때, 이렇게 2차원 배열이 필요한 거예요. 20개 곱하기 20개가 필요한데, 사실은 이것보다 조금 더 큰 값을 부여할 수 있다는 소리예요. 근데 문제는 메모리를 최소화해야 된다고 했기 때문에 20 곱하기 20 배열이..

2주차 개념 #4-2. 인접행렬(adjacency matrix) 문제를 풀어보면서 배워보도록 할게요. 한번 생각해본 다음에 답을 보셔야 합니다. 쉽죠? 이건 뭘까요? 간단하죠? 연결되어 있다, 인접해 있다 이걸 그냥 1 또는 0 이렇게 표현하는 거예요. 이건 뭘까요? 이렇게 만들어야 겠죠. 물론 20보다 큰 수를 담을 수가 있어요. 뭐냐면 정점의 개수가 20개가 있으면, 이렇게 해도 할 수가 있어요. 그러니까 20개 이상이면 되는 거예요. 우리가 표현해야 되는 건 뭐? 정점의 개수가 20개일 때, 이렇게 2차원 배열이 필요한 거예요. 20개 곱하기 20개가 필요한데, 사실은 이것보다 조금 더 큰 값을 부여할 수 있다는 소리예요. 근데 문제는 메모리를 최소화해야 된다고 했기 때문에 20 곱하기 20 배열이..

2주차 개념 #4-1. 인접행렬(adjacency matrix) 우리가 지금까지 그래프라는 걸 배웠죠. 정점과 간선의 집합인 그래프를 컴퓨터에게 알려주려면 어떻게 해야 될까요? 아니 이제 정점과 간선이라는 개념들은 알겠어. 그런데 정점과 간선으로 연결된 이러한 그래프가 있다고 컴퓨터에게 알려주려면 어떻게 해야될까요? 두 가지 방법이 있습니다. 첫 번째는 인접행렬, 두 번째는 인접리스트 라는 게 있습니다. 여기서 인접이라는 것은 연결되어 있다는 거예요. 자, 오늘은 인접행렬과 인접리스트 중에서 인접행렬을 설명을 해드릴 거예요. 그 전에 한 개 짚고 넘어갈 게 있는데, 뭐냐면 우리가 앞서서 단방향 간선에 대해서 배웠죠? 이렇게 하나의 간선만 있는 게 뭐? 단방향 간선이다. 근데 만약에 하나 더 있어. 그럼 ..

2주차 개념 #4-1. 인접행렬(adjacency matrix) 우리가 지금까지 그래프라는 걸 배웠죠. 정점과 간선의 집합인 그래프를 컴퓨터에게 알려주려면 어떻게 해야 될까요? 아니 이제 정점과 간선이라는 개념들은 알겠어. 그런데 정점과 간선으로 연결된 이러한 그래프가 있다고 컴퓨터에게 알려주려면 어떻게 해야될까요? 두 가지 방법이 있습니다. 첫 번째는 인접행렬, 두 번째는 인접리스트 라는 게 있습니다. 여기서 인접이라는 것은 연결되어 있다는 거예요. 자, 오늘은 인접행렬과 인접리스트 중에서 인접행렬을 설명을 해드릴 거예요. 그 전에 한 개 짚고 넘어갈 게 있는데, 뭐냐면 우리가 앞서서 단방향 간선에 대해서 배웠죠? 이렇게 하나의 간선만 있는 게 뭐? 단방향 간선이다. 근데 만약에 하나 더 있어. 그럼 ..

2주차 개념 #3. 이진트리와 이진탐색트리 오늘은 이진트리와 BST 라고 불리는 이진탐색트리까지 얘기를 해보도록 하겠습니다. 일단은 이진트리, BST라고도 불리죠. 이진트리에 대해서 얘기를 해보도록 할텐데, 이진트리는 각각의 자식노드 수가 2개 이하로 구성되어 있는 트리를 의미합니다. 뭐냐면 저희가 앞서서 트리에 대해서 배웠죠. 왼쪽도 트리고 오른쪽도 트리죠. 자 여러분 왼쪽 트리는 각각 몇개의 자식노드를 가지고 있을까요? 이렇죠. 그리고 이 트리는 루트 노트의 자식노드가 4개이죠. 그러니까 모양이 예쁘지 않더라도 이런 것도 트리(Tree)라는 거예요. 그런데 이렇게 제거를 하면, 자식 노드가 2개 이하인 트리가 완성 되죠. 이러한 트리를 이진트리라고 하는 겁니다. 즉, 각각의 노드의 자식노드 수가 2개..

2주차 개념 #3. 이진트리와 이진탐색트리 오늘은 이진트리와 BST 라고 불리는 이진탐색트리까지 얘기를 해보도록 하겠습니다. 일단은 이진트리, BST라고도 불리죠. 이진트리에 대해서 얘기를 해보도록 할텐데, 이진트리는 각각의 자식노드 수가 2개 이하로 구성되어 있는 트리를 의미합니다. 뭐냐면 저희가 앞서서 트리에 대해서 배웠죠. 왼쪽도 트리고 오른쪽도 트리죠. 자 여러분 왼쪽 트리는 각각 몇개의 자식노드를 가지고 있을까요? 이렇죠. 그리고 이 트리는 루트 노트의 자식노드가 4개이죠. 그러니까 모양이 예쁘지 않더라도 이런 것도 트리(Tree)라는 거예요. 그런데 이렇게 제거를 하면, 자식 노드가 2개 이하인 트리가 완성 되죠. 이러한 트리를 이진트리라고 하는 겁니다. 즉, 각각의 노드의 자식노드 수가 2개..

2주차 개념 #2. 트리(Tree Data Structure) 오늘은 트리에 대해서 배워보도록 할게요. 저희 나무 한번 생각해볼까요. 이러한 나무를 뒤집으면 어떻게 될까요? 뒤집으면 이렇게 되겠죠? 이러한 모습, 그러니까 나무를 뒤집은 모습을 가지고 있는 자료구조를 트리다 라고 해요. 오늘은 트리에 대해서 배워보도록 하겠습니다. 트리는 자식노드와 부모노드로 이루어진 계층적인 구조를 가지며 무방향 그래프의 일종이자 사이클이 없는 자료구조를 의미합니다. 먼저 자식노도와 부모노드로 잠깐 예를 들어볼게요. 중간에 있는 이 노드를 중심으로, 이 노드를 기반으로 만들어지는 경로 상에서 위에 있는게 부모, 아래에 있는게 자식입니다. 즉, 위에 있으면 부모구요. 아래에 있으면 자식 노드가 된다라는 거에요. 그리고 지금..