자료알고 검색 결과

해당 글 130건
이중 연결 리스트 : 노드를 연결하는 포인터가 2개다.

보통 C++의 STL에서는 double list를 많이 쓰는데요. 노드를 가리키는 포인터가 2개입니다. 각각 이전 것과, 다음 것을 가리키고 있습니다. 실제로, 이전 것도 가지고 있으면, 삭제하거나, 들어가야 하는 위치를 안다고 했을 때, 빠르게 자료구조에서 데이터를 삭제하거나, insert를 할 수 있어요. 기준 위치로부터 이전 노드의 주소도 알고 있기 때문입니다. 오늘은 이중 연결 리스트를 구현 해 보도록 하겠습니다. 먼저 node형 구조체는 다음과 같이 선언합니다. 각각, data를 담아두는 필드와, 이전 것 prev, 그리고 next를 가리키는 요소를 저장하고 있습니다. 다음에 head와 tail이 있는데요. 이것은 각각 리스트의 시작 위치와 끝나는 위치를 나타냅니다. 그러면 연결 리스트를 초기화..
자료알고/자료구조 2019. 7. 27. 17:30
자기 참조 구조체 : 간단하게 이해해 봅시다.

자기 참조 구조체란, 자기 구조체와 같은 형을 point 하는 필드가 있는 구조체를 말해요. 왜 갑자기 자료구조가 안 나오고, 이것이 먼저 나왔을까요? 이것을 이해해야 List를 이해할 수 있기 때문이에요. 코드를 봅시다. 보시면 struct node 안에, struct node를 가리키는 포인터가 있음을 알 수 있어요. 그렇다면, node 안의 어떠한 필드가 또 다른 node를 가리킬 수 있다는 것을 의미합니다. 이런 식으로 말입니다. 이게 single로 이어져 있으면 모르겠지만, double로 이어져 있다면, 삭제할 위치라던지, 삽입할 위치만 알고 있다면, 삽입과 삭제하는 연산을 금방 할 수 있기 때문에, List를 쓰고요. C언어에서 List를 구현하기 위해서 자기 참조 구조체를 쓰는 셈입니다. "..
자료알고/자료구조 2019. 7. 24. 18:05
버블 정렬 알고리즘 : 인접한 원소들을 비교하면서 진행한다.

정렬 알고리즘 중, 버블 정렬은 서로 이웃한 원소들끼리 비교하면서 우선 순위가 낮은 데이터를 뒤로 보내는 정렬을 합니다. 이것도, insert, selection과 같이 시간 복잡도는 O(n^2)인데요. 따로 처리를 하지 않는 이상, 어떠한 경우에도, 제곱에 비례하기 때문에, merge나 heap에 비해서는 거의 안 쓰인다고 보시면 되어요. 배열 [2, 1, 4, 5, 3]을 오름차순으로 정렬해 볼 겁니다. 그러면 수가 작을수록 우선 순위가 높고, 수가 클수록 우선 순위가 낮다는 이야기가 되겠어요. 인접한 두 수 a와 b가 있다면, a보다 b가 더 작다면, a랑 b를 바꾸는 식으로 동작할 듯 싶습니다. 배열이 이렇게 있어요. 아직 sorting 하기 전이에요. 총 5회전을 돌 건데요. 이것은 1회전입니다..
자료알고/알고리즘 2019. 7. 23. 23:17
히스토그램에서 가장 큰 직사각형 : 스택으로 선형에 풀어보자.

스택을 응용한 문제 중에는, 히스토그램에서 가장 큰 직사각형이라는 문제가 있습니다. 히스토그램 안에서 그릴 수 있는 직사각형 중, 넓이가 가장 큰 직사각형의 넓이를 구하는 문제입니다. 이것은 푸는 방법이 상당히 많습니다. 세그먼트 트리로 풀어도 되고, 분할 정복으로 풀어도 됩니다. 여기에서는 우리가 배운 스택을 응용해서 풀어보도록 하겠습니다. 먼저 데이터가 다음과 같이 들어왔다고 해 봅시다. 히스토그램에서, 총 7개의 직사각형이 있어요. 그러면 arr[0]과 arr[8]은 0으로 초기화를 합니다. 이를 더미 데이터라고 합니다. 처리하기 쉽게 처리한 겁니다. 그리고 arr[1] = 2, arr[2] = 1, arr[3] = 4, arr[4] = 5, arr[5] = 1, arr[6] = arr[7] = 3..
자료알고/자료구조 2019. 7. 22. 16:30
부분합 구하기 : 누적합만 들고 있으면 된다.

1차원, 2차원 배열에서 구간이 주어졌을 때 어떻게 부분합을 구하는지 알아봅시다. 3차원 이상인 경우에는, 포함 배제의 원리를 알고 있어야 됩니다. 그렇기 때문에, 저는 1차, 2차원 array에서 subsum, 부분합을 구하는 것만 알려드리도록 하겠습니다. 먼저 누적합을 1차원에서 어떻게 구하는지 봅시다. 배열 arr이 있습니다. 제가 보라색으로 칠해놓은 것은 더미 데이터를 넣는데요. 0을 넣습니다. 0에 x를 더해도 0이기 때문입니다. 즉, 0은 덧셈에 대한 역원이기 때문에 보통 0으로 초기화를 합니다. nj[x]를 다음과 같이 정의합시다. 구간 [0,x]에 있는 수들의 합. 그렇다면 nj[0]의 값은 0입니다. 아무것도 없으니까 합이 0일 수 밖에 없기 때문입니다. 그러면 [0,x]까지의 합은 어떻..
자료알고/알고리즘 2019. 7. 21. 23:55