전체 글96 [자료구조] 9장 Priority Queue 1. Priority Queue : 우선순위가 높은 데이터가 먼저 나감. 배열/연결리스트/힙으로 구현 가능. 2. Heap 완전 이진 트리 최대 힙: 부모 노드의 키 값이 자식노드의 키값보다 크거나 같음 최소 힙: 부모 노드의 키 값이 자식노드의 키 값보다 작거나 같음 힙은 배열을 이용해 만들면 효율적. 완전 이진 트리 -> 각 노드에 번호를 붙임 -> 배열의 인덱스 3. Upheap(삽입) 새로운 요소가 들어오면 일단 마지막 노드에 이어서 삽입 삽입된 위치에서 루트까지의 경로에 잇는 노드들을 비교, 교환 키가 부모 노드보다 작거나 같으면 종료. O(logn) 4. Downheap(삭제) 루트 삭제. 루트에서부터 단말 노드까지의 노드들을 교환해 힙 성질 만족. O(logn) 5. 힙정렬 n개의 요소를 최.. 2023. 12. 16. [자료구조] 8장 BST 1. BST : 이진 트리 기반 효율적인 탐색 가능 2. 이진 탐색 트리 정의 : key(왼쪽 서브트리) = 루트 -> 오른쪽으로 순회하는 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있음. 3. 이진 탐색 트리의 탐색 연산 4. 이진 탐색 트리의 삽입 연산 : 탐색을 하다가 실패한 위치가 새로운 노드 삽입의 위치. 5. 이진 탐색 트리의 삭제 연산 case1) 단말 노드 삭제: 부모 노드 찾아서 연결 끊음. case2) 자식이 하나인 노드 삭제: 노드 삭제하고 서브트리를 부모 노드에 붙임. case3) 두 개의 자식을 가진 노드 삭제: 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져옴. 6. 이진 탐색 트리의 성능 : 이진 탐색 트.. 2023. 12. 16. [소응] 15장 Sponsored Search Markets 15-1 Advertising Tied to Search Behavior(검색 행동에 연결된 광고) 1. Paying per click 검색엔진이 어떻게 클릭당 가격을 설정할까? 이거 어려운 일!: 키워드 조합이 너무 많고, 수요가 변해 합리적인 가격을 유지하기 어려움.. 대신! 검색 엔진은 경매를 사용해 가격을 결정! 하나의 슬롯: sealed-bid second-price auction 여러 광고 슬롯이 다른 가치를 갖는 경우: 복잡해! 2. Designing an Auction 검색 엔진이 광고주의 클릭에 대한 가치를 알면 - slot과 advertiser간의 매칭 검색 엔진이 광고주의 가치를 모른다면 - truth bidding을 이끌어내거나 그냥 untruthful bidding 처리 VCG m.. 2023. 12. 15. [소응] 10장 Matching Markets 10-1 Bipartite Graphs and Perfect Matchings 1. Perfect Matching 모든 노드가 정확하게 하나씩 연결되어 있고, 어떤 왼쪽의 노드도 동일한 오른쪽 노드에 할당되지 않은 경우. 2. Constricted sets & Matching Theorem Constricted set(수축된 집합) biparite에서 perfect matching이 없음을 보여주기 위한 개념. 어떤 노드 집합 S에 대해 N(S)가 S의 이웃집합을 나타낸다고 하자. 이 경우, S가 수축된 집합인 경우는 S가 N(S)보다 훨 씬 큰 경우임.(위의 예시 참고) Matching Theorem 만약 양쪽에 동일한 수의 노드가 있는 이분 그래프가 perfect matching을 갖지 않았다면, 그.. 2023. 12. 15. [소응] 9장 Auctions(경매) 9-1 Types of Auctions 1. Auction의 종류(4) Ascending-bid auctions: 가격이 오르는 경매. 실시간 경매 등 Descending-bid auctions: 가격이 떨어지는 경매. 너무 비싸서 가격이 점점 떨어짐 First-price sealed-bid auctions: 봉투에 가격을 적어 seller에게 줌. 가장 높은 입찰자가 낙찰 받음. Second-price sealed-bid auctions: 봉투에 가격을 적어 seller에게 줌. 두번째로 높은 입찰자가 낙찰 받음. 9-3 Relationships between Different Auction Formats 1. Descending-Bid and First-Price Auctions descending-.. 2023. 12. 15. [소공] 11장 유지보수 11-1 유지보수의 소개 1. 유지보수 정의 : 개발 후 이뤄지는 소프트웨어 변경 작업. 수정 후 배포하는 작업. 2. 변경의 이유(5) 버그 제거 운영 환경의 변화 정부 정책의 변화 비즈니스 절차의 변화 미래 문제 배제를 위한 변경 3. 유지보수 유형(4) 수정형 유지보수 - 발견한 결함을 고치기 위해 수정 적응형 유지보수 - 변경된 환경에서도 사용 가능하게 소프트웨어 이식 및 변경 완전형 유지보수 - 성능이나 유지보수성을 개선하기위해 실시 예방형 유지보수 - 오류 발생을 방지 4. Lahman의 법칙(8) 시스템 타입 E타입: 계속 진화하는 타입(완전히 정의 X) S타입: 완전히 정의할 수 있는 타입(체스게임) 지속적인 변경의 원칙 - 지속적으로 좋은 방향으로 진화되어야 함. 엔트로피, 복잡도 증가의.. 2023. 12. 14. [소공] 9장 코딩 9-1 코딩 작업 1. 코딩 작업 과정(5) 코딩 표준을 만들기 프레임워크 패키지와 응용 패키지 결정 클래스 구현 끝나는 대로 인스펙션 클래스 단위로 테스트 응용 시스템으로 통합 2. 자주 발생하는 오류(11) ① 메모리 누수 : 메모리가 프리되지 않고 프로그램에 계속 할당되는 현상 ② 중복된 프리 선언 : 이미 프리로 선언된 자원을 한번 더 프리로 선언 ③ NULL의 사용 : NULL을 포인트하고 있는 곳의 콘텐츠를 접근. 이는 시스템 다운 시킴. ④ 별칭의 남용 : 서로 다른 주소 값을 예상한 두 변수의 값이 별칭 선언으로 같은 값이 되었을 때 오류 발생. ex. strcat(src, destn) ⑤ 배열 인덱스 오류 : 배열 인덱스가 한도를 벗어나거나 음수값을 갖는 경우 ⑥ 수식 예외 오류 : 0으.. 2023. 12. 14. 이전 1 2 3 4 5 6 ··· 14 다음
