자료알고/자료구조 검색 결과

해당 글 43건
프로그래머스 크게 만들기 : 쿼리 특징을 잡아봅시다.

자료구조는 어떻게 공부해야 하는가? 사실 명확하게 답을 드리지는 못하겠습니다. 문제 상황이 다르게 바뀌었을 때, 어떤 구조로 어떻게 optimize를 시켜야 하는지 생각해 보면, 생각보다 도움이 많이 될 듯 싶어요. 프로그래머스에는 '큰 수 만들기' 라는 문제가 있는데요. 이것을 어떻게 해결해야 하는지. 그리고 들어올 수 있는 문자 집합이 커지면 또 어떻게 해결해야 하는지 천천히 보도록 하겠습니다. 문제는 아래와 같습니다. 단, 남은 수들의 순서는 바뀌면 안 됩니다. 이 문제의 조건만 조금 바꿔서, 소문자로만 이루어진 길이 ? 이하의 문자열에서 ?개를 지워서, 사전순으로 가장 앞선 것을 만들라는 문제가 코테에 출제 되었습니다. 문자 집합만 다를 뿐이지, 풀이 자체는 동일하다는 거 보이시나요? k개를 일일..
자료알고/자료구조 2019. 11. 27. 18:52
완전이진트리 vs 포화이진트리 : 이 둘에 대해 알아봅시다.

Heap, 다른 말로 우선 순위 큐 알고리즘을 배우기 전에, 완전이진트리와 포화이진트리에 대해서 짚고 넘어가도록 하겠습니다. 트리에 대해서 이론적으로만 설명하면 재미가 없으니, 나올 때 마다 설명을 하는 게 맞는 듯 싶어요. 이진 트리라고 하면, 자식의 갯수가 최대 2개인 Tree를 의미합니다. 이 둘은, 균형 트리라는 공통점이 있어요. 다른 점은 무엇일까요? 이 둘을 영어로는 각각, Complete Binary Tree, Perfect Binary Tree라고 이야기를 합니다. 당연하게도, 포화 이진 트리는 완전 이진 트리이기도 합니다. 먼저 포화 이진 트리부터 그려봅시다. 먼저 잎이란, 자식이 없는 노드를 의미해요. 단말 노드라고 많이 이야기를 합니다. 일단 이들의 레벨이 모두 같다? 깊이가 모두 같..
자료알고/자료구조 2019. 11. 9. 02:48
전치 행렬 (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