정렬 검색 결과

해당 글 14건
in place 알고리즘에 대해서 간단하게 알아봅시다.

정렬 알고리즘을 배우면서, stable 한지 그렇지 않은지는 많이 본 거 같습니다. 그런데 in-place 한지 여부도 분명 다룬 거 같았습니다. 그런데, 저는 이 부분에 대해서 잘 신경을 쓰지는 않았는데요. 쉽게 간과할 정도로 무지했던 셈입니다. 정리할 겸 겸사겸사 알아보도록 하겠습니다. 먼저, in place 알고리즘은 추가적인 메모리를 쓰지 않는 알고리즘? 그런데 아주 약간의 메모리를 써도 되는 알고리즘 정도로 문서에서 언급하고 있어요. 제가 보는 교과서에서는 constant한 공간을 쓰면 in-place 알고리즘이라고 언급하고 있습니다만, 대충 인풋 크기에 비해 정말 작은 메모리를 쓴다. 정도로만 이해하고 넘어가셔도 좋겠네요. 대충 input size가 500만 정도라고 생각해 보면, int나 l..
자료알고/알고리즘 2021. 9. 27. 04:21
백준 1060번 구간 : 후보해를 추린다.

이번 시간에는 백준 1060번 문제를 풀면서, 후보해를 어떻게 추리는지 보도록 하겠습니다. 문득 떠오르는 시스텟 페일 간단한 알고리즘을 물어보는 코딩테스트에도 이 글에서 간접적으로 설명한 것들은 나올 법 하니, 알아두면 좋을 듯 싶습니다. 사실 코테 접은 지 1년 넘어서 잘 모른다는 것은 함정입니다. 문제는 아래와 같습니다. 어떤 집합 S에는 양의 정수 L개가 있고, f(x)를 아래 조건을 만족하는 구간의 갯수로 정의합니다. 0보다 큰 정수 x, y가 있다고 한다면, f(x) < f(y)이거나, f(x) = f(y)이고 x
자료알고/알고리즘 2020. 12. 3. 01:21
백준 balanced cow subsets : 반으로 잘 쪼개 봅시다.

안녕하세요. 오늘은 USACO에 나왔던 Balanced Cow Subsets 문제를 풀어보도록 하겠습니다. 문제는 간단해요. 문제를 해석하는 연습을 하셨다면, 이 정도는 밑줄을 치셨으리라 생각이 듭니다. 왜 n이 20 이하일까요? 그냥 브루트 포스 해도 되는 거 아닐까요? 라는 생각을 하실 수도 있을 듯 싶어요. 그런데, 이 문제는 무려 옛날 USACO gold에 나온 문제입니다. 단순히 브루트 포스 해도 되었다면, Bronze에나 냈을 거에요. 그런데 Gold도 가끔 브루트 포스 하면 풀리는 게 있으니, 그렇게 해도 되지 않을까요? 그러면 어떻게 브루트 포스를 할 건가요? n = 20이라면 많아봤자, 2^20개의 상태가 있으니까, 이들에 대해서 일일히 check를 해 보는 방법이 있습니다. 그렇게 오래..
자료알고/알고리즘 2020. 2. 10. 01:33
프로그래머스 가장 큰 수 : 수 2개만 고려해 봅시다.

오랫만입니다. 정렬에 대해서 배웠으니, 오늘은 프로그래머스에 있는 가장 큰 수를 풀어보도록 하겠습니다. 쉽지 않아 보입니다. 옛날 (브, 실, 골 티어로 이루어진) USACO 실버나, 아니면 COCI 2번이나 3번 정도에 나왔던 문제로 기억합니다. 일단, 문제가 무엇을 요구하는지는 알았습니다. 조건을 해석해 봅시다. n의 최댓값이 10만이니, O(nlogn)이나, O(n) 정도의 복잡도를 생각할 수 있습니다. 물론, O(n^2)에서 상수 최적화를 잘 해서 통과할 수도 있겠지만, 상수 최적화 같은 경우에는, ps를 조금 깊숙히 하셔야 하는 부분입니다. 코딩 테스트에서 안 풀리는 복잡도가 정해인데 상수로 잘 뚫어야 하는 문제가 나왔다. 그러면 거르면 됩니다. 일단, 구하고자 하는 것은, 어떻게 배열을 적절히..
자료알고/알고리즘 2020. 1. 24. 02:58
java comparable vs comparator : 정렬을 할 때 많이 쓰는 것들을 알고 넘어갑시다.

Java에서 객체를 정렬하려면 어떻게 해야 할까요? 기본적으로 어떤 것을 비교 기준으로 삼을지가 중요하다고 했습니다. Key 2개를 비교하는 compare 기반 정렬이라면. 이는 Quick sort, merge sort, Tim sort 등이 그러합니다. 반면에 Key 2개를 비교하면서 정렬하지 않는 것도 있는데요. 대표적으로 기수 정렬이라던지, Count sort 등이 있습니다. Merge Sort는 잘 보면 Key 2개를 가지고 비교하면서, 정복하는 알고리즘임을 알 수 있어요. 그러면, 우리는 어떠한 두 원소를 비교했을 때 어떤 것이 우선 순위가 더 높은지 정하는 게 중요하다고 했습니다. 그러한 기준이 있는 것들은 따로 비교 기준을 정의하지 않아도 됩니다. 그런데, 이런 경우를 생각해 봅시다. 하고 ..
레퍼런스/예제 2020. 1. 15. 02:22