Computer Science72 [자료구조] 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. [소공] 7장 아키텍쳐와 패턴 7-1 아키텍처 기초 1. 소프트웨어 아키텍처 정의 : 소프트웨어 시스템에서 높은 수준의 구성요소와 그들의 관계, 상호작용 등을 의미. 2. 아키텍처 설계 정의 : 소프트웨어 시스템에 대한 전반적인 구조 설계하는 과정. (서브시스템 분할 및 덩어리화 작업, 서브시스템 상호 작동 결정, 서브시스템 인터페이스 결정) 3. 아키텍처 표현 관점(5) 논리적으로 분할된 서브시스템 서브시스템 사이의 인터페이스 컴포넌트 사이의 동적인 상호작용 서브시스템 사이에 공유되는 데이터 런타임에 존재하는 컴포넌트 위치 4. 아키텍처 중요성(4) 소프트웨어 시스템을 개발자가 잘 이해하기 위해 시스템의 일부는 독립적으로 작업하기 위해 시스템의 확장을 위해 재사용과 재사용 가능성을 위해 5. 아키텍처의 역할 : 소프트웨어 개발의 중.. 2023. 12. 14. [데이터베이스] 9장 트랜잭션 9-1 트랜잭션 개요 1. 트랜잭션 위의 상황에서 수정하고 있는데 중간에 컴퓨터 다운되면 어캄..? -> log를 유지하자! 두 가지 이상의 명령문이 실행될 때 중간에 다운 될 것을 고려하여 하나의 트랜잭션으로 취급해야함. 두 개 이상의 sql문들을 하나의 트랜잭션으로 취급하려면 사용자가 명시적으로 표시해야함. 이로써 모든 명령어가 실행되거나 모두 실행이 안되거나임. 2. 트랜잭션의 특성(ACID) Atomicity 원자성 - 모두 수행되거나 말거나 Consistency 일관성 - 트랜잭션 수행전과 다른 새로운 일관된 상태를 가짐. 일시적인 불일치 가능 Isolation 고립성 - 한 트랜잭션이 데이터를 갱신하는 동안 이 트랜잭션이 완료되기 전에는 갱신 중인 데이터를 다른 트랜잭션들이 접근 못하도록. D.. 2023. 12. 12. [데이터베이스] 8장 뷰와 시스템 카탈로그 뷰: 관계 데이터베이스 시스템에서 데이터베이스의 보안 메커니즘. 복잡한 질의를 간단하게 표현하는 수단. 데이터 독립성을 높이기 위해 사용. 시스템 카탈로그: 시스템 내의 객체에 관한 정보를 포함. 8-1 뷰 1. 뷰 한 사용자의 전체 외부 뷰 대신 하나의 가상 릴레이션을 의미. 뷰는 기존의 기본 릴레이션에 대한 SELECT문으로 정의됨. 뷰는 리렐이션으로부터 데이터를 검생하거나 갱신할 수 있는 동적인 창의 역할을 함. 스냅샷: SELECT문의 결과를 기본 릴레이션의 형태로 저장한 것. 2. 뷰의 정의 3. 뷰 사용시 DBMS에서 거치는 과정 4. 뷰의 장점 복잡한 질의를 간단하게 표현할 수 있게 함 데이터 무결성을 보장하는데 활용됨. - WITH CHECK OPTION을 사용하면 뷰가 선택할 수 없는 투.. 2023. 12. 12. 이전 1 2 3 4 5 6 ··· 8 다음
