자료알고 검색 결과

해당 글 130건
링크드 리스트 : 왜 순회 시간이 배열보다 오래 걸릴까요?

리스트와 배열의 차이점은 면접에서 자주 나오는 질문 중에 하나입니다. 저에게 메일로 질문이 들어온 것 중 하나는, 순회 속도가 어떻게 차이가 나느냐였습니다. n이 작을 때는 별 차이가 없을 수도 있습니다. 하지만 n이 3000 ~ 4000만 정도만 되도 이야기가 달라집니다. 배열은 순차적으로 저장이 되지만, 리스트는 그렇지 않습니다. cache를 이용하기 좋은 구조는 리스트보다 배열이라는 겁니다. 정말 그런지 실험을 해 봅시다. 배열과 링크드 리스트의 순회 성능 테스트를 위한 코드를 작성해 봅시다. node형을 하나 선언해 주었는데요. data 필드와, 다음 주소를 가리킬 필드를 선언해 주었습니다. 단일 링크드 리스트는 포인터가 1개, 더블은 2개일 거에요. C++의 리스트는 더블로 구현이 되어 있습니다..
자료알고/자료구조 2019. 7. 4. 18:08
냅색 알고리즘 문제 : 가방에 어떻게 넣어야 이득이 최대일까?

12번째 글은, 냅색 알고리즘 문제입니다. 이것도 꽤 여러 종류가 있는데요. 쪼갤 수 있는 물건이냐, 그렇지 못하냐에 따라서, 그리디로 접근을 할 수 있는지, 아니면 dp로 접근해야 하는지가 나뉩니다. 저는 0/1 냅색 문제를 다뤄 보겠습니다. 이것은 물건을 쪼갤 수 없어요. 물건이 n개가 있습니다. 그리고 가방에 넣을 수 있는 무게는 W입니다. 이 때, 가방에 넣을 수 있는 물건들의 최대 이익은 얼마나 될까요? 먼저 기저 조건을 생각해 봅시다. 물건 0개를 넣었을 때, 가방에 넣은 물건의 총 무게는 0, 이익 또한 0일 겁니다. 따라서, dp[0개][용량 0]을 넣었을 때 값은 0입니다. 대충 이런 경우입니다. 만약에 물건 0개를 넣었는데, 가방에 넣은 물건의 총 무게가 x(x>0)라면 이건 어떨까요?..
자료알고/알고리즘 2019. 7. 3. 00:25
dfs 심화편 : 깊이 우선 탐색의 단점을 어떻게 보완하는가?

dfs, 그러니까 깊이 우선 탐색의 단점은 크게 2가지입니다. 해가 없는 경로에 깊이 빠진다. 그렇기에 유한 시간 내에 끝나지 않을 수도 있다. 그리고, 해를 구했을 때, 그것이 최적이 아닐 수도 있다. 이 2가지 때문에, 보통 최단 거리를 구할 때에는 사용하지 않아요. 그런데, 이걸 잘 보완하면 절찬리에 써먹을 수도 있어요. 절찬리에 잘 써먹을 수 있는 문제 중에 하나를 예로 들어봅시다. 어떠한 세제곱 수를 k개 더해서 n을 만들어야 합니다. k값은 최소가 되어야 합니다. 예를 들어서, 43은 3^3 + 2^3 + 2^3으로 만들 수 있습니다. 물론 1^3을 43개 써서 만들 수도 있지만, 43개보다 작게 만들 수 있는 방법이 존재하기 때문에, 답이 될 수 없습니다. 이 문제는 어떻게 풀어야 할까요? ..
자료알고/알고리즘 2019. 6. 28. 01:14
외판원 문제 : 팩토리얼을 지수 복잡도로 낮춰보자

우리가 흔히 말하는 TSP, 외판원 문제는, 어떠한 도시에서 출발해서, 모든 도시를 방문하고 다시 출발점으로 돌아왔을 때, 최단 경로의 길이를 구하는 문제입니다. 이것을 단순하게, 모든 경우를 따져가면서 푼다면 n! 의 가짓수를 모두 따져야 할 겁니다. n이 12만 되어도 4억이 넘어갑니다. 이렇게 비효율적인, 팩토리얼급을 어떻게 지수급으로 낮추느냐가 핵심인데요. 중복된 상태를 memoi 하는 방법으로, O(n^2*2^n)으로 줄일 수 있습니다. dp를 다음과 같이 정의합시다. 시작점과 끝점은 0이라고 가정합시다. dp[state][s] : 현재 s에 있고, state 상태일 때 최단 거리. 그러면, 이 state가 무엇인지 궁금하실 텐데요. s에서 출발하였을 때, 방문한 도시들의 집합을 나타낸 겁니다...
자료알고/알고리즘 2019. 6. 27. 04:21
동적 배열 : expand 연산을 이해하는 것이 핵심이다.

보통 Dynamic array, 동적 배열이라고 하면 크기가 변하는 배열을 의미합니다. c++의 STL에서는 vector가, 그리고 Java에서는 ArrayList가 있어요. 그런데, push_back이나 add를 100만번, 200만번을 해도, 실제로는 그렇게 오래 걸리지 않는 듯 싶습니다. 이는 왜 그럴까요? ArrayList와 vector는 다음 두 함수가 있습니다. size와 capacity. 이 둘의 차이를 이해하기 전에, 배열에 원소를 추가할 때 어떤 식으로 처리해야 좋은지 생각해 보도록 합시다. 추가할 공간이 많이 남아 있습니다. 예를 들자면, 이 경우, 추가할 공간이 2개나 더 있습니다. 4 뒤에 추가해도 되는 상황입니다. 그러면, push_back이나 add가 호출이 되었을 때, 4 뒤에..
자료알고/자료구조 2019. 6. 23. 23:22