알고리즘33 [백준] 2957번: 이진 탐색 트리, 1539번: 이진 검색 트리 | C++ 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 1539번: 이진 검색 트리 P는 크기가 N인 배열이다. P에는 0보다 크거나 같고, N-1보다 작거나 같은 정수가 중복 없이 채워져 있다. 이진 검색 트리는 루트가 있는 이진 트리로, 각각의 노드에 정수 값이 저장되어 있는 트 www.acmicpc.net 거의 같은 문제! 틀린 이유 처음에 2957번 문제를 풀 때 그냥 BST를 구현했었다. #include #include #include #define MAX 100000 #define fse(A,B,C).. 2023. 5. 27. [백준] 2887번: 행성 터널 | C++ https://www.acmicpc.net/problem/2887 2887번: 행성 터널첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이www.acmicpc.net 접근방법1. MST문제다. union-find 써야 할 것 2. 모든 행성 간 가중치를 구하려면 N! 인데? 3. 행성 간 가중치는 행성 간 3차원 거리가 아니라 min(|xA-xB|, |yA-yB|, |zA-zB|) 이다. 4. x, y, z 대로 정렬 3번 수행하고 인접한 행성의 거리를 구한다. 5. 힙에 넣어 가중치 최솟값을 구한다면? 라고 생각회로 거쳤다. 정렬.. 2023. 5. 22. [자료구조] 세그먼트 트리을 이용해 구간 합 구하기 구간 합 구간 합을 구하기 위해 사용되는 방법은 세 가지이다. 1. for문으로 해결하기 int ans = 0; for (int i=l; i 2023. 5. 21. [알고리즘] 해시 충돌 해결 방법 | Hash Collision Seperate Chaining 추가적인 공간을 활용해 충돌을 해결한다. seperate 뜻에 맞게 Linked-List를 사용한다. 보통 헤드에 삽입한다. (테일에 삽입하면 테일까지 가는 시간이 걸리기 때문) 최악의 경우 하나의 해시에 데이터가 몰리면, 조회할 때 Linked-list를 탐색하는 시간이 걸리게 된다. Open Addressing Linear Probing 해시 충돌 발생 시 충돌이 발생하지 않을 때까지 해시를 linear 하게 탐색한다. 단, clustering 군집현상이 발생할 수 있다. Quadratic Probing 충돌 발생 시 해싱 함수에 특정 연산을 더해 새로운 해시를 제작한다. 보통 제곱연산을 쓰는데 추가적인 상수곱이나 제곱연산이 가능하다. 사진을 예시로 3번째 값 hf_q.. 2023. 5. 3. [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. [알고리즘] 배낭 알고리즘 (fractional 배낭, 0-1 배낭) 분할 가능한(fractional) 배낭 알고리즘 문제 도둑은 W만큼 들 수 있는 가방을 가지고 있다. W를 초과하는 보석을 담을 경우 가방이 찢어져 버리고 만다. 무게가 w고 가치가 v인 N개의 보석이 존재할 때 도둑이 훔칠 수 있는 보석의 최대 가치를 구하라. (보석은 분할 가능하다.) 그리디 알고리즘을 다룰 때 가장 자주 나오는 문제이다. 브루트포스를 사용해 훔칠 수 있는 보석의 모든 조합을 구할 수 있겠지만 N개의 보석의 모든 조합을 구하려면 O(2^N)의 시간이 걸릴 것이다. (보석을 훔친다 || 안 훔친다.) * N개 따라서 그리디하게 접근하면 효율적으로 해결할 수 있다. 무게 대비 가치가 높은 것부터 가방을 채우면 되지 않을까? N개의 보석을 v/w가 높은 순으로 정렬 후 W만큼까지만 훔쳤을 .. 2023. 4. 29. [알고리즘] 퀵 정렬과 병합 정렬 퀵 정렬 배열에서 기준값(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. [자료구조] B-tree와 B+tree 이진트리 종류 정이진트리 Full Binary Tree 트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 경우 (한국의 교재에선 포화이진트리라고 번역된 게 있는데 둘은 다른 개념이다.) 포화이진트리 Perfect Binary Tree 말 그대로 마지막 레벨까지 노드가 꽉 찬 트리, (2^N-1)개의 노드를 가진다. 완전이진트리 Complete Binary Tree 마지막 레벨을 제외한 모든 레벨에서 순서대로 노드가 꽉 찬 트리, 마지막 레벨은 왼쪽부터 채워져야 한다. 균형이진트리 Balanced Binary Tree 말단 노드들의 레벨 차이가 최대 1레벨까지만 나는 트리, 균형이 깨지면 별도의 로직을 통해 다시 균형을 잡게 된다. 포화이진트리, 완전이진트리, 정이진트리는 이상적인만큼 현실에서 잘 찾아볼.. 2023. 4. 24. 이전 1 2 3 4 5 다음
