💻 CS15 메모리 조합칩 : 다양한 입력에 대한 출력을 내는 칩 순차칩 : 출력이 현재 시점과 이전에 처리했던 입출력에도 영향을 받는 칩 시간의 진행 틱, 톡 이라는 2진 신호를 연속적으로 생성하는 클럭을 이용해 모델링 가능하다. 주기 : 틱의 시작과 톡의 종료 사이의 시간 → 모든 메모리 칩의 작동을 조절 메모리장치 컴퓨터 프로그램은 변수와 같은 데이터를 유지하는 추상화 개념을 지원하며 이는 메모리를 통해 구현된다. 클록과 0과 1사이를 왔다 갔다 거리는 시간의존적 게이트를 통해 논리게이트가 상태를 유지하고 시간이 변함에 따라 응답하도록 한다. 이러한 게이트를 데이터 플립 플롭 DFF (모든 메모리 칩을 만드는데 기본구성블록)이라 불린다. 순차 논리 시간에 따라 기억하는 능력을 칩들은 가져야 한다. 시간의 문제 지연이 .. 2024. 2. 6. 그래프 탐색 -BFS, DFS 그래프 탐색 (그래프 순회) 하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것 BFS 너비 우선 탐색 시작 노드를 방문 표시 후 큐에 넣음 큐에 아무노드가 없을때까지: 큐 가장 앞 노드를 꺼낸다. 꺼낸노드에 인접한 노드들을 모두 보면서: 처음 방문한 노드면: 방문한 노드 표시를 해준다 큐에 넣어준다. BFS 알고리즘 시간 복잡도 BFS 노드 전처리 → O(V) 큐에 노드를 넣고 빼는데 걸리는 시간 → O(V) 큐에서뺀 노드의 인접한 노드들을 도는데 걸리는 시간 →O(E) ⇒총 O(2V+E) ⇒ O(V+E) DFS 깊이 우선 탐색 시작 노드를 옅은 회색 표시후, 스택에 넣음 스택에 아무 노드가 없을때까지 : 스택 가장 위노드를 꺼낸다. 노드를 방문 표시를 한다. 인접한 노드들을 모두 보면서: 처음 방문.. 2024. 1. 23. 그래프 연결 데이터를 저장 할 수 있는 자료구조 세상에는 다양한 연결 관계가 존재하기 때문에 그래프 자료구조는 이를 저장하기 유용하다. 그래프 용어 정리 노드 : 그래프에서 하나의 데이터 단위를 나타내는 객체 엣지: 그래프에서 두노드의 직접적인 연결 관계 데이터 엣지가 방향을 가지면 → 방향그래프 엣지가 어떤 정보를 나타내는 수치를 가지면 → 가중치그래프 차수 : 하나의 노드에 연결된 엣지들의 수 무방향 그래프 → 하나의 노드에 연결된 엣지들의 수를 나타낸다. 방향 그래프 → 노드를 떠나는 엣지의 수를 출력 차수 노드에 들어오는 엣지의수를 입력 차수로 부른다. 경로 : 한 노드에서 다른 노드까지 가는길 경로의 거리 비가중치 그래프 → 엣지의 수 가중치 그래프 → 엣지의 가중치 합 최단 경로 : 두노드 사이의 경.. 2024. 1. 22. 객체 지향 프로그래밍 _ SOLID 단일 책임 원칙 모든 클래스는 단 한가지의 책임만을 갖고 클래스 안에 정의 되어있는 모든 기능은 하나의 책임을 수행하는데 집중되어있어야한다. ⇒ 하나의 클래스로 너무 많은 일을 하지 말고 딱 한가지 책임만 수행하자 god object: 너무 많은 책임을 지니고 있는 객체 한 클래스는 한가지 책임에 관한 변경사항이 생겼을때 코드를 수정할수있도록 하자 개방폐쇄 원칙 클래스는 확장에 열려있어야 하며 수정에는 닫혀있어야한다. ⇒ 기존 클래스의 코드를 수정하지 않고도 기능을 확장할 수 있어야한다. 리스코프 치환 원칙 부모클래스의 인스턴스를 사용하는 위치에 자식 클래스의 인스턴스를 대신 사용했을 때 코드가 원래 의도대로 작동해야 한다. 형식적인 측면 : 자식클래스가 오버라이딩하는 변수와 메소드가 부모클래스에 있는 .. 2024. 1. 21. 이진 탐색 트리 (binary search tree) → 딕셔너리, 세트를 구현할 때 쓸수있다. 그 이유는 뒤에서 살펴 보겠다. 이진탐색트리속성 부모 노드 왼쪽에는 무조건 부모노드보다 작은 자식노드가 들어가고 부모노드 오른쪽에는 부모노드보다 무조건 큰 자식 노드가 들어간다. 배열이나 파이썬리스트로 구현하지 않고 노드 인스턴스를 연결해서 구현 모든 자식노드가 부모의 레퍼런스를 저장하고 있다. InOrder 순회를 하면 데이터의 값이 순서대로 출력된다. ⇒ ABCDEFGHI 삽입연산 새로운 노드 생성 루트 노드부터 비교하면서 저장할 위치 찾음 찾은 위치에 새롭게 만든 노드 연결 시간복잡도 : O(h) h=높이 탐색연산 주어진 노드의 데이터와 탐색하려는 데이터 비교 탐색하려는 데이터가 더 크면 노드의 오른쪽 자식으로간다. 탐색하려는 데이터가 더 작으면 노드의 왼.. 2024. 1. 19. 이전 1 2 3 다음
