이진 트리의 순회 이진 트리를 순회한다는 것은, 이진트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하기 위함이다. 스택이나 큐에서는 순회하는 방법이 한가지 밖에 없었지만, 이진트리를 순회하는 방법은 여러가지 이다. 이진트리 순회 방법 이진트리의 순회 방법엔 크게 3가지가 있다. 전위 : VLR 후위 : LRV 중위 : LVR 루트노드를 방문하는 것을 V, 왼쪽 서브트리를 방문하는 것을 L 그리고 오른쪽 서브트리를 방문하는 것을 R이라고 하자. 루트노드를 방문한다음 서브트리를 방문하는 것을 전위순회라고 하고, 루트노드를 왼쪽과 오른쪽 서브트리 중간에 방문하는 것을 중위순회라고 하며, 루트노드를 서브트리 방문 후에 방문하면 후위순회라고 한다. 트리 순회 알고리즘은..
버퍼란 임시 저장 공간이다. 버퍼는 데이터를 이동시킬 때 사용된다. 데이터를 키보드로부터 입력받고, 이를 잠시 버퍼에 저장한다. 그렇다면, 버퍼를 언제, 왜 사용하는가? 버퍼는 속도차이가 큰 두 대상이 상호작용하며 입출력을 할 때 사용된다. 예를 들어서, HDD에서 CPU로 데이터를 전송한다고 해보자. CPU는 초당 수억개의 비트를 처리할 수 있다.(속도가 매우 빠름) 하지만 HDD는 데이터 전송 속도가 CPU의 처리 속도에 비해 매우 느린 편이다. HDD가 초당 5개의 데이터를 전송할 수 있고, CPU가 초당 100개의 데이터를 처리할 수 있다고 가정한다면, CPU의 능력에 비해, HDD에서 전송되어 오는 데이터의 양은 너무나 작다. 여기서 95만큼을 더 처리할 수 있지만, CPU는 빈둥빈둥 놀게되는 ..
Window OS를 설치할때 32비트 혹은 64비트 윈도우를 설치할 것인지 사용자에게 묻는다. 본인이 중학생, 고등학생때는 64비트? 더 높으니까 32비트보다는 좋아보여서, 그리고 32비트 윈도우에서는 RAM을 4GB밖에 인식을 못하니, 64비트 윈도우를 '무지성'으로 설치했던 기억이 있다. 그렇다면, 32비트 윈도우에서는 왜 메모리를 4GB밖에 인식하지 못할까? 라는 의문이 컴공과 2학년이 되어서야 들기 시작했다.. 그 이유를 알고자 전공책과 구글서치를 한 결과를 포스팅하려한다. 32비트 CPU 우선, 우리가 현재 사용하고 있는 CPU는 크게 2가지로 나뉜다. 32비트 CPU 64비트 CPU 레지스터는 CPU가 처리할 데이터들을 잠깐 담아두는 일종의 메모리이다. 32비트 CPU는 한번에 최대 32비트의..
트리의 개념 리스트, 스택, 큐는 선형 자료 구조이다. 선형 자료 구조란 자료들이 선형으로 나열되어 있는 구조를 의미한다. 계층적인 구조를 나타낼 땐, 트리를 이용한다. 트리의 용어 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()함수를 이용해서 풀면 될까? -> 메모리 초과로 불가능 그래도 시간 초과가 ..
