본문 바로가기

📚 전공 공부/문제해결기법

(11)

[문제해결기법] 3. 자료구조1 1. RMQ : Range Minimum Query (범위 최소 쿼리) 배열의 부분배열에서 최솟값을 찾기 (1) O(n^3) 전처리, O(1) 질의 : brute force 방식으로 가능한 RMQ(a,b)에 대한 답을 모두 저장해놓는다. n^2칸을 채워야하고, 한 칸을 채울 때 최대 O(n)시간이 걸린다. (2) O(n^2) 전처리, O(1) 질의 : 가능한 RMQ(a,b)에 대한 답을 모두 저장하는데, RMQ(a,b+1) = min(RMQ(a,b) , A[b+1])을 사용하여 n^2칸을 각각 O(1)의 시간으로 채울 수 있다. (3) O(n) 전처리, O(sqrt(n)) 질의 : 배열을 sqrt(n) 묶음으로 나눈 후 각 묶음의 최솟값을 구하는데에 O(n)이 걸리며, RMQ(a,b)를 구하..

[문제해결기법] 2. 기초수학 1. 벡터의 외적 : cross product 2. 외적의 응용 : 부호 점검 3. CCW 알고리즘 : Counter-Clock Wise 세 점이 주어졌을 때 A->B와 A->C 두 벡터의 외적의 부호가 방향을 결정함. int ccw(int x1, int y1, int x2, int y2, int x3, int y3){ int tmp = x1*y2 + x2*y3 + x3*y1; tmp -= (y1*x2 + y2*x3 + y3*x1); if(tmp > 0) return 1; // a에 대해 b가 반시계 방향(왼쪽)에 있음 else if(tmp < 0) return -1; // a에 대해 b가 시계 방향(오른쪽)에 있음 else return 0; } 4. 응용 : 선분의 교차 여부 a-b를 이은 벡터 A에 ..

[문제해결기법] 1. C++ 1. 사용 언어 C : 가장 익숙하지만 지원 기능이 적음 C++ : STL에서 제공하는 기능을 활용 Java : java.util에 유용한 기능이 많다. 실행시간이 느려서 속도에서 제한을 받음 Python : 프로그래밍이 쉽지만, 실행시간이 가장 느리다. 2. 문제 해결 -> 기본적으로 자료구조, 알고리즘, 프로그래밍 능력을 묻는 문제 3. auto for(auto a : A){ ~ } 4. for : 반복문 5. pair 6. STL : standard template library made by HP in 1994 코드를 짧고 빠르게 작성할 수 있도록 도와줌. 7. template template const T& my_max(const T&x, const T&y){ return (y { 1, 3 } ..

이전 1 2 다음

728x90

티스토리툴바