전체 글 검색 결과

해당 글 904건
k번째 수 찾기 : count sort를 응용해 봅시다.

백준 11004번, k번째 수를 구하는 문제가 있습니다. 오름 차순으로 정렬하였을 때, k번째 수가 무엇인지를 묻는 문제입니다. 그런데 배열의 크기가 500만입니다. 그렇기 때문에 fast io를 쓴 다음에 sort를 쓰거나, 아니면 다른 방법을 써야 하는데요. 저번에 배운 count sort를 조금 응용해 보도록 하겠습니다. [관련 글] count sort에 대해 알아봅시다. 이게 k번째 수와 어떠한 관련이 있을까요? [0, 20억] 사이에 있는 수는 다음과 같이 표현할 수 있습니다. 65536a + b (단 a, b는 0보다 크거나 같고 65536보다 작은 자연수) 즉, 65536 진법으로 표현할 수 있습니다. 그러면 몫을 구할 때 (x>>16)을, 나머지를 구할 때에는 (x&65535)로 구할 수 ..
자료알고/알고리즘 2019. 8. 17. 18:27
선형 큐 : push 연산의 횟수만큼 크기를 할당하면 된다.

Queue를 직접 구현해야 할 때에는 어떻게 해야 할까요? 사실, 선형 큐를 먼저 고려합니다. 큐는 먼저 넣은 친구가 먼저 빠지는 특성을 지닙니다. 예를 들자면, 은행 창구를 생각해 보세요. 먼저 번호표를 뽑은 손님이 먼저 처리됩니다. 그런가요? 그렇기 때문에, 포인터가 front하고 rear, 이렇게 2개가 있는데요. front는 제일 앞에 있는 것을, rear는 제일 뒤에, 넣을 위치를 가리킵니다. 선형 큐를 구현할 때, 저는 is_full 처리를 하지 않아요. 그렇기 때문에 초기 크기를, 큐에 들어가는 원소의 갯수 + 10로 잡습니다. 예를 들어서, 가로 r개, 세로 c개의 맵이라면 BFS를 돌릴 때, rc만큼 들어가기 때문에 크기를 rc + 10 정도로 잡습니다. 처음에 front와 rear의 값..
자료알고/자료구조 2019. 8. 16. 23:57
양방향 탐색 : 시작점과 도착점에서 동시에 탐색을 한다.

bfs는 뎁스가 깊어질수록 생성되는 state 수가 매우 많아집니다. 그러면, depth를 줄일 수만 있다면, 속도가 획기적으로 개선된다는 이야기 또한 됩니다. 시작점과 도착점에서 동시에 bfs를 하는 방식을 양방향 bfs라고 하는데요. 이렇게 하면, s에서 e로 가는 최적해가 2x일 때, s에서 x만큼, e에서 x만큼의 깊이만 탐색하면 됩니다. s에서만 출발하면 2x만큼 탐색하는 것에 비하면 거의 절반 가까이 줄어버린 셈입니다. 일단 어떤 식으로 탐색을 하는지 개략적으로 보고, 입문 문제를 풀어보도록 합시다. 백준에서 흔히 알려진, 루빅의 사각형은 구현이 안 되면 매우 힘든 문제이기 때문에, 입문 문제로 제외하였습니다. branch factor가 b라고 해 봅시다. 즉, 한 상태를 queue에서 뺐을 ..
자료알고/알고리즘 2019. 8. 16. 14:34
리눅스 fork 함수 : 프로세스를 생성한다.

오늘은 sleep sort에 나왔었던, unistd.h에 있는, 리눅스 fork 함수에 대해서 알아보겠습니다. int fork(); 이것만 보면 별 거 없어요. 그냥 프로세스를 생성해주는 역할을 합니다. 그런데, 리턴 값이 2개인데요. 예를 들어서 process A에서 fork가 호출되어서 process B가 생성이 되었다고 합시다. 그러면, A의 자식은 B가, B의 부모는 A가 됩니다. 그러면, 이 때, 프로세스 B에서는 0이라는 값이, 프로세스 A에는 B의 pid 값이 리턴이 됩니다. 이제 이 함수를 호출하면 어떤 식으로 흘러가는지 예제만 보도록 하겠습니다. 먼저 global 변수와, heap, stack 변수를 하나씩 생성했습니다. 그리고 10번째 줄에서 문제의 함수를 호출하였습니다. 일단, 그러면..
OS/리눅스 2019. 8. 15. 22:18
퀵 정렬 : bad partition이 발생할 경우 문제가 된다.

퀵 정렬 알고리즘은 간단하게 언급만 하고 넘어가겠습니다. 사실, ps에서 그리 많이 쓰이는 정렬 방법은 아니기 때문입니다. 다만, 평균적으로는 병합 정렬보다는 빠른데, 그 이유는 다음 시간에 평균 복잡도를 분석하면서, 언급하도록 하겠습니다. 먼저 퀵 정렬은 피봇을 잡는 것부터 시작합니다. arr의 [s,e] 구간을 정렬한다고 하면, pivot을 선택해서, 그 피벗이 있는 위치와 arr[s]의 값을 교환합니다. 이는, 피봇을 선택하는 함수와, 그걸 토대로 divide 하는 것을 별개로 생각하기 위해서입니다. 여기서 저는 pivot을 5로 잡았습니다. 그리고, 우리는 2개의 포인터를 잡을 겁니다. 이는 각각 le와 ri 포인터입니다. 어떤 식으로 교환이 일어나는지만 보시면 되는데요. 우리는 ri 포인터가 s..
자료알고/알고리즘 2019. 8. 15. 12:12