자료알고/알고리즘 검색 결과

해당 글 87건
프로그래머스 가장 큰 수 : 수 2개만 고려해 봅시다.

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

제가 제대로 된 코딩을 한 지 별로 안 되서 그런지, 백준 1442번 같은 문제를 만나면 당황스럽더라고요. 문제는 다음과 같습니다. 부끄럽게도, 어떻게 Dynamic programing을 해서 트래킹을 해야 할 지 감이 오지 않았습니다. 그러면 어떻게 해야 할까요? 손을 놓고 가만히 있어야 할까요? 아닙니다. 정확하게 문제를 앞쪽, 뒤쪽으로 나누었을 때, 적절한 전처리를 해서, 앞쪽만 보고 접근할 수 있다면, 양방향 탐색과 유사한, 중간에서 만나는 meet in the middle 이라는 기법을 고려해 볼 만 합니다. 코딩 테스트에서 제일 중요한 것은 문제를 어떻게 읽느냐였다고 했습니다. 앞에 15개, 뒤에 16개로 왜 나눌까요? 일단, 그 전에 R - L이 20만 이하인 경우부터 해결해 봅시다. 먼저,..
자료알고/알고리즘 2020. 1. 20. 16:01
백준 11691 lcm(i,j) : lcm과 gcd의 관계를 이용한 역발상이 필요하다.

오늘은 2019년 마지막 날이니, 마지막 날을 장식할 만한 포스트를 작성하도록 하겠습니다. 아래 수식의 결과 값을 10억 7로 나눈 나머지는 얼마일까요? 단, n은 2이상, 10^6 이하 자연수입니다. n = 10^6이면 대충 O(n)이나, O(128n)에 돌려도 무난할 복잡도입니다. 이것이 생각보다 꽤 큰 힌트 중 하나입니다. 먼저, 최대 공약수에 대한 관점을 비틀어 봅시다. a와 b의 최대 공약수가 g였다고 해 봅시다. 이걸 P라고 합시다. 그러면 위 수식이 성립합니다. 그런데 정말 그럴까요? 위 수식을 Q라고 해 봅시다. 만약에, gcd(a/g,b/g)의 값이 c이고, 이 값이 1이 아니라면, gcd(a,b)의 값은 gc가 됩니다. c가 1이 아니므로, gc의 값은 g가 아닙니다. 즉, not Q이..
자료알고/알고리즘 2019. 12. 31. 21:57
백준 팰린드롬 진법 : 후보해는 생각보다 많이 적다.

오늘 풀어볼 문제는 백준 팰린드롬 진법이라는 문제입니다. 난이도는 솔브드 기준으로 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