자료알고 검색 결과

해당 글 130건
그리디 알고리즘 : 매 순간 최적의 해를 선택한다.

greedy는, 욕심쟁이라는 뜻입니다. 이름에 걸맞게, 매 순간 제일 매력적인 해를 택하는 방법입니다. 그런데 그게 best한 답일까요? 답은 그럴 수도 있고 아닐 수도 있다는 것입니다. 오늘은 이러한 approach로 풀 수 있는 문제 중에서 쉬운 문제만 소개해 드리도록 하겠습니다. 작업 n개가 주어집니다. 이들을 끝내는 데 걸리는 시간이 있습니다. 각각 T(1), ... ,T(n)이라고 합시다. 우리는 제한시간 limit 내에 최대한 많은 작업을 끝내려고 합니다. 어떻게 하면 좋을까요? 직관적으로 생각했을 때, 선택하지 않은 작업들 중에서, 소요 시간이 제일 짧은 작업들을 매 순간마다 선택하면 될 거 같습니다. 그러면 T 배열을 정렬하면 될 겁니다. 예를 들어 T = [2, 5, 1, 3, 7] 이라..
자료알고/알고리즘 2019. 10. 26. 18:58
셀 정렬 : 갭을 줄여가면서 해결한다.

삽입 정렬의 복잡도는 O(n^2)입니다. 물론 평균 복잡도 또한 O(n^2)입니다. 물론, memcpy 등으로 실행 시간을 빠르게 할 수 있는 여지는 있지만, 거기까지일 뿐입니다. 다만, insertion sort의 장점도 있는데요. 거의 정렬된 데이터에 대해서는 상당히 빠르게 동작한다는 장점이 있어요. 하지만, 한 번에 한 요소씩. 비교 1번 할 때 마다, 1요소씩만 move 하기 때문에 효율적이지 않은데요. 이를 보완하기 위해서 gap이라는 변수를 둡니다. 그러면 먼저 init 함수를 봅시다. 먼저, si 라는 벡터가 있습니다. 여기에 무슨 값들이 들어있는지 봅시다. 1, 4, 13, 40, 121, 361, 1093, 3280, ... 네. 이런 값들이 들어 있는데요. gap으로 쓸 겁니다. 예를 ..
자료알고/알고리즘 2019. 10. 14. 01:24
전치 행렬 (Transpose matrix) : 왜 중요한가?

원래 이 포스트는 곱셈까지 다루려고 했습니다. 그런데, 생각보다 내용이 길어질 듯 싶어서, 이 부분만 먼저 다루도록 하겠습니다. 전치 행렬은, 원본 행렬에서, 행과 열을 서로 맞바꾼 것을 말합니다. 예를 들어 [[1,2],[3,4]]의 전치 행렬은 [[1,3],[2,4]]가 됩니다. 희소 행렬 곱셈을 배우기 위해서, 먼저, transpose matrix에 대해서 배우는데요. 사실. 그렇게 해야 조금 더 쉽고 빠르게, 그리고 cache를 더 잘 써먹을 수 있기 때문에 그러지 않나 싶기도 하네요. 예를 들어 원본 행렬에서 2행 3열에 7이라는 값이 있었습니다. 그러면, 전치 행렬에서는 3열 2행에, 7이라는 값이 있어야 합니다. 이걸 어떻게 하면 좋을까요? 데이터가 m개 있다면, 열 번호를 1번째 기준으로,..
자료알고/자료구조 2019. 10. 13. 17:47
희소 행렬 (sparse matrix) : 어떤 정보가 중요한가?

이번 시간부터는 약간씩 고급진(?) 자료구조들을 배워보려고 합니다. 그 중, 첫 번째는 어떻게 희소행렬 (sparse matrix)를 표현할 것인가? 입니다. n행 m열의 행렬이 있다면, nm개의 수를 가지고 있을 거에요. 그것에 비해, 0의 수가 월등하게 많다면 어떻게 해야 할까요? 예를 들어, 1000 by 1000 행렬에, 1이 10개만 있고, 나머지는 모두 0이라고 해 봅시다. 그러면, 인접 행렬로 10^6개의 수들을 모두 저장할 필요가 있을까요? 그렇지 않다는 것이 핵심입니다. 그러면 어떤 정보를 저장하면 좋을까요? r행 c열에 수 k가 있다. 그러면, 이러한 정보를 동적 배열에 넣어버리면 될 겁니다. 예를 들자면, 1행 1열에 1, 1행 3열에 1, 2행 2열에 15가 있는 5 by 5짜리 행..
자료알고/자료구조 2019. 9. 27. 18:00
LRU 알고리즘 : 리스트를 활용해서 구현해 봅시다.

고급 자료구조 이론에 들어가기 전에, 복습 겸 코딩 테스트에 자주 나오는 LRU 알고리즘을 간단하게 구현해 보도록 하겠습니다. 어떠한 페이지를 찾아야 한다고 해 봅시다. 메모리에서. 그런데, 그 페이지가 없어요. p라는 페이지가. 이 때, 메모리에서 어떤 페이지를 제거해야 할까요? 가장 오래 전에 사용이 된 것을 제거하는 것을 LRU 알고리즘이라고 합니다. 약어로는 Least Recently Used한 것을 제거하는 것이죠. 보통, 이러한 문제를 만났을 때, 저는 map 2개로 많이 코딩하라고 이야기를 합니다. 그런데, STL을 쓸 수 없는 환경에서는 어떻게 해야 할까요? 코딩하기도 어려운 레드 블랙 트리를 500줄 가까이 작성해야 할까요? 아니면 포인터의 향연에서 벗어날 수 없는 skip list를 작..
자료알고/자료구조 2019. 9. 23. 21:33