반응형 Algorithm/Sort4 Sort 고득점 kit 풀이 완료, 후기 정렬은 대학 1학년 과정부터 나오는 알고리즘으로 매우 기초적인 개념이다. 그러나 방대한 데이터범위가 주어졌을 경우에는 시간 복잡도를 줄이지 않으면 안되는 상황이 오게 된다. 고득점 Kit의 3문제에서는 모두 퀵정렬(Quick sort)를 이용했으며 시간 복잡도는 O(nlogn)이다. C++에서는 algorithm 헤더 파일에 sort함수가 내장되어 있고 sort함수의 3번째 인자에 boolean을 반환하는 함수를 넣어줘서 어떤 기준으로 정렬할 것인지도 정할 수 있다. 정렬 알고리즘은 그리디, 다이나믹, 크루스칼 등등 많은 알고리즘 안에서 이용 되므로 배우지 않으면 안된다. 문제모음 [난이도 하] H-Index kimcoder.tistory.com/96 [난이도 중] 가장 큰 수 kimcoder.tisto.. 2020. 9. 11. [정렬, 난이도 하] 프로그래머즈, H-Index 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이라고 했을 때 가능한 h의 최댓값을 구하는 문제이다. 단순히 citations를 오름차순으로 정렬하면 문제를 쉽게 해결할 수 있다. 오름차순으로 정렬한 후에 n-h번째에 있는 논문의 인용 수가 h이상이라는 뜻은, 논문의 인용수가 h이상인 논문의 수는 h개 이상이라는 뜻이 된다. 본인의 소스코드에서 사용한 정렬은 시간 복잡도가 O(nlogn) 이므로, 시간복잡도도 O(nlogn) 밖에 되지 않는다. 테스트케이스 16개 모두 통과 #include #include int maxi(int a,int b){ if(a>b) return a; else return b; } using namespace std; int solution(vector.. 2020. 9. 10. [정렬, 난이도 중] 프로그래머즈, 가장 큰 수 정렬 방식을 찾기에 쉬운 문제는 아니었다. 문자열을 그대로 내림차 순으로 정렬 한다면 예제 2에서는 30이 3보다 앞에 오게 된다. 303 2020. 9. 10. [정렬, 난이도 하] 프로그래머즈, K번째수 (벡터 복사) 기초적인 정렬문제이다. 구간을 잡고 정렬해서, 그 구간내에서 원하는 인덱스값을 추출하면 된다. 그런데 테스트케이스가 여러개이기 때문에 벡터를 테스트케이스마다 초기화해줘야 한다. 본인 같은 경우에는 구간을 잡을 때, 구간을 잘라서 다른 벡터에 따로 할당시켰다. 벡터를 할당하는 함수의 사용법이다. 할당받을 대상인 벡터를 V1이라고 하고 할당할 값들이 있는 벡터를 V2라고 한다면 V1.assign(V2.begin()+firstindex, V2.begin()+lastindex+1) 만약 V2벡터의 1번째 인덱스부터 4번째 인덱스까지 복사하여 V1벡터에 붙여넣고 싶다면 V1.assign(V2.begin()+1, V2.begin()+5) 로 작성한다. (2번째 인자 값의 이전까지만 포함) 통째로 복사하고싶다면 V1.. 2020. 9. 10. 이전 1 다음
