본문 바로가기

분류 전체보기

 (774)
std::enable_shared_from_this [1. 개요]std::enable_shared_from_this 를 상속한 클래스 (여기서 템플릿 T는 상속한 클래스를 말함) 는멤버 함수 내에서 shared_from_this() 를 호출하여 자기 자신에 대한 shared_ptr 을 생성 할 수 있다. 이것이 주로 활용되는 시점은 다음과 같다.콜백에서 자기 자신을 공유해야 할 때 (재참조 할 때)자기 자신을 다른 shared_ptr 구조로 넘겨야 할 때기타...shared_ptr 을 공유한다는 의미는 아래와 같다.실제 객체는 하나임그러나 여러 곳에서 참조하게 됨그래서 더 이상 참조하는 곳이 없어지게 되면 해당 객체는 자동 소멸하게 됨.그래서, 콜백에서 자기 자신을 공유해야 한다는 것은 아래와 같은 의미가 있다.일반적으로 콜백이라 함 은 특정 이벤트 발..
... [1762] [1. 문제 설명]https://www.acmicpc.net/problem/1762[2. 풀이 접근]완전 탐색시간 초과 발생 사유...선형 탐색 안에서 이분 탐색 시, 선형 탐색 하는 양이 더 많아지게 된다면,,이분 탐색의 장점이 사라짐.즉, 서로 연결 된 두 점의 동시에 연결 되는 점을 찾기 위해서,선형 탐색 (outer) - 이분 탐색 (inner) 조합을선형 탐색 (outer) 의 대상이 되는 노드 의 차수가 항상 더 낮은 값이 오도록 하는 편이 좋다.[3. 코드]
mo`s. [13548] [1. 문제 설명]https://www.acmicpc.net/problem/13548[2. 풀이 접근]동일한 숫자의 발생 횟수를 저장할 배열이 필요함. (occurs)index: 수열의 원소value: 현재 구간에서 해당 원소의 발생 횟수발생 횟수에 대해서 해당 횟수만큼 존재하는 숫자의 개수. - 3이라는 원소가 4번 발생하고, 5라는 원소가 4번 발생한 경우- 4번 발생한 원소의 개수는 2개가 된다.index: 횟수value: 횟수만큼 존재하는 숫자의 개수.즉, 쿼리에 대해서 각 포인터가 (Left, Right) 넓혀지는 방향으로 움직이는 경우.구하고자 하는 최대 값이 갱신 되는지 확인 하도록 한다.반대로, 각 포인터가 좁혀지는 방향으로 움직이는 경우.현재 포인터가 가리키는 원소 a 의 발생 횟수가 1..
제곱근 분할법 [1. 개요]배열에 대한 제곱근 분할법이란배열을 길이의 제곱근 단위로 나누어 구간에 대한 쿼리를 처리하는 것이다.즉, 오프라인 쿼리 처리에서 매우 유용하지만, 수정이 불가능한다는 단점이 있다.[2. 상세]배열의 특정 구간에 대해 최대값, 최소값 등을 계산해야 한다고 할 때,세그먼트 트리 등을 이용해 처리할 수 도 있지만, 배열을 특정한 크기로 묶어서(이하 블록) 아래와 같이 처리 할 수 있다.쿼리 구간 [L, R] 이 블록 들에 interleave 한 경우 쿼리 구간 [L, R] 이 전체 블록을 포함 하는 경우전체 배열의 길이를 N , 블록의 크기를 K 라 할 때, 1번 경우는 아래와 같다.L 이 왼쪽 블록에 포함되고R 이 오른쪽 블록에 포함 됨.이 경우, 쿼리의 시간복잡도는 2K2번 경우는 전체 구간이..
제곱근 분할법. [13546] [1. 문제 설명]https://www.acmicpc.net/problem/13546[2. 풀이 접근]완전 탐색으로 풀이L -> R 방향으로 배열을 순회하면서배열의 값을 index 로 하여 배열의 값의 최초 출현 위치를 기록하고,2회 이상 출현 시, 최초 저장 된 위치를 이용하여 구하고자 하는 길이를 계산 하고,필요 시, 전체 결과를 갱신하도록 한다.완전 탐색 풀이는 배열의 길이와 쿼리의 개수로 보아 그 시간 복잡도는 O(NK) 이고,N 과 K 모두 최대 100,000 이므로, 시간 조건을 만족하지 못함. 여기서, 배열 내 값이 변하지 않고 현재 쿼리의 결과가 나중 쿼리 결과에 영향을 주지 않으므로 오프라인 알고리즘 적용을 고려해 볼 수 있다. 오프라인 알고리즘으로 풀이제곱근 단위로 배열을 분할 및 mo..
Placement new [1. 개요]placement new 라는 문법(혹은 기능) 은 일반적인 동적 할당 보다 조금 더 세밀하게 메모리의 수명을 관리할 수 있게 해준다. 일반적으로 객체를 대상으로 하는 new 는 메모리 할당 및 생성자 호출을delete 는 소멸자 호출 및 메모리 해제를 같이 진행 하게 해준다. 그러나, 아래와 같은 요구사항이 있을 수 있다.메모리를 할당만 하고, 생성자 호출은 뒤로 미루고 싶다.소멸자를 호출하여, 객체 내부의 메모리를 정리하지만, 객체 자체의 메모리는 당장 해제하지 않고 싶다.특히, 아래와 같은 상황도 있을 수 있다.공유 메모리를 대상으로 특정 객체를 공유하고 싶다.즉, 메모리는 이미 할당이 되어있지만, 객체의 생성자를 호출하고 싶다. 주의할 점은 소멸자가 자동으로 호출되지 않는다. (소멸자..
차분 배열 [19551] [1. 문제 설명]https://www.acmicpc.net/problem/19951[2. 코드]
차분 배열 [1. 개요]차분 배열은 배열을 효율적으로 구간 단위로 갱신 할 수 있도록 해주는 자료 구조이다.[a. b] 구간에 대해서 +k 를 하고,[c, e] 구간에 대해서 +m 을 하고,...이와 같은 방식으로, 구간 내 변화가 발생한다고 했을 때,단순한 방법으로는 각 구간을 iterate 하면서 업데이트 하는 방법 이 있지만,결국 필요한 구간 만큼 iterate 해야 하는 상황이 발생하게 된다.즉, 쿼리 개수 (Q) 와 구간의 길이 (L) 에 대해서 시간 복잡도 O(Q * L) 이 발생하게 된다. 그러나 차분 배열을 이용하면 동일한 작업에 대해서 시간 복잡도를 O(Q + L) 로 낮출 수 있다.[2. 차분 배열의 정의]어떤 배열 A 가 있을 때, 차분 배열 D 는 아래와 같이 정의 된다.D[0] = A[0]D..
radix tree [1. 개요] [3. 코드]
라빈-카프 [3033] [1. 문제 설명]https://www.acmicpc.net/problem/3033[2. 풀이 접근]완전 탐색으로 접근부분 문자열이 발생할 수 있는 대상은 아래와 같다.부분 문자열의 길이는 1 부터 L-1 까지길이 L-1 부터 발생 할 수 있는 모든 부분 문자열을 모두 확인하여 비교하는 방법라빈-카프 알고리즘 등을 이용하여 문자열 비교를 진행하더라도, O(L2) 의 시간 복잡도 발생이분 탐색으로 접근길이가 4인 부분 문자열이 2개 이상 존재한다고 했을 때,길이가 3인 부분 문자열의 존재는 굳이 확인하지 않아도 된다."ABCDE"FGH"ABCDE"XYZ=> ABCD 라는 중복 되는 부분 문자열이 있음을 바로 알 수 있다.즉, 중복 되는 부분 문자열이 있을 때, 그 보다 작은 길이의 부분 문자열의 중복 존재..

티스토리툴바