728x90 반응형 Computer Science16 그리디 알고리즘(Greedy Algorithm) 서론 영단어 greedy의 의미는 "탐욕스럽다"이다. 즉, 그리디 알고리즘이란, 탐욕스러운 사람처럼 눈앞에 보이는 이익만 쫓아가는 알고리즘을 뜻한다. 그리디 알고리즘이란 위와 같은 트리 구조에서, 왼쪽 노드로 가는 것이 가장 좋은 경로이지만 당장의 탐욕스러움으로 오른쪽 노드로 가는 것. 이러한 트리 탐색 알고리즘을 그리디 알고리즘이라고 한다. 언제 사용할까? 그리디 알고리즘은 * 동전 개수를 최소로 사용하는 문제. (가장 큰 금액의 동전을 많이 사용하면 된다) * 도시락을 하나씩만 데울 수 있는데, 먹는 시간을 최소화해야 하는 문제. (먹는 데 가장 오래 걸리는 도시락부터 데우면 된다) 와 같은 문제에서 유용하게 쓰일 수 있다. 2023. 5. 18. 알고리즘 성능 측정의 지표 - 빅오 표기법(Big-O Notation) 빅오 표기법 알고리즘의 성능을 측정하기 위한 가장 중요한 지표로 빅오 표기법이 존재한다. 빅오 표기법으로 시간 복잡도와 공간 복잡도를 계산할 수 있는데, 우선 빅오 표기법이 뭔지부터 알아보자. 위의 그래프가 빅오 표기법을 나타낸 그래프이다. 빅오 표기법은 크게 아래의 7가지로 나눌 수 있다. O(1) O(logN) O(N) O(NlogN) O(N^2) O(N^3) O(2^N) 빅오 표기법이란 간단히 설명해서 O() 괄호 안에 원하는 식을 집어 넣는다. 그리고 식의 계수는 다 떼어 버린다. 왜냐하면 10000000000N이 아무리 크다 하더라도 N이 극한에 가까워지게 되면 결국 N^2보다 작아지는 순간이 오기 때문이다! 그렇게 해서 어떤 식이 더 규모가 큰 식인지를 빅오 표기법으로 구분하는 것이다. O(1.. 2023. 5. 18. 완전탐색(Brute Force)과 백트래킹(Backtracking)의 차이 완전탐색(Brute Force) 1) 탐색 순서 브루트포스는 가능한 모든 해를 순차적으로 검사하는 방식이다. 모든 경우의 수를 하나씩 시도하여 정답을 찾을 때까지 모든 경우를 확인한다. 즉, 문제 공간의 모든 가능성을 전부 조사하는 방식이다. 2) 제약 조건 브루트포스는 문제의 제약 조건을 고려하지 않고 모든 가능한 해를 탐색한다. 제약 조건에 따라 해의 개수가 많아질 수 있다. 3) 탐색 중단 브루트포스는 모든 가능한 해를 탐색해야 하므로, 정답을 찾지 못하더라도 모든 경우를 검사한다. 따라서 실행 시간이 길어질 수 있다. 백트래킹(Backtracking) 1) 탐색 순서 백트래킹은 탐색 도중 불필요한 부분을 가지치기하여 탐색 공간을 줄인다. 유망한 후보 해를 따라가다가 더 이상 진행할 수 없는 상황에.. 2023. 5. 17. 사진 전송의 과정으로 보는 Base64, Segment, Packet, Fragment 서론 사진을 데이터로 전송해야 하는 상황이라고 가정해보자. 사진을 전송하려고 할 때, 색의 3원소인 RGB로 이미지를 전송한다고 하면, RGB 각각 8bit씩 총 24bit + 좌표 데이터(x: 8bit, y: 8bit) ⇒ 최소 40bit가 필요하다. 만약 200X200 픽셀에 사진을 다 채운다고 하면 40bit * 40000 ⇒ 1.6mbytes의 용량이 나온다. 만약 영상을 보낸다고 치면, 1초에 24장의 사진이 필요하므로 1.6 * 24 = 38.4mb의 용량이 필요하다. 그렇게 되면 용량이 기하급수적으로 상승하므로, 용량을 줄이기 위한 인코딩(압축)이 필요하다. 내 컴퓨터에서 상대방의 컴퓨터로 사진 전송을 한다고 치자. 이러한 Layer가 존재하는데, Application 영역 1번 영역 App.. 2023. 2. 6. 이전 1 2 3 다음 728x90 반응형
