자료구조 검색 결과

해당 글 34건
전치 행렬 (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
평방 분할 (Sqrt Decompositon) : 루트로 쪼개보자.

세그먼트 트리를 모를 때, k번째로 빠른 수를 어떻게 찾아야 할 지 모를 때, 어떤 방법을 쓰면 좋을까요? n이 적당히 크다면, 우리는 이런 아이디어를 생각해 볼 수 있습니다. 구간이 n개가 아닌 sqrt(n)개. 그리고, 구간 별 원소 갯수도 sqrt(n)개. 사실, 이것을 응용한 알고리즘이 Mo's algorithm인데, 여기까지 다루지는 않겠습니다. 예를 들어, 배열의 임의의 원소가 구간 [1,9]에 속하는 자연수라고 해 봅시다. 이 때 배열 [1, 3, 3, 4, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9]에서, 13번째로 작은 수를 찾기 위해서 어떻게 하면 좋을까요? 일단, co[x]는 x가 나타나는 빈도수를 나타낸 겁니다. 그러면 단순하게 생각하면, 누적 값을 더해가면서, 1이 출현하..
자료알고/자료구조 2019. 9. 22. 00:18
자료구조 해시 테이블 : 직접 구현해 봅시다.

저번에 비둘기 집의 원리에 대해서 잠깐 언급을 했었습니다. 거기서, hash에 대해서 잠깐 언급을 했었는데요. 오늘은 이 hash를 STL 없이 직접 구현을 해 봅시다. 다음 시간에 String의 hashCode를 직접 구현해 보고, 백준의 듣보잡 문제를 풀어 봅시다. 사실 Hash는 크게 보면 딱 1가지만 주목하면 됩니다. 가 있을 때, 우리는 Key에 대응이 되는 bucket 값을 b(key)라 할 거에요. 예를 들자면, Key 값이 10101010입니다. b(10101010)의 값이 10이라면, 우리는 10번 버킷에 Value를 넣는 것입니다. Key가 정수인 경우, 함수 b는 Key 값에다가 버킷 갯수를 나눈 모듈러를 취하는데요. 예를 들어서, Key의 값이 2058370이고, 버킷 수가 100만..
자료알고/자료구조 2019. 9. 11. 01:30