컴퓨터공학54 [알고리즘] 배낭 알고리즘 (fractional 배낭, 0-1 배낭) 분할 가능한(fractional) 배낭 알고리즘 문제 도둑은 W만큼 들 수 있는 가방을 가지고 있다. W를 초과하는 보석을 담을 경우 가방이 찢어져 버리고 만다. 무게가 w고 가치가 v인 N개의 보석이 존재할 때 도둑이 훔칠 수 있는 보석의 최대 가치를 구하라. (보석은 분할 가능하다.) 그리디 알고리즘을 다룰 때 가장 자주 나오는 문제이다. 브루트포스를 사용해 훔칠 수 있는 보석의 모든 조합을 구할 수 있겠지만 N개의 보석의 모든 조합을 구하려면 O(2^N)의 시간이 걸릴 것이다. (보석을 훔친다 || 안 훔친다.) * N개 따라서 그리디하게 접근하면 효율적으로 해결할 수 있다. 무게 대비 가치가 높은 것부터 가방을 채우면 되지 않을까? N개의 보석을 v/w가 높은 순으로 정렬 후 W만큼까지만 훔쳤을 .. 2023. 4. 29. [자료구조] AVL 트리, Red-Black 트리 AVL 트리 AVL트리는 발명가 Adelson-Velsky, Landis 이름 앞글자에서 따온 균형이진탐색트리이다. 스스로 균형을 잡는 트리로 처음 고안됐으며 말단 노드의 레벨 차이가 항상 1이하로 나는 트리이다. 노드 삽입, 삭제 시 균형이 깨진다면 스스로 조절하기 때문에 높이는 항상 logN이 보장된다. Red-Black 트리 아래 다섯 조건을 만족하는 트리를 레드블랙트리라고 한다. 마찬가지로 균형이진탐색트리이므로 높이는 logN이다. 모든 노드는 Red / Black 의 색을 가져야 한다. 루트 노드는 항상 블랙이다. NIL 노드는 항상 블랙이다. (value가 없는 말단 노드를 항상 가진다. NIL == Null Leaf) 레드 노드의 자식 노드는 항상 블랙이다. (블랙 노드는 상관 없다) 각 노.. 2023. 4. 28. [네트워크] 네트워크 성능 분석 명령어 ping ping(Packet INternet Groper)은 네트워크 상태를 확인하려는 대상 노드를 향해 일정 크기의 패킷을 전송하는 명령어 이다. 해당 노드까지 패킷 수신 상태, 도달하기까지 시간, 네트워크 연결이 잘 돼 있는지 확인할 수 있다. ICMP 프로토콜(OSI 3계층)을 사용한다. netstat 접속되어 있는 서비스들의 네트워크 상태를 표시하는 데 사용되며 네트워크 접속, 라우팅 테이블, 네트워크 프로토콜 등 리스트를 보여준다. nslookup DNS에 관련된 내용을 확인하기 위해 사용하는 명령어이다. 특정 도메인에 매핑된 IP를 확인할 때 사용한다. tracert(Windows), traceroute(Linux) 목적지 노드까지 네트워크 경로를 확인할 때 사용하는 명령어이다. 목적지 노드.. 2023. 4. 27. [알고리즘] 퀵 정렬과 병합 정렬 퀵 정렬 배열에서 기준값(Pivot)을 설정해 작은 값은 왼쪽에, 큰 값은 오른쪽에 배치한다. 재귀적으로 분할해 정렬을 수행한다. pivot, left 인덱스와 right 인덱스를 설정한다. left값이 피봇보다 작으면 오른쪽으로 이동하고 크면 stop, right값도 똑같이 피봇보다 크면 왼쪽으로 이동하고 작으면 stop한다. 둘 다 stop인 경우 두 값을 swap한다. left 인덱스와 right 인덱스가 만날 때까지 수행하고, 그 인덱스를 기준으로 파티션을 분할해 정렬을 수행한다. 평균 시간복잡도는 O(nlogn)이지만 최악의 경우(오름차순 되어 있는데 내림차순으로 변경할 때) O(n^2)이다. 병합 정렬 https://i.namu.wiki/i/4JKVP3wRyMYaDKU_CBtFlxlJletKN.. 2023. 4. 26. [자료구조] B-tree와 B+tree 이진트리 종류 정이진트리 Full Binary Tree 트리의 모든 노드가 0개 혹은 2개의 자식을 가지는 경우 (한국의 교재에선 포화이진트리라고 번역된 게 있는데 둘은 다른 개념이다.) 포화이진트리 Perfect Binary Tree 말 그대로 마지막 레벨까지 노드가 꽉 찬 트리, (2^N-1)개의 노드를 가진다. 완전이진트리 Complete Binary Tree 마지막 레벨을 제외한 모든 레벨에서 순서대로 노드가 꽉 찬 트리, 마지막 레벨은 왼쪽부터 채워져야 한다. 균형이진트리 Balanced Binary Tree 말단 노드들의 레벨 차이가 최대 1레벨까지만 나는 트리, 균형이 깨지면 별도의 로직을 통해 다시 균형을 잡게 된다. 포화이진트리, 완전이진트리, 정이진트리는 이상적인만큼 현실에서 잘 찾아볼.. 2023. 4. 24. [운영체제] 세마포어와 뮤텍스 공유된 자원에 여러 프로세스가 동시에 접근하면 문제가 발생할 수 있다. 이러한 문제를 제한하기 위해 고안된 방법이 세마포어와 뮤텍스이다. 이때 각 프로세스가 접근하는 공유 데이터 부분을 임계 구역(Critical Section)이라고 한다. 세마포어: 멀티 프로세스 환경에서 공유 자원에 대한 접근을 제한하는 방법 뮤텍스: 임계 구역을 가진 스레드들의 실행시간이 서로 겹치지 않고 각각 단독으로 실행되게 하는 기술 상호배제(Mutual Exclusion)의 약자이다. 뮤텍스보다 세마포어가 좀 더 상위 개념이다. 세마포어의 P, V연산 P연산: 임계 구역에 들어가기 전 수행 (프로세스 진입 여부를 자원의 개수 S를 통해 결정) V연산: 임계 구역에서 나올 때 수행 (자원 반납 알림, 대기 중인 프로세스를 깨우.. 2023. 4. 22. [네트워크] 주소창에 URL을 입력 시 일어나는 일 요약 주소창에 도메인을 입력한다. 브라우저가 캐시에서 DNS 기록이 있는지 확인한다. 없다면 ISP의 DNS 서버가 도메인을 호스팅하는 IP주소를 찾기 위해 DNS 쿼리를 날린다. 브라우저가 해당 서버와 TCP 연결을 한다. 브라우저가 웹서버에 HTTP 요청을 보낸다. 서버는 요청을 처리하고 응답을 보낸다. 서버는 HTTP 응답을 보낸다. 브라우저는 HTML 콘텐츠를 가시화한다. DNS(Domain Name System)은 URL의 이름이고 특정 IP 주소와 연결되어 있다. 모든 URL은 유일한 IP 주소와 매치된다. IP주소는 요청하는 웹사이트의 서버 호스트 컴퓨터에 종속된다. 예를 들어 www.google.com URL이 20.85.227.104 IP주소를 가지는 것처럼. #2 DNS 기록을 찾기 위.. 2023. 4. 21. [네트워크] OSI 7계층, PDU OSI 7 Layers OSI(Open Systems Interconnection) 모형은 네트워크 통신을 저수준에서 고수준까지 7단계로 분류한 것이다. 인터넷에서 컴퓨터들이 서로 정보를 주고 받는 데 쓰이는 프로토콜의 집합이다. 1단계부터 4단계까지는 저수준, 5단계부터 7단계까지는 고수준 계층이라고 한다. 네트워크의 기본 원리는 '데이터를 받아서 가야 할 곳으로 전달해 주는 것'이다. 저수준일수록 하드웨어적, 전기적, 기계적 관점으로, 고수준일수록 응용 프로그램과 사용자 영역관점으로 다룬다. 이 계층들은 특정 계층이 변경되었을 때 다른 계층이 영향을 받지 않도록 설계되었다. 물리 계층 (Physical) 물리적으로 전류나 광신호, 라디오 신호를 통해 비트 단위의 데이터 전달이 이루어진다. 즉, 데이터.. 2023. 4. 20. 이전 1 2 3 4 5 6 7 다음
