솔

컴퓨터네트워크 책COMPUTER NETWORKINGA TOP-DOWN APPROACHEight Edition

버킷 정렬이란?bucket은 바구니를 의미합니다. 말 그래도 버킷 정렬은 바구니에 데이터를 담는 형태를 닮았다 하여 이름 붙여졌습니다.위 그림과 같이 숫자를 카테로리별로 나눠 바구니에 담은 뒤,그 바구니 안을 정렬해주는 방식입니다. 바구니 안을 정렬할 때는 앞에서 배웠던 정렬 방식 중 아무거나 사용하셔도 상관 없습니다. 저는 삽입 정렬을 이용해서 버킷 정렬을 구현해보았습니다.  코드)디버깅, 실행할 때 보기 편하도록 버킷을 출력해주는 함수를 추가해주었습니다.#include #include void Print(std::vector& v) { for (auto& a : v) { std::cout >& v) { for (int i = 0; i & v) { for (int i = 0; i = 0 &&..

DFS ( 깊이 우선 탐색 ) 와BFS ( 너비 우선 탐색 ) 에 대한 문제입니다. DFS는 그래프가 있을 때 인접한 vertex중 값이 작은 것부터 깊게 탐색하는 것이고,BFS는 그래프가 있을 때 인접한 모든 vertex를 값이 작은 순으로 탐색하고 그 다음에 깊게 들어가는 방식입니다. 따라서,DFS는 Stack 혹은 재귀를 사용하여 구현할 수 있고 (LIFO)BFS는 Queue 를 사용하여 구현할 수 있습니다. (FIFO) 코드)main함수입니다.문제에 맞는 조건의 수를 입력받아 그래프를 만들고 탐색하도록 작동시킵니다.int main(void) { int N, M, V; std::cin >> N >> M >> V; AdjMatGraph m(N + 1); for (int i = 1; i > u ..

1.61.7  1.8  1.13     1.14 1.15

1.7 The Power Wall 예시 현대의 문제는 전압을 낮추면 트랜지스터가 새는 것처럼 보인다는 것이다. 지금도 서버 칩 소비 전력의 40%가 누출로 인해 발생한다 만약 더 누출되기 시작하면, 전체 프로세스를 다루기 어려워질 수 있다. 이 문제를 해결하기 위해 노력했지만, 비용이 너무 많이 드는 문제로 새로운 방법을 찾았고, 처음 30년간 마이크로프로세서를 설계하던 방식과는 다른 길을 택했다.  ------------------------------------------------------------------------------------------------------------------1.8 The Sea Change: The Switch from Uniprocessors to Multi..

1.1 Introduction과거에는 컴퓨터 공상과학이었던 것들-자동차 안에 들어가는 컴퓨터 -휴대전화 -유전자 프로젝트 ( 비용 문제 )  -www ( world wide web ) -검색엔진  컴퓨터의 3가지 타입-Personal computers(PCs)개인용, 가장 잘 알려진 형태의 컴퓨터 -Servers네트워크를 통해서만 연결되는 컴퓨터 -Supercomputers하이엔드급의 컴퓨터, 복잡한 과학이나 공학계산 등에 쓰인다. -Embedded computers가장 광범위한 범주에 있는 컴퓨터이지만 볼 일이 없어 많은 사람들이 모른다. --------------------------------------------------------------------------------------------..

https://sol248.tistory.com/50 MergeSort (병합 정렬)이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하sol248.tistory.comhttps://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com  앞서 살펴본 퀵정렬과 병합정렬을 비교해보겠습니다. 먼저, 퀵정렬은 난수를 사..

https://sol248.tistory.com/51 QuickSort (퀵정렬)이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬sol248.tistory.com퀵정렬은 중복된 값이 많을수록 느리다는 단점이 있기 때문에 앞에서는 중복된 값이 없다는 가정을 하고 진행했습니다. 이것을 극복할 수 있는 방법이 3-way partitioning 입니다. 앞에서는 pivot 값보다 작은것과 큰 것 두 묶음으로 나누었지만, 여기서는key 값보다 작은 값,key 값과 같은 값,key 값보다 큰 값이렇게 3가지로 나눕니다. 구현 자체는 어렵지 않습니다. 코드) void Quick3way(..

이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬은 pivot 값을 중심으로 배열을 두 개로 나눕니다. 이떄 pivot 값은 어떤 값이 되어도 상관 없습니다. (pivot 값에 따라 시간 복잡도가 달라집니다) -퀵정렬 코드(난수x)int Partition(int* arr, int low, int high, int n) { int pivot = arr[size_t(floorf((high - low) / 2.0f)) + low]; int i = low; int j = high; while (true) { while (arr[i] pivot) j--; if (..

이번에는 병합 정렬에 대해 알아보겠습니다. 병합 정렬은 이전에 살펴봤던 Karatsuba algorithm 과 비슷하게, 데이터의 크기를 작게 쪼갠 후합치면서 정렬하는 방식입니다. Karatsuba algorithm이 궁금하신 분들은 아래 글 참고 부탁드립니다. https://sol248.tistory.com/46 Karatsuba AlgorithmKaratsuba Algorithm은 큰 문제를 잘게 쪼개서 하나씩 하나씩 결합하는 분할&정복 알고리즘 중에 하나입니다. 먼저, 문제를 어떻게 잘게 쪼개는지 살펴보겠습니다. 1234*5678을 예시로 살펴보죠.이런sol248.tistory.com   다음 사진은 병합 정렬의 작동 방식입니다.  작동 방식 자체는 간단하죠? 그럼 이제 코드를 한번 살펴보겠습니다...