자료구조 검색 결과

해당 글 34건
세그먼트 트리 구조에서 lazy propagation을 적용하는 코드를 뜯어봅시다.

안녕하세요. 백준에서 활동하고 있는 chogahui05입니다. 저번 lazy propagation 시간에는 변환을 합성한다는 관점에서 접근했습니다. 이번에는, 그것을 알고 있다는 전제 하에서, 어떻게 코드를 이해하셔야 할 지 설명을 해 보도록 하겠습니다. 이 글에 있는 코드는 설명을 위해 중요 부분만 간략화 한 것임을 참고해 주시면 감사하겠습니다. 먼저, lazy는 누적된 변환이라는 것이 핵심이라고 했습니다. 그러면, 누적된 변환이라는 개념이 왜 나왔는지부터 생각해 봅시다. 그 전에, 연속된 k개의 구간을 어떻게 처리할 것인지부터 고민해 봅시다. 보통의 segment Tree에서 연속된 k개의 구간을 업데이트 하는 연산은 klogn번만큼 수행이 됩니다. 문제는, 이런 쿼리가 50만개 들어왔다고 생각해 봅..
자료알고/자료구조 2020. 3. 31. 00:34
유니온 파인드 (union find) : 병합 연산과 루트를 찾는 연산만 있다.

안녕하세요. chogahui05입니다. 유니온 파인드 (Union find)는 2가지 연산을 지원하는 자료구조입니다. a와 b를 같은 집합에 넣는 것은 merge 연산으로 합니다. 같은 집합에 있는지 검사하기 위해서, find 함수를 호출합니다. 이 둘을 수행하는 구조인데요. 이 중에서 오늘은 경로 압축에 대해서 알아보겠습니다. 이것만 적용해도 상당히 빠르게 수행할 수 있습니다. 얼마나 빠르게 수행하는지는, 추후에 작성을 하도록 하겠습니다. 먼저 find 함수부터 보겠습니다. 되게 간단해 보이는데요. 여기서, p[x]는 x에서부터 타고 올라갔을 때, Root를 의미합니다. x의 부모가 x라면, 즉 자기 자신이라면, -1입니다. 3번째 줄은, 기저 조건입니다. 만약에 x의 부모가 -1인 경우에 바로 x를 ..
자료알고/자료구조 2020. 3. 14. 01:49
c언어 문자열 경계 검사에 대한 몇 가지 이야기

입력을 신뢰하면 안 된다. 현실 세계에서는 알고리즘 문제와 같이 제한에 맞춰서 입력이 들어오지 않는다. 이 말은 많이 들어보셨으리라 생각이 듭니다. c언어에서 많은 string 함수, 예를 들어서 strcpy, strcat 같은 것들이 이런 문제를 가지고 있다고 하는데, 무엇일까요? 문자를 5개 저장할 수 있는 배열을 선언했습니다. 문자열은 NULL 문자가 끝에 들어갑니다. 그러면, 길이가 4인 문자열까지는 들어갈 수 있습니다. 예를 들어 "cho"는 길이가 3인 문자열입니다. 그러므로, 들어갈 수 있습니다. 그런데, 이런 경우라면 어떨까요? "chogahui를 넣는다. 길이가 8입니다. 그런데, gets나, strcpy, strcat에 들어가는 정보는 string 배열의 시작 주소일 뿐입니다. 길이 값..
코딩/C 2020. 3. 9. 14:04
누적된 변환과 lazy propagation 알고리즘

안녕하세요. 2 ~ 3편에 걸쳐서, 레이지 프로퍼게이션을 적용한 세그먼트 트리를 쓰도록 하겠습니다. 세그먼트 트리에 쓰이는 lazy 기법을 1줄로 요약하면 아래와 같습니다. 네. 앞으로 쓸 2 ~ 3편 글에 대한 핵심입니다. 이것만 정확하게 이해하시면 됩니다. 정말 중요한 키워드는 굵게 강조 표시까지 했는데요. 변환, 흡수, 전파. 이 셋입니다. 변환, 흡수, 전파? 이게 대체 무엇을 의미할까요? 이번 시간에는 이 중에 첫 번째 키워드와 두 번째 키워드인 변환과 흡수에 대해 알아보도록 하겠습니다. 왜 자식에 전파하는지는 다음 포스트에서 이야기 해 보도록 하겠습니다. 1번 변환을 생각해 봅시다. 이 변환을 함수 f(v)로 표현해 봅시다. 그러면, f(v) = v + a가 됩니다. 다음에, 2번 변환을 생각..
자료알고/자료구조 2020. 2. 29. 22:37
균형 이진 트리 : 제약 조건이 맞지 않으면 추가적인 연산을 한다.

ps를 하시면, 많이 보는 자료구조 중 하나는, Java에서 TreeSet, TreeMap, C++의 STL에서는 Map, Set 등이 있습니다. 균형 트리로 구현이 되어 있다는 이야기는 많이 합니다. 이게 무엇일까? 에 대해서만 간단하게 생각해 보도록 하겠습니다. 필기 시험에 나올 때 상당히 매력적인 보기를 주는 경우도 있으니, 간단하게 개념을 짚고 넘어가시는 것도 좋겠습니다. 이진 트리를 생각해 봅시다. 이것은 기준 노드를 기준으로 그것보다 작으면 왼쪽에, 크면 우측에 옵니다. 그러면 1을 찾기 위해서는 몇 번의 탐색이 필요할까요? 3보다 작으므로 왼쪽으로 갑니다. 2보다도 작으므로 왼쪽으로 갑니다. 그랬더니 1이 있습니다. 3번 탐색하면 됩니다. 그러면 이 트리에서 -5를 찾기 위해서는 어떻게 해야..
자료알고/자료구조 2020. 1. 11. 03:28