본문 바로가기

Computer Science61

객체지향 프로그래밍에 대한 전반적인 정리 객체지향 프로그래밍이란? OOP (Object-Oriented Programming)이란 객체 지향적인 프로그래밍. 즉, C언어같은 절차 지향적인 프로그래밍(프로그램이 함수 단위로 순서대로 진행)이 아닌 프로그래밍에서 필요한 데이터를 추상화 시켜 상태와 행위를 가진 객체로 만들고, 그 객체의 관점에서 프로그래밍을 한다는 것이다 .객체들간의 상호작용을 통해 로직을 구성한다. OOP는 절차지향에 비해서 사람의 사고방식과 더 가깝다. OOP는 객체들의 유기적인 관계를 통해서 프로세스가 진행된다. 애플리케이션을 구성하는 요소들을 객체로 바라보고, 객체들을 유기적으로 연결하여 프로그래밍 하는 것을 말한다. 클래스, 객체, 인스턴스의 차이 객체 소프트웨어 세계에 구현할 대상 물리적으로 존재하거나 추상적으로 생각할 .. 2023. 4. 9.
이진탐색트리와 AVL 트리 이진탐색트리 이진 탐색 트리는 다음과 같은 속성이 있는 이진 트리 자료 구조이다. 각 노드에 값이 있다. 값들은 전순서가 있다. 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다. 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다. 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다. 즉, 이진 트리 구조로 되어있는데 자식의 왼쪽 값이 부모보다 작고 오른쪽 값이 부모보다 크면 이진탐색트리다. 이진탐색 트리를 순회 할 때는 중위 순회 방식(왼쪽-루트-오른쪽)을 쓴다. 이렇게 하면 이진탐색트리 내에 있는 모든 값들을 정렬 된 순서로 읽을 수 있다. 예시로, 다음의 이진탐색 트리를 중위 순회하면 1, 3, 5, 7, 8, 10으로 정렬된 .. 2023. 4. 3.
Heap과 Priority Queue Heap 우선순위 큐에 대해 알아보기 전에, 우선순위 큐를 위하여 만들어진 자료구조인 Heap에 대해 먼저 알아보자. heap의 특징은 다음과 같다. 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정렬 상태(느슨한 정렬 상태) 를 유지한다 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다.) 힙의 종류에는 최소 힙과 최대 힙이 있는데, 최대 힙의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이고, 최소 힙의 경우 부모 노드의 키 값이 자식 노드의 키 값보다 작거.. 2023. 4. 3.
탐색 알고리즘 탐색 알고리즘이란 지정된 데이터들 중에 원하는 값을 찾는 알고리즘이다. 선형 탐색 알고리즘 (Linear Search Algorithm) 맨 앞이나 맨 뒤부터 순서대로 하나하나 원하는 값을 찾아보고, 원하는 값을 찾았을 때 탐색을 종료하는 탐색 방법이다. 4를 찾을 때 맨 왼쪽에 있는 1부터 시작해서 하나씩 탐색한다. 원하는 값이 리스트의 맨 마지막 원소거나, 없는 경우 n번의 탐색 과정을 거치므로 시간 복잡도는 O(N)이다. int arr[9] = { 3,1,5,7,2,4,9,6,8 }; int arr_size = sizeof(arr) / sizeof(int); int linearSearch(int target) { // 찾은 값의 index 반환, 없으면 -1 반환 int result = -1; fo.. 2023. 4. 1.
Hashing과 Hash Table Hashing Hashing이란 임의의 길이의 값을 해시 함수(Hash function)을 사용하여 고정된 크기의 값으로 변환하는 작업을 말한다. 해시는 다양한 목적으로 사용될 수 있지만, 주로 다음과 같은 용도로 사용된다. 해시 테이블을 이용한 탐색 암호화 : 해시를 통해 변환된 데이터는 원본의 모습을 알아볼 수 없을 정도로 완전히 달라지므로, 이를 이용해 암호화라를 진행한다. SHA(Secure Hash Algorithm)알고리즘이 그 대표적인 예이다. 데이터 축약 : 해시는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있다. 이 특성을 이용하면 커다란 데이터를 '해시'하면 짧은 길이로 축약할 수 있다. 이렇게 축약된 데이터끼리 비교를 수행하면 커다란 원본 데이터들을 비교하는 .. 2023. 4. 1.
그래프와 탐색 그래프란 현실세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화하여 표현한 것을 말한다. 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)으로 이루어진다. G = (V, E) 그래프와 관련된 용어 정점, 노드 (Vertex, Node) : 데이터가 저장 된다. 간선 (Edge) 무향 간선 (Undirected Edge) : 방향이 존재하지 않는 간선, 양방향 유향 간선 (Directed Edge) : 방향이 존재하는 간선 인접 (Adjacent) : (정점 관점) 두 정점 A, B 사이에 간선이 존재한다면 A, B는 인접한다. 부속 (Incident) : (간선 관점) 두 정점 A, B 사이에 간선 e가 존재한다면 간선 e는 정점 A, B에 부속한다. 차수 (Degree) : 한 정.. 2023. 4. 1.

티스토리툴바