자료알고 검색 결과

해당 글 130건
java queue : 어떻게 사용하는지 간단히 알아봅시다.

java에서 Queue는 어떻게 사용할까요? 저번 시간에 리스트를 잘 보셨다면, 대략적으로 감이 오실 거에요. 아. 이건 빼박 리스트구나. 사실 동적 배열을 이용해도 되는데요. 이것은 잘 생각해 보세요. 예제 프로그램을 봅시다. 일단 저는 my_Object 객체를 Queue에 넣을 거에요. 이건 아마 딱 봐도, 미로 찾기나, 어느 지점에서부터 최단 거리를 구할 때 쓰는 것 같군요. 이제 main 함수를 볼까요? 16번째 줄이 보이시나요? 저는 LinkedList를 쓸 거에요. LinkedList는 deque를, deque는 queue를 implements를 한 관계입니다. 이것은 Collections 시간에 다시 정리해 봅시다. 일단 오늘은, 아 이런 게 있구나. 정도만 보시면 되겠습니다. 사실 큐의 특..
자료알고/자료구조 2019. 8. 5. 17:48
약수 구하기 알고리즘 : n^0.5만 보고도 구할 수 있다.

약수를 구하는 것은, 정수론 문제를 풀 때 기본이 되는 연산 중 하나입니다. 우리는 약수를 구하는 알고리즘을 다음과 같은 구현을 생각할 수 있을 겁니다. 이것은 간단합니다. n의 약수를 구할 때, 나누는 수를 1부터 n까지 모두 검사해 봅니다. 만약에 n을 나누는 수 r로 나눴을 때, 나머지가 0이라면, r로 나누어 떨어지는 겁니다. 이것은 올바른 결과를 냅니다. 하지만, 오래 걸립니다. 예를 들어서, n의 값이 10^12만 되어도 아래와 같은 연산을 10^12번 해야 할 겁니다. 10^12번. 상당히 끔찍하지 않나요? 1초에 단순 연산을 10^9회 정도 한다고 한다면, 1000초, 약 20초, 어마무시한 시간이 걸려버립니다. 이 끔찍한 시간을 줄일 수 있는 방법이 없을까요? Lemma 하나 들고 옵시다..
자료알고/알고리즘 2019. 8. 4. 23:51
백준 1406 에디터 : List를 이용해서 해결해 봅시다.

링크드 리스트를 이용해서 간단한 편집 프로그램, 그러니까 vim과 같은 것들을 구현할 수 없을까요? 물론, 실제로 제가 구현할 것은 이것보다는 간단한 녀석입니다. 보통, 자료구조 프로젝트 때 적지 않게 하실 수도 있을 듯 싶네요. 사실 기능은 생각보다 단순해 보입니다. 커서를 이동시킵니다. 그리고 커서 앞에 문자를 추가시킵니다. + 앞에 't'를 추가시켰습니다. 이게 add 연산입니다. 아니면, 커서 앞에 있는 문자를 제거할 수도 있어요. 예를 들어서, 여기에서는 ( 앞에 있는 y라는 문자를 제거했습니다. 이런 간단한 편집 프로그램은 어떻게 구성하면 좋을까요? 단, 삽입, 삭제, 커서 이동 쿼리가 최대 60만개 들어옵니다. 배열은 장점이 무엇인가요? cache friendly 하다는 겁니다. 단점이 무엇..
자료알고/자료구조 2019. 8. 4. 00:57
기수 정렬 (radix sort) : 버킷만 있으면 된다.

오늘은 기수 정렬에 대해서 알아보도록 하겠습니다. 이것은 키 2개를 가지고 비교하는 정렬이 아닌데요. 이 특성은 저번에 배운, counting sort의 '2개의 키 값을 비교'하는 '비교 기반 정렬이 아니다' 라는 성질을 가지고 있습니다. 이들과, merge sort는 키 2개를 직접 비교하는 비교 기반 정렬이냐, 아니냐의 차이가 있어요. 아래 두 개의 글을 잘 보셔도 눈치를 채실 수 있을 듯 싶습니다. [관련글] 빈도를 저장하는 counting sort. 알아봅시다. 정렬된 두 배열을 합치는 합병 정렬 알아보아요. 그러면, 이것은 어떻게 동작할까요? 저는 1가지 용어만 정의하겠습니다. b진법으로 잡고 정렬한다. 버킷의 갯수가 b개이다. 우리는 양의 정수를 표현할 때, x진법으로 표현할 수 있습니다. ..
자료알고/알고리즘 2019. 8. 2. 01:07
병합 정렬 : sorting 된 두 배열을 합치면서 해결한다.

병합 정렬 (merge sort)는, 분할을 하고, 정복하는 단계에서 정렬된 두 배열을 합치는 식으로 동작합니다. 추가적인 공간이, 배열 크기만큼 필요하다는 것을 생각해 본다면, 메리트가 없을 수도 있어요. 실제로, Quick이 merge보다 빠르다는 이야기도 있을 정도이니까요. 그런데, Quick이 최악의 경우에 제곱에 비례하는 시간이 걸리는 반면에, merge는 그렇지 않아요. depth가 logn이기 때문입니다. 실제로 머지는 최악이던 최선이던 O(nlogn)에 동작합니다. 버블이나, insertion, selection sort에 비하면 꽤 빠릅니다. 일단 정렬이 된 두 부분 배열이 있다고 해 봅시다. 즉, le에서 mid까지 정렬이 되어 있고, mid+1부터 ri까지 sorting이 되어 있습니..
자료알고/알고리즘 2019. 7. 30. 20:46