자료구조(Data Structure)

구독하고 자주 챙겨보는 유투버 중에서 김포프라는 프로그래머가 있다.게임 렌더링 프로그래머이고 경력이 아주 화려한분.. C++관련 깊이 있는 주제와 흔히 간과하기 쉬운 문제들을 다루면서,컴퓨터 공학적 인사이트를 많이 얻어갈 때가 많다. 최근에 봤던 영상 중 하나는, 해시테이블에 관한 내용이다.https://www.youtube.com/watch?v=S7vni1hdsZE 영상을 요약하자면,어떤 자료구조, 알고리즘 STL을 그대로 갖다가 쓰는게 아니라 내부 동작원리를 이해해야한다!라는 내용이다. 사실 당연한 내용이다.말단급 엔지니어가 아니라 상위급 엔지니어로 갈수록 어떤 도구를 사용할때 그 도구의 작동원리까지 완벽하게 파악하고있다.그래서 문제가 터지면 원인을 빠르게 진단하고 해결할 수 있기 때문이다. 이런 내..

이진 트리의 순회 이진 트리를 순회한다는 것은, 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하기 위함이다. 스택이나 큐에서는 순회하는 방법이 한가지 밖에 없었지만, 이진트리를 순회하는 방법은 여러가지 이다. 이진트리 순회 방법 이진트리의 순회 방법엔 크게 3가지가 있다. 전위 : VLR 후위 : LRV 중위 : LVR 루트노드를 방문하는 것을 V, 왼쪽 서브트리를 방문하는 것을 L 그리고 오른쪽 서브트리를 방문하는 것을 R이라고 하자. 루트노드를 방문한다음 서브트리를 방문하는 것을 전위순회라고 하고, 루트노드를 왼쪽과 오른쪽 서브트리 중간에 방문하는 것을 중위순회라고 하며, 루트노드를 서브트리 방문 후에 방문하면 후위순회라고 한다. 트리 순회 알고리즘은..

트리의 개념 ​ 리스트, 스택, 큐는 선형 자료 구조이다. 선형 자료 구조란 자료들이 선형으로 나열되어 있는 구조를 의미한다. 계층적인 구조를 나타낼 땐, 트리를 이용한다. 트리의 용어 ​ ​ A, B, C, D .. 이런것들을 노드라고 한다. 계층의 가장 위에있는 노드를 루트노드, (B, E, F) (C, G) (D H I)를 서브트리라고 부른다. 그리고, (B E F)의 루트는 B가 되고, 나머지 E F는 서브트리가 된다. 트리에서 루트와 서브트리를 연결하는 선을 간선(edge)라고 부른다. ​ 노드의 차수는 노드가 갖고있는 자식노드의 개수를 의미한다. A는 자식을 B C D 총 3명 가지고있으므로 차수(degree)가 3이다. B는 2개. 트리의 차수는 트리가 가지고 있는 노드의 차수중 가장 큰 값..

희소 행렬이란? 행렬의 값이 대부분 0인 행렬 일반적으로 행렬은 2차원 배열을 이용한다. #define MAX_ROWS 100 #define MAX_COLS 100 int matrix[MAX_ROWS][MAX_COLS]; 이것이 방법 1 이고. 하지만, 이 방법으로 행렬을 표현하게 된다면 다수의 항이 0일 경우에 메모리 낭비가 심하게 된다. 그래서 다른 방법을 사용할 필요가 있다. 희소 행렬을 나타내는 다른 방법 배열을 이용하되 행렬 값이 0이 아닌 노드만을 행 / 열 / 값 으로 표시하는 것이다. 이것이 방법 2 이다. 예를 들어, 이렇게 생긴 행렬이 있다고 가정해보자. 이 행렬을 새로운 방법으로 나타내면, 이렇게 나타낼 수 있다. 만약 방법 1(이차원 배열)로 행렬의 전치 연산을 한다고 생각해보자. ..

원형 연결 리스트란? 원형 연결 리스트는 마지막 노드가 첫 번째 노드를 가리키는 리스트다. 단순 연결 리스트라면 마지막 노드는 NULL을 가리키지만, 원형은 첫 번째 노드를 가리킨다. 장점? - 원형 연결 리스트는 원형적으로 구현되어있어 하나의 노드에서 다른 모든 노드를 접근할 수 있다. 왜냐면, 노드를 쭉 따라다가보면 결국 모든 노드를 거쳐 자기 자신 노드로 되돌아 올 수 있기 때문에. 그리고, 삽입 / 삭제가 단순 연결 리스트보다 간편하다. (이전 노드를 가리키는 포인터가 필요없다!) 원형 연결 리스트는 리스트의 끝에 노드를 삽입할 때, 단순 연결 리스트보다 효율적이다. 단순 연결 리스트의 경우, 리스트의 끝에 노드를 삽입할 때, 첫 노드부터 링크를 따라서 끝까지 도달해야만 한다. 하지만! 원형 연결..

연결 리스트 저번 시간에 구현했던 그냥 '리스트'와는 달리, 연결 리스트는 동적으로 크기가 변할 수 있고, 삭제나 삽입 시에 데이터를 이동할 필요가 없다. why? 이것이 연결리스트의 기본 구조이다. 데이터가 담긴 상자를 노드(node)라고 부른다. 노드와 노드를 연결하는 선을 포인터(pointer)로 구현한다. 연결 리스트에서는 노드를 연결시켜주는 줄만 바꾸면, 삽입 / 삭제가 간편하다. 만약 b와 c사이에 새로운 데이터를 삽입한다고 가정한다면, 그림과 같이 b가 n을 가리키도록, 그리고 n이 c를 가리키도록 줄을 수정해주면 된다. 만약 c를 삭제한다고 가정한다면, 이렇게 줄을 연결하면 된다. 연결 리스트의 구조 우리는 상자를 node라고 불렀다. node는 2가지 영역으로 나뉘는데, 하나는 데이터가 ..