CS 지식 (9) 썸네일형 리스트형 [객체지향의 사실과 오해] 01. 협력하는 객체들의 공동체 동아리에서 서버파트 튜터를 맡게 됐다.1,2주차가 객체지향에 관련된 과제인데 그에 대한 코드리뷰를 해줘야 한다.근데 나부터 객체지향이 뭔지도 잘 모르고 그저 개발을 해온 것 같아서조영호님의 '객체지향의 사실과 오해'를 구매하게 됐다. https://m.yes24.com/goods/detail/18249021 객체지향의 사실과 오해 - 예스24『객체지향의 사실과 오해』는 객체지향이란 무엇인가라는 원론적면서도 다소 위험한 질문에 답하기 위해 쓰여진 책이다. 안타깝게도 많은 사람들이 객체지향의 본질을 오해하고 있다. 가장m.yes24.com 워낙 유명한 책이라 옛날부터 읽어보고 싶었는데, 미루고 미루다 드디어! 구매하게 됐다.오랜만에 얇은 책을 봐서 더 기쁜 마음으로 정말 재밌게 읽고 있다. 내용을 잊지 않.. [한 권으로 끝내는 코딩테스트 with 파이썬] Chapter2. 자료 구조 배열배열은 같은 데이터 타입들의 원소로만 이루어지지만, 파이썬은 다른 데이터 타입이어도 한 배열에 담을 수 있다. 파이썬에서는 배열의 최대길이를 지정하지 않기 때문에 데이터를 추가하고 삭제하기 편리하다. 배열 인덱스에 접근하는 데 소요되는 시간: O(1)배열의 중간에 삽입하는 데 소요되는 시간: O(n)뒷부분에 있는 데이터를 한 칸씩 shift한 후에 데이터를 넣어야하기 때문 리스트 끝에 데이터를 삽입하는 경우: O(1)장점구현이 쉽고, 참조를 위한 추가 메모리가 필요 없음연속적이므로 메모리 관리에 편리인덱스를 통한 빠른 검색단점배열의 크기를 변경할 수 없고 사용하지 않는 공간으로 인한 메모리 낭비>> 파이썬의 리스트는 이런 단점을 보완함 문자열문자들의 집합문자를 저장하고 있는 "자료형" 인덱스는 관리하.. [컴퓨터 네트워크] connection-oriented service, connectionless service, sharing the links 네트워크 통신은 연결지향형 / 비연결지향형 service로 나뉜다. 연결지향형 servicea connection-oriented service인터넷의 connection-oriented service를 TCP라 부른다.client와 server의 연결이 설정된 후 데이터가 전송된다.프로토콜에 의해 연속적으로 패킷의 정보 상태 유지된다.모든 데이터는 적절한 순서를 유지하며 에러 없이 전달된다. 1:1 연결 상태를 유지하며 통신한다.이때 만들어진 연결 선로를 session이라고 한다. handshaking 과정은 TCP프로토콜에서 사용하는 개념이다. 통신을 시작하기 전에 연결을 설정하는 과정으로 3-way handshaking으로 불린다.SYN: TCP connection request > 클라이언트.. [알고리즘] HALTING Problem decision problem 컴퓨터 알고리즘에서 decision problem(결정 문제, 판정 문제)란 특정 입력에 대해 예-아니로 답이 있는 문제를 의미한다.이는 알고리즘 이론과 복잡도 이론에서 중요한 개념 중 하나이다. Halting Problemhalting problem(정지 문제)는 decision problem의 한 갈래로, "주어진 프로그램이 해결하고자 하는 문제가 해결 가능한지 말해줄 수 있는 일반화된 알고리즘이 존재하는가?" 라는 질문이다. 문제 정의프로그램 M과 입력 X가 있을 때, M에 입력 X를 시키면 종료할 것인가?M(X): 프로그램 M에 입력 X를 주고 실행시킨 상태사람이 문제를 푼다고 생각하고, M과 X가 모두 문자열이라 가정한다.모든 경우에 해결이 돼야한다.M(X)는 종.. Union Find & an Application Minimum Spanning Treecycle이 없지만, 전체를 커버한다.루트x, 방향성xKruskal Algorithm가장 작은 weight부터 edge를 추가한다.cycle은 없게 한다.N-1까지의 edge를 추가한다. > tree조건도 만족 Why is Kruskal Correct?cycle을 만들지 않는, 가장 작은 edge를 추가한다.↔ 만약 추가하려는 edge가 cycle을 만든다면, 추가하지 않는다.해당 edge를 추가하려면 cycle을 구성하고 있는 edge중 하나를 빼야한다.> 작은 edge부터 추가하고 있으므로 cycle 중 하나는 빼면 추가 하려는 것보다 더 작은 edge가 빠짐최단거리 아님. 모순 발생> 완벽한 증명은 아니지만 이런 아이디어로 진행된다. Union/Find or D.. Priority Queue & an Application Priority Queue란?일단 queue. 근데 우선순위가 존재한다.우선순위가 높은 노드부터 나오는 것한 마디로 1등만 조진다 !!Heap Structurecomplete binary tree왼쪽부터 다 채워져 있다. child 간의 순서는 없고, parent > child 의 순서만 맞춘다. 인덱스 i의 오른쪽 child : 2i인덱스 i의 왼쪽 child : 2i + 1 heap insert먼저 모양만 맞춘 상태로 insert > 가장 마지막 노드에 insert 한다.if) x 일단 x와 c를 바꾼다.x와 c의 자리를 바꾸게 되면 위와 같은 그림이 되는데, 원래 c → x와 a의 관계가 문제 하지만 상관없다! 또 비교해서 x > a라면 자리를 바꾸면 그만이다.insert solution이 위와 같.. AVL Tree AVL Tree Idea직관왼 / 오 무게가(개수가) 비슷하면 성능이 좋을 것이다. (log n과 n은 매우 큰 차이 ..!!)6이 root에 있는 한 해결불가 > 루트가 바뀌는건 필수적임if) 4가 루트가 되면 6의 왼쪽 child가 비어서 포인터만 이동하면 child 2개로 조정할 수 있다. AVL Tree DefinitionL: left sub tree 높이R: right sub tree 높이> 각각의 노드는 L과 R인 두개의 label을 가진다.조건: l L-R l > 만약 AVL Tree의 노드가 n개라면 높이는 O(lonN)이 된다.더보기l L-R l → 높이가 상대적으로 낮음 Down Sequence DefinitionLLRLRRLLRL..L과 R의 string루트에서부터의 움직임을 나타.. 컴퓨터 네트워킹 하향식 접근(Computer networking :a top-down approach) - 02 1.4 패킷 교환 네트워크에서의 지연, 손실과 처리율위 그림에서패킷이 업스트림 노트로부터 라우터 A에 도착→ 라우터 A는 패킷 헤더를 조사해 적당한 출력 링크 결정→ 선택된 링크로 그 패킷을 보냄 (패킷에 대한 출력 링크가 라우터 B에 이르는 링크) 이때,링크에 현재 전송되는 다른 패킷x, 큐에 자신보다 앞선 다른 패킷들x ≫ 링크로 전송링크 이미 사용 or 그 링크를 사용하기 위해 큐에서 대기하는 패킷o ≫ 인 투 더 queue~~ 지연 유형처리 지연패킷 헤더를 조사하고 그 패킷을 어디로 보낼지를 결정하는 시간패킷의 비트 레벨 오류를 조사하는 데 필요한 시간과 같은 요소를 포함할 수도 있다.큐잉 지연큐에서 링크로 전송되기를 기다리는 시간큐에 저장되어 링크로 전송되기를 기다리는 앞서 도착한 패킷의 .. 이전 1 2 다음
