트리의 개념 ​ 리스트, 스택, 큐는 선형 자료 구조이다. 선형 자료 구조란 자료들이 선형으로 나열되어 있는 구조를 의미한다. 계층적인 구조를 나타낼 땐, 트리를 이용한다. 트리의 용어 ​ ​ 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(이차원 배열)로 행렬의 전치 연산을 한다고 생각해보자. ..

https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 어떻게 풀어야 할까? 아마 이 문제를 처음 접할 때, 선택 정렬 알고리즘을 사용할 것 이다. 그러면 틀린다. 왜냐면 배열을 int 형으로 잡고 10,000,000 계산한다고 가정했을때, 보수적으로 잡아도 40MB의 메모리가 소요되기 때문이다. 선택 정렬로 풀면 이중 for문이 들어가게 된다. -> 시간 초과에서 걸린다. 그렇다면, sort()함수를 이용해서 풀면 될까? -> 메모리 초과로 불가능 그래도 시간 초과가 ..

만약 2차원 배열을 함수의 인자로 전달해서(포인터 형식으로), 그 2차원 배열을 정렬한다고 가정해보자. void sort(int (*arr)[5], int n) { int i = 0; int j = 0; int least; int temp; for(i = 0; i arr[n][j]) least = j; } temp = arr[n][i]; arr[n][i] = arr[n][least]; arr[n][least] = temp; } } 2차원 배열을 포인터 형식으로 받고, n번째의 행을 정렬하는 함수다. 여기서 봐야할 부분은 void sort(int (*arr)[5], int n) 이다...

https://www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 어떻게 풀 것인가? 처음에는 소수를 판별하는 함수(2부터 n보다 작은 수로 나눠서 나머지가 0인게 중간에 있다면 소수O) 를 사용하여 풀려고 했다. 하지만, 이 방식을 사용하게 된다면 시간초과가 뜰 가능성이 매우 높다. '에라토스테네스의 체'를 사용하여 문제를 풀 수도 있었지만, for문의 사용을 최대한 줄여서, 연산시간을 최대한 줄일려고 노력했다. 소스 코드 #include using namespace s..

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