알고리즘 검색 결과

해당 글 51건
백준 팰린드롬 진법 : 후보해는 생각보다 많이 적다.

오늘 풀어볼 문제는 백준 팰린드롬 진법이라는 문제입니다. 난이도는 솔브드 기준으로 G3 ~ G1 정도 되는 문제입니다. x의 범위는 10^9입니다. 어떻게 풀어야 할까요? 먼저, x가 적당히 작은 수일 때에는 굉장히 쉽습니다. 이 때 난이도는 S5에서 S4 정도 됩니다. 그냥 2부터 n까지 z진법이 팰린드롬인지 검사하면 됩니다. zinbup 내부를 봅시다. yuki는 32개짜리 크기의 int형 배열입니다. zinbup 함수가 호출이 될 때 마다, 32개짜리 int형 배열을 초기화 시킵니다. 그리고 cur를 z로 나눠가면서 나머지 값만 계속 취합니다. 59 ~ 62번째 줄이 그러한 일을 수행합니다. p는 z진법으로 나타냈을 때 자릿수인데요. 팰린드롬이라면, 거꾸로 읽으나, 올바르게 읽으나 값이 같습니다. ..
자료알고/알고리즘 2019. 12. 21. 23:07
힙 정렬 (heap sort) : 최악의 경우에도 O(nlogn)이다.

오늘은 힙 정렬, Heap sort에 대해서 배워보도록 하겠습니다. 어렵지 않으니, 천천히 따라오시기만 하면 됩니다. 저번에, 우선순위 큐라는 자료구조를 배우셨을 거에요. 이 구조를 이용해서 정렬한 것입니다. 이게 끝입니다. 어렵지 않죠? 제가 우선순위 큐를 설명했을 때, 깜빡 잊은 것이 하나 있어요. 이것은, 이진 포화 트리를 만족한다는 것입니다. 그렇기 때문에, 트리의 깊이는 log(들어간 원소의 갯수)에 비례합니다. 그러면, 이것을 어떻게 구축할지가 문제입니다. Root를 0번 인덱스라고 합시다. 그리고 0번의 자식은 1, 2번이라 합시다. 그리고 1번의 자식은 3, 4번이라 합시다. 즉, 어떠한 노드 k가 있다면, 그들의 child는 2k+1과 2k+2가 됩니다. 그러면, 우선 순위 큐에 들어가는..
자료알고/알고리즘 2019. 12. 19. 21:17
0-1 bfs 알고리즘 : 가중치가 0과 1만 있을 때 최단거리는 어떻게 구할까요?

가중치가 0과 1만 있는 그래프에서 최단 거리는 어떻게 구할까요? 얼핏 들어서는 그냥 다익스트라를 잘 이용하면 될 거 같습니다. 그런데, deque나 Queue 구조만을 이용해서 코딩을 할 수 있습니다. 이게 어떻게 가능할까요? 먼저, 가중치는 0과 1만 있어요. 그리고 알고리즘 1은 위와 같습니다. 해석해 보면 그렇게 복잡하지 않아요. 시작 지점을 s라 합시다. 처음에는 s까지 최단 거리가 0이다. 라는 정보를 dq에 넣을 겁니다. 그리고, 자료 구조 dq의 앞 부분에서만 정보를 뺍니다. 이 정보는 to까지 min_dist가 cost다. 입니다. to와 인접한 지점을 a라 합시다. 이 때, to로부터 a까지 거리가 0이라면, a까지 거리에 대한 정보를 dq의 앞에 넣고, 아니라면 dq의 뒤에 넣습니다...
자료알고/알고리즘 2019. 12. 12. 20:28
등차수열에서 중간에 빠진 수 구하기 : binary search 기법으로 풀면 된다.

오늘 새벽에 들어온 문제 하나 보겠습니다. 당연하게도, brr은 오름차순으로 sort가 된 상태입니다. 쉬운 문제는 아닙니다. 다만, 아이디어를 얻을 수 있는 것 중 하나는 이진 검색이라는 것이 있어요. 링크 들어가셔도 좋을 듯 싶어요. 이것을 아신다는 전제하에 설명을 드리도록 하겠습니다. 먼저, 등차 수열 {a(1), a(2), ... , a(n)}이 있다면 임의의 1= 0일 때, a = 0이고 b = 1이거나, 혹은 a = 1이고 b = 0이여야 합니다. 그러면, 좌측에서 수가 빠지지 않았다면, 우측에서 탐색을 해야 하고, 반대로, 좌측에서 수가 빠졌다면, 왼쪽 구간을 탐색해야 할 거에요. 데이터를 볼까요? 문제를 보면, arr[mid] - arr[le]의 값은 8입니다. ..
자료알고/알고리즘 2019. 12. 10. 03:43
인트로 정렬 : c++의 sort는 왜 최악의 경우에도 빠르게 동작하는가?

C++의 sort는 어떻게 O(nlogn)의 복잡도가 보장될 수 있을까요? 저번에 compare 함수가 항상 True를 리턴할 때에 어떤 일이 일어나는가? 편에서 이 함수를 뜯은 적이 있었습니다. 그 기억을 되살려서 보도록 하겠습니다. Quick sort는 pivot을 어떻게 선택하느냐가 중요하다고 했어요. 저번에 median 값을 가지고 pivot값을 생성한다는 것을 알 수 있는데요. 이 방법을 저격하는 데이터가 있다는 것이 알려져 있어요. 그러면 이 방법을 어떻게 해결할까요? nth_element에도 적용되는 기법 중 하나인데요. 호출 깊이의 제한을 둡니다. first와 last가 다른 경우, __introsort_loop를 호출합니다. 그런데, 이것은, 3번째 인자에 이상한 __lg(__last -..
레퍼런스/분석 2019. 12. 7. 21:25