반응형 💻 programming67 퀵 소트 (Quicksort) - c/c++ 20세기에 발견된 가장 중요한 알고리즘 중 하나 Mergesort와 함께 가장 많이 사용되는 정렬 알고리즘 재귀호출을 사용하며, Mergesort와 달리 파티션이라는 작업을 통해 어느정도 정렬한 뒤 재귀호출 수행 기본 아이디어 배열을 섞는다 파티션을 나눈다 : j를 기준으로 왼쪽에는 a[j]보다 작은 원소, 오른쪽에는 작지 않은 원소가 오도록 이동시킨다 : 여기서 j는 피벗 (pivot)에 해당한다 왼쪽 파티션과 오른쪽 파티션을 정렬한다 소스코드 /* C implementation QuickSort */ #include void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } int partition (int arr[], int low, int high) .. 2021. 5. 5. [Modern CMake] target_link_library, link_library (임시) modern CMake는 빌드 의존성 문제 및 빌드 속도 개선을 위해 CMake 3.0.0 버전부터 도입되었습니다. modern CMake에서는 기존의 link_library 대신 target_link_library를 사용할 것을 권장하고 있습니다. classic CMake의 문제는 무엇이었는지, 그리고 modern CMake에는 무엇이 변경되었는지 차례로 설명하겠습니다. 1. classic CMake 문제점 먼저 classic CMake의 문제점에 대해 알아보겠습니다. CMake 2.7.x 버전에는 link_libraries, include_directories 명령어를 이용하여 빌드 옵션을 지정하였습니다. ADD_COMPILE_OPTIONS ( ... ) INCLUDE_DIRECTORIES ( ..... 2021. 4. 15. 기초 기호 표 (Elementary Symbol Table) 기초 기호 표 (Elementary Symbol Table) I. 기호 표 (Symbol Table) 기호 표 (Symbol table)는 추상적 개념에 연산을 추가하기 위해 고안된 자료구조로, 컴파일러 또는 인터프리터와 같은 언어 변환기에서 사용하고 있습니다. 이번 강의에서는 기호 표 자료구조를 위한 메서드와, 구현 방법에 대해 알아보겠습니다. I-1. Basic symbol table API 기호 표의 기본 메서드는 다음과 같습니다. key와 value 저장하기 - void put (key, value) 주어진 key로 value 검색하기 - value get (key) 주어진 key로 value 삭제하기 - void delete (key) 모든 key 내용 불러오기 - Iterable keys() .. 2021. 3. 26. git 커밋 메시지를 작성하는 방법 (How to Write a Git Commit Message) 아주 유명한 블로거의 글을 참고하였습니다. chris.beams.io/posts/git-commit/ How to Write a Git Commit Message Commit messages matter. Here's how to write them well. chris.beams.io 왜 좋은 git 커밋 메시지를 작성해야 할까? 😒 git 저장소를 하나 골라서 커밋 로그를 한 번 비교해 보면 이해하기 쉽습니다. 먼저 예-전에 작성된 커밋 로그를 한 번 봅시다. $ git log --oneline -5 --author cbeams --before "Fri Mar 26 2009" e5f4b49 Re-adding ConfigurationPostProcessorTests after its brief remo.. 2021. 2. 26. 기본 정렬 (Elementary Sort) 기본 정렬 (Elementary Sort) 1. Comparable Interface 어떤 자료를 정렬하기 위해서는 대소관계를 판단할 수 있어야 합니다. Java에서는 대소관계를 판단할 수 있는 함수를 가지고 있다는 것을 보증하기 위해 Comparable Interface를 사용합니다. 이 인터페이스는 compareTo( )라는 메서드를 가지는데, 두 객체의 대소관계를 판단하여 작음(-1), 같음 (0), 큼(1)을 반환합니다. 1.1 Total order 객체의 크기가 비교 가능하려면 다음 규칙을 만족해야 합니다 v ≤ w 이고 w ≤ v 이면 v = w이다 v ≤ w 이고 w < x 이면 v ≤ x이다 v ≤ w 거나 w ≤ v 이다 1.2 Sort algorithm (c++) c++은 quick s.. 2021. 2. 26. 최대 합 부분 배열 (Maximum sub-array problem) 최대 합 부분 배열을 찾는 세 가지 방법에 대해 알아보자, 먼저 최대 합 부분 배열이란, 배열의 부분 배열들 중 원소의 합이 최대가 되는 부분 배열을 의미한다. 아래 예시에서는 arr[2 .. 6]이 최대 합 부분 배열이다. Largest Sum Contiguous Subarray - GeeksforGeeks (1) 전체 탐색: O(n^2) 가장 기본적인 방법으로 부분 배열의 시작을 i, 배열의 끝을 j라고 하고 이중 반복문을 이용하여 전체 탐색한다. int getMaxSumOfSubarrayWithBruteForce(const vector& arr) { int maxSum = -1; int tmpSum = 0; for(int i = 0; i < arr.size(); i++) { tmpSum = 0; f.. 2021. 2. 26. [TCP/IP] 멀티캐스팅 프로그래밍, 라우팅 테이블 업데이트 멀티캐스트란? 멀티캐스트(multicast)란 여러 호스트에게 데이터를 동시에 전송하는 것을 말합니다. 멀티캐스트가 수행되는 절차는 다음과 같습니다. 먼저, 클라이언트는 멀티캐스트 그룹에 참여 (join)해야 합니다. 멀티캐스트 그룹에 참여함으로써 해당 멀티캐스트 주소로 들어오는 데이터를 수신하고 싶다고 알릴 수 있습니다. 그룹에 참여하고 나면 서버가 멀티캐스트 주소로 데이터를 송신했을 때 멀티캐스트 그룹에 참여한 모든 클라이언트에게 데이터가 전달됩니다. 아래는 멀티캐스트 데이터 전송을 그림으로 표현한 것입니다. (ko.wikipedia.org/wiki/멀티캐스트) 멀티캐스트 주소 멀티캐스트 그룹에 참여하기 위해서는 멀티캐스트 주소를 이용해야 합니다. 그런데 모든 주소를 멀티캐스트 주소로 사용할 수 있는.. 2021. 1. 13. [TCP/IP] 2. TCP 서버 - 클라이언트 (IPv4) www.geeksforgeeks.org/socket-programming-cc/ Socket Programming in C/C++ - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 소켓 API를 사용하여 서버와 클라이언트의 통신을 수행하기 위해서는 클라이언트와 서버의 구분이 필요합니다. 서버와 클라이언트가 사용하는.. 2020. 12. 18. [TCP/IP] 1. 네트워크, 패킷 그리고 프로토콜 네트워크, 패킷 그리고 프로토콜 컴퓨터 네트워크는 수많은 호스트 (host)와 라우터 (router) 장비들로 구성되어 있습니다. 호스트는 웹 브라우저나 파일 공유 프로그램들을 구동하는 컴퓨터를 의미합니다. 호스트에서 동작하는 응용 프로그램이야 말로 네트워크의 '실 사용자'라고 할 수 있습니다. 라우터 (=게이트웨이)는 하나의 통신 채널 (communication channel)로부터 온 정보들을 다른 통신 채널로 전달하는 장비입니다. 프로토콜은 통신 프로그램 사이에서 교환되는 패킷에 대한 약속이자 정의입니다. 그 중에서 TCP/IP는 이러한 문제를 해결하기 위한 프로토콜의 모음 (protocol suite)중 하나입니다. TCP/IP 프로토콜 집합체의 중요 프로토콜에는 IP, TCP, UDP가 있습니다.. 2020. 12. 18. 이전 1 2 3 4 5 6 7 8 다음 반응형
