본문 바로가기

자료구조5

[자료구조] 세그먼트 트리을 이용해 구간 합 구하기 구간 합 구간 합을 구하기 위해 사용되는 방법은 세 가지이다. 1. for문으로 해결하기 int ans = 0; for (int i=l; i 2023. 5. 21.
[C++] pow함수 double 형의 정확성 문제 https://www.acmicpc.net/problem/1740 1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 합으로 표현되는 수를 생각할 수 있다. 예를 www.acmicpc.net 해당 문제를 풀다가 발견한 문제.. 분명 로직은 맞는데 어디서 틀린건지? 으잉? 분명 (맨앞) 1비트씩 차이나는데 왜 pow로 곱한 값은 같은 거지????? 문제를 발견하고 뒤적이기 시작했다. 아..하.. 실수 연산의 차이... 부동소수점.... 2023. 4. 30.
[알고리즘] 퀵 정렬과 병합 정렬 퀵 정렬 배열에서 기준값(Pivot)을 설정해 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치한다. 재귀적으로 분할해 정렬을 수행한다. pivot, left 인덱스와 right 인덱스를 설정한다. left값이 피봇보다 작으면 오른쪽으로 이동하고 크면 stop, right값도 똑같이 피봇보다 크면 왼쪽으로 이동하고 작으면 stop한다. 둘 다 stop인 경우 두 값을 swap한다. left 인덱스와 right 인덱스가 만날 때까지 수행하고, 그 인덱스를 기준으로 파티션을 분할해 정렬을 수행한다. 평균 시간복잡도는 O(nlogn)이지만 최악의 경우(오름차순 되어 있는데 내림차순으로 변경할 때) O(n^2)이다. 병합 정렬 https://i.namu.wiki/i/4JKVP3wRyMYaDKU_CBtFlxlJletKN.. 2023. 4. 26.
[C++] 우선순위 큐 오름차순(최소힙) 만들기 1. 기본 자료형 일 때 priority_queue q; 2. pair 자료형 일 때 priority_queue q; 2022. 12. 4.
코딩테스트를 위한 자료구조와 알고리즘 with c++ 독서기간_22년 11월 21일 ~ 22년 11월 22일 저자_존 캐리, 세리안 도시, 피야스 라잔 급하게 코테를 벼락치기 해야 할 일이 있어서 급하게 읽은 책^^ 이론 위주로 읽었다. C++ STL 라이브러리, 트리, 힙, 해시 테이블, 분할 정복, 그리디, 정렬, 그래프1, 그래프2, 동적 계획법1, 동적 계획법2로 목차가 구성되어 있다. 코테에 출제되는 수준의 알고리즘을 다룬다. 알고리즘이 이론뿐만 아니라 실무에서 성능을 고려하는 알고리즘을 사용하는 방법을 알 수 있다. 예를 들어, 블룸필터가 거짓-부정(false-negative)이 없다는 것은 확신하지만 거짓-긍정(false-positive)이 있다는 것은 확신하지 못하는 알고리즘이라면, 수억 개의 이메일에서 중복되는 이메일이 있는지 찾는 알고리즘.. 2022. 11. 24.

티스토리툴바