728x90 공부164 C++ Sort() 사용 클래스 객체를 이용해서 정렬하는 건 실무에서 많이 사용되는 방법이고 프로그래밍 대회에선 실행 시간에 안 좋은 측면 때문에 자주 사용되지 않는다고 합니다. 실제로는 C++에 vector 라이브러리에, pair 를 더 많이 이용합니다. 정렬은 이미 만들어진 훌륭한 라이브러리가 많으니깐 원리를 이해하고 바로 라이브러리를 사용하면 좋겠죠! sort 함수는 라이브러리에 포함되어있고 pair는 라이브러리에 포함되어 있습니다. #include #include using namespace std; //sort 기준을 스스로 정할 수 있음 //단순 데이터 정렬 기법은 현실적이지 않음 bool compare(int a,int b){ return a < b; } int main(void){ int a[10] = {9, 3,.. 2020. 5. 30. 컴퓨터구조3 CPU 오늘은 컴퓨터의 Top-Level 구조에 대해 살펴보겠습니다. 현재의 컴퓨터들은 폰 노이만 구조입니다. 폰 노이만 구조의 특성은 세가지가 있습니다. 1. 데이터와 명령어가 RW memory 에 저장 (가장 큰 특성) 2. memory의 주소값에 의해 구분 3. 순차적 실행 반대로 Hardwired program 존재 하드웨어적으로 선이 연결이 되어 있는 프로그램입니다. 이는 쉽게 변경할 수 없습니다. 이 로직 함수 박스가 덧셈이라고 생각해봅시다. 그럼 숫자를 넣었을때 덧셈이 되겠죠. 근데 갑자기 나눗셈을 하고 싶습니다. 그러면 하드웨어 프로그래밍에서는 방법이 나눗셈 로직 함수 박스를 다시 들고와서 다시 꽂는 거 밖에 방법이 없습니다. 하지만 소프트웨어 프로그래밍에선 그냥 명령어를 '나눗셈'이라고 넣어주면.. 2020. 5. 29. 병합정렬 복습 저번 시간에서는 O(NlogN) 인 퀵정렬에 대해 배웠습니다. 하지만 퀵정렬은 정렬이 거꾸로 되어 있는 경우에 O(N^2)의 시간복잡도로 효율이 굉장히 안 좋아지는데요. 그에 반해 병합정렬은 O(NlogN) 의 시간복잡도를 보장해줍니다. 평균이 퀵정렬보다 빠르진 않지만 보장해준다는 면에서 굉장히 좋은 정렬 알고리즘임을 알 수 있습니다. 병합정렬도 퀵정렬과 같이 나누고 해결하는 '분할 정복(divide and conquer) 알고리즘' 을 사용하는데요. 여기서 병합정렬이 시간복잡도를 보장해주는 이유에 대해서 나옵니다. 병합정렬은 무조건 두개로 나눠줍니다. 그리고 합치면서 정렬을 수행합니다. 합칠때 계산 횟수가 n 번이기 때문에 병합정렬은 O(nlog n) 의 시간복잡도를 보장할 수 있는 것 입니다. i 번.. 2020. 5. 29. 퀵정렬 복습 오늘은 퀵정렬에 대해 배워보았습니다. 말에서 부터 뭔가 굉장히 빠를 거 같은 느낌이 들죠? 선택,삽입,버블 정렬은 다 O(N^2) 복잡도의 알고리즘이었는데요 . 퀵정렬은 무려 O(n log n)의 복잡도를 가지고 있습니다. log n 은 어마어마한 수인데요 생각해보면 n = 1000 log n = 10 정도고 n = 1000000 이면 n은 20 정도 입니다. 실제로 알고리즘을 조금 더 공부하면 log n의 대단함을 더 느낄 수 있다고 하네요. 이런 퀵정렬의 핵심은 "특정한 값을 기준으로 큰 숫자와 작은 숫자를 나누면 어떨까!" 입니다. 이 특정한 값을 보통 기준 pivot 값이라고 칭합니다. 퀵정렬은 큰 문제를 나눠서 해결하는 분할 정복 알고리즘에 기반하기 때문에 더 빠르게 정렬이 가능합니다. -> 특.. 2020. 5. 28. 이전 1 ··· 35 36 37 38 39 40 41 다음 728x90
