티스토리

코딩공학

검색하기

블로그 홈

코딩공학

churnobyl.com/m

화학공학과 개발자

구독자: 18

방명록 방문하기

반응형

주요 글 목록

[Data Structure] NonLinear - (3) Graph - 기본 개념 그래프(Graph) 그래프는 어떤 개념들 간의 연결관계를 표현하기 위해 사용하는 자료구조다. '개념들 간의 연결관계'라는 말이 모호하기 때문에 그 관계의 예를 몇 가지 들면, 사람과 사람 간의 관계, 도시와 도시와 연결된 도로들의 관계, 네트워크에서 A컴퓨터, B컴퓨터, C컴퓨터, ... 들 간의 관계 등이다. 즉, 그래프 자료구조에서 주로 포커싱되는 대상은 관계이며, 현실세계나 추상적인 개념의 문제들을 그래프 구조로 맵핑시키고 난 뒤에는 그 관계들을 이용해 다양한 알고리즘을 적용해 문제들을 해결할 수 있다. 1) 기본 개념 자료구조로서 그래프는, 위의 설명에서 개념에 대응하는 정점(Vertex; 노드(Node) - 컴퓨터 과학에서는 주로 노드를 씀)과 관계에 대응되는 간선(Edge)으로 이루어진다. 개.. 공감수 0 댓글수 0 2024. 4. 3.
[OOP] 객체 지향 설계의 다섯가지 원칙: SOLID SOLID란? 객체 지향 프로그래밍에서 항상 등장하는 SOLID원칙은 개발 및 보수를 하는 데 있어, 소스코드를 읽기 쉽고 확장이 원활하도록 만드는 다섯가지 원칙이다. SOLID는 각 원칙의 첫번째 글자를 합친 것으로 각각 Single Responsivility Principle, Open/Closed Principle, Liskov Substitution Principle, Interface Segregation Principle, Dependency Inversion Principle이다. SOLID 원칙을 사용하지 않더라도 객체 지향적인 프로그래밍은 가능하지만, 원칙을 지키면 동료들과의 협업이 원활해지며, 추후 소프트웨어를 확장할 때도 실수를 미연에 방지할 수 있다. 단일 책임 원칙(Single R.. 공감수 0 댓글수 0 2023. 10. 2.
[Data Structure] NonLinear - (2) Heap 힙(Heap) 힙 자료구조는 일종의 트리다. 힙은 형태 속성과 힙 속성을 만족해야 하는데, 즉 힙은 완전이진트리 구조여야 하며 힙 속성을 가져야 한다. 완전이진트리는 이전 글에서 작성한 것처럼 마지막 레벨을 제외한 모든 노드가 다 채워져 있는 이진 트리이며, 마지막 레벨은 왼쪽에서 오른쪽으로 채워져 있는 트리이다. 힙 속성은 각 노드의 데이터들은 각각의 자식 노드의 데이터보다 크거나 같은 속성을 말한다. 힙 구현하기 힙 자료구조 또한 완전이진트리 형태를 가지고 있으므로 동적 배열로 나타낼 수 있다. 즉, 파이썬에서는 리스트로 힙 자료구조를 표현할 수 있다. 아래는 최대힙을 구현한 코드이다. 간단하게 heapify, heappop, heappush함수를 구현했다. def _swap(arr, index_1,.. 공감수 0 댓글수 0 2023. 10. 2.
[Data Structure] 분리 집합 (Disjoint Set) 분리 집합 (Disjoint Set) 분리 집합은 서로소 집합이라고도 한다. 전체 집합 U에 대해 U의 분리 집합 A, B는 다음 조건을 만족한다. A, B는 U의 부분집합이다 A, B는 서로 공통 원소를 가지지 않는다 A, B의 합집합이 곧 전체집합 U이다. 즉, 전체 집합 U를 겹치는 부분이 발생하지 않도록 모든 원소를 분리시킨 집합을 분리 집합이라고 한다. 분리 집합은 일반적으로 두 원소가 같은 집합에 속하는지 빠르게 여부를 확인하거나, 두 집합을 합치는 등의 연산을 할 때 사용된다. 예를 들면 SNS에서 A라는 사람과 B라는 사람이 친구 관계인지 여부를 확인하거나, 친구를 맺었다면 두 집합을 합치는 연산을 할 수 있다. 분리 집합은 대표적으로 트리 자료 구조와 Union-Find 알고리즘으로 구현.. 공감수 0 댓글수 0 2023. 9. 21.
[Data Structure] NonLinear - (1) Binary Tree 일반 트리(General Tree) 일반적인 트리는 노드들의 집합으로, 하나의 루트 노드와 서로 겹치지 않는 여러 개의 부분 집합으로 이루어진 나머지 노드들로 구성되어 있다. 트리에서는 노드들 간에 상하관계인 부모-자식 관계가 만들어진다. 즉 부모와 자식 간의 레퍼런스가 있어 서로의 노드를 식별할 수 있다. 일반 트리는 자식 노드 수의 제한이 없기 때문에 무한정 늘어날 수 있는 특징이 있으며, 이로 인해 노드의 수를 파악하기 어려우므로 알고리즘을 적절하게 사용하기 어렵다. 따라서 주로 일반 트리를 이진 트리로 변환해 사용한다. class Node: def __init__(self, data) -> None: self.data = data self.children = [] root = Node(1) nod.. 공감수 0 댓글수 0 2023. 9. 19.
[Data Structure] Hash Table 해시 테이블(Hash Table) 해시 테이블은 key-value형태로 데이터를 저장하는 자료구조로, 일반적인 경우 O(1)의 시간복잡도로 값을 탐색할 수 있다. 1. Direct Access Table 우리가 저장할 key-value 쌍들이 있을 때 key값 중 가장 큰 숫자만큼의 배열을 생성한 뒤 해당 인덱스에 value를 저장하면, value에 접근하고 싶을 때 key를 통해 바로 접근할 수 있으므로 O(n)의 시간복잡도를 가진다. 이를 Direct Access Table이라고 한다. data = [(57, "고영희"), (208, "강아지"), (900, "고릴라")] max_index = 0 for key, value in data: if key > max_index: max_index = ke.. 공감수 0 댓글수 0 2023. 9. 19.
[Data Structure] Linear - (6) Queue 큐(Queue) 선입선출(First-In First-Out, FIFO)특징을 가진 자료구조다. 즉, 가장 나중에 들어온 자료가 가장 먼저 나가도록 되어 있다. 커스텀 큐 구현 싱글리 링크드 리스트로 큐를 구현해보자. 스택과 차이점은 한쪽 끝에서 연산이 이루어 지는 게 아니라 양쪽에서 각각 삽입과 인출이 일어난다는 것이다. 따라서 레퍼런스를 front와 rear로 두고 rear측에 새로운 노드가 삽입되고, front측에서 노드가 나가는 형태로 구현을 해야 한다. from typing import Iterable, Optional class Node: """싱글리 링크드 리스트 노드""" def __init__(self, data) -> None: self.data = data self.next = None.. 공감수 0 댓글수 0 2023. 9. 13.
[Data Structure] Linear - (5) Stack 스택(Stack) 후입선출(Last-in First-Out, LIFO)특징을 가진 자료구조다. 즉, 가장 최근에 들어온 자료가 가장 먼저 나가도록 되어 있다. 커스텀 스택구현 파이썬으로 스택을 구현하기 위해선 우선 두 가지 고려할 점이 있다. List? 일반적인 경우 그냥 파이썬 리스트로 스택을 사용해도 된다. 하지만 값이 계속해서 삽입되는 경우 파이썬 리스트는 동적 배열이므로 공간을 자동적으로 확장하면서 O(n)의 시간이 걸릴 때가 가끔 있다. 참고 공간이 작을 땐 문제가 안되겠지만 무지막지하게 큰 경우 시간이 오래 걸릴 수도 있다. Singly Linked List? 어차피 후입선출, 즉 맨끝에서만 자료가 삽입되고 나갈 수 있도록 구현하면 된다 각 자료들이 레퍼런스로만 연결되어 있기 때문에 공간의 확.. 공감수 0 댓글수 0 2023. 9. 13.
[Data Structure] Linear - (4) Deque 데크(Deque) 큐가 양쪽으로 연결된 형태. 따라서 양쪽에서 삽입과 삭제가 가능하다. 이미 파이썬에는 collections모듈에 deque가 구현되어 있다. c/c++로 구현되어 있으며 양쪽에서 삽입과 삭제가 가능해야 하므로 더블리 링크드 리스트로 만들어져 있다. 이로 인해 양쪽에서 삽입과 삭제가 O(1)의 시간이 걸리므로 코딩테스트 파이썬에서 스택이나 큐를 이용할 때 이 데크를 사용하기도 한다. 커스텀 데크 구현 파이썬으로 데크를 구현해 보았다. from typing import Iterable, Optional class Node: """더블리 링크드 리스트의 노드 클래스""" def __init__(self, data) -> None: self.data = data self.prev = None .. 공감수 0 댓글수 0 2023. 9. 12.
[Data Structure] Linear - (3) Linked List - Circular Linked List 원형 링크드 리스트 (Circular Linked List) 싱글리 링크드 리스트에서 마지막 노드가 다시 첫 노드와 연결되어 있는 자료구조다. 따라서 마지막 노드와 첫번째 노드를 O(1) 시간에 방문할 수 있다는 장점과 리스트가 비어있을 때를 제외하고 모든 노드의 레퍼런스가 None을 가지지 않기 때문에 None 조건에서 조금 자유로울 수 있다는 장점을 가지고 있다. 하지만 싱글리 링크드 리스트로 구현했다면 앞 노드를 방문하기는 쉽지 않다는 단점이 있다. 더블리 링크드 리스트로 구현하면 해결된다. 또한 무한 반복의 우려가 있다. class Node: def __init__(self, data) -> None: self.data = data self.next = None class CircularLinke.. 공감수 0 댓글수 0 2023. 9. 11.
[Data Structure] Linear - (2) Linked List - Doubly Linked List 더블리 링크드 리스트 (Doubly Linked List) 노드들이 다음 노드 뿐만 아니라 이전 노드에 대한 레퍼런스까지 가진 링크드 리스트를 더블리 링크드 리스트라고 한다. 앞과 뒤의 노드에 대한 레퍼런스를 가지고 있기 때문에 양 방향으로 탐색할 수 있는 특징이 있다. 노드(Node) class Node: """더블리 링크드 리스트 노드""" def __init__(self, data) -> None: self.data = data self.next = None # 다음 노드에 대한 레퍼런스 self.prev = None # 이전 노드에 대한 레퍼런스 def __str__(self) -> str: return str(self.data) # 노드 인스턴스 node1 = Node(3) node2 = Nod.. 공감수 0 댓글수 0 2023. 9. 11.
[Data Structure] Linear - (2) Linked List - Singly Linked List 링크드 리스트는 파이썬의 리스트처럼 선형 자료 구조로서, 데이터를 순서대로 저장할 수 있고 계속해서 요소를 추가할 수 있다. 이는 데이터와 다음 노드에 대한 레퍼런스를 가진 노드를 사용해 구현하는데, 노드들은 메모리 공간 여기저기 흩어진 상태로 저장되지만 각 노드에는 다음 노드나 이전 노드에 대한 레퍼런스를 가지고 있어서 선형적으로 다음 노드를 탐색할 수 있는 특징이 있다. 싱글리 링크드 리스트 (Singly Linked List) 노드들이 다음 노드에 대한 레퍼런스만을 가진 링크드 리스트를 싱글리 링크드 리스트라고 한다. 다음 노드에 대한 레퍼런스를 가지고 있기 때문에 한 방향으로 탐색할 수 있는 특징이 있다. 노드(Node) class Node: """노드 클래스""" def __init__(self.. 공감수 0 댓글수 0 2023. 8. 16.
[Data Structure] Linear - (1) Array 파이썬 리스트는 c의 배열을 이용해 만들어졌다. 두 자료구조의 큰 차이점은 정적 배열(Static Array)이냐 동적 배열(Dynamic Array)이냐다. c의 배열은 정적배열로서, 처음에 메모리에 배열의 크기를 정해놓고 시작한다. 즉, 크기가 고정되어 있다. 반대로 파이썬의 리스트는 동적배열로, append()메소드를 이용해 데이터를 추가할 때마다 배열의 크기가 가변적으로 늘어날 수 있고 반대로 del 예약어 등으로 크기가 자동적으로 줄어들 수도 있다. 01. 정적 배열 vs 동적 배열 (Static Array versus Dynamic Array) 위에 언급한 것처럼 c의 배열은 정적 배열이고, c의 배열을 이용해 만든 파이썬의 리스트는 동적 배열이다. 정적 배열 우선 c의 배열은 int newA.. 공감수 0 댓글수 0 2023. 8. 16.
[Overview] 03. Operating Systems - (2) Kernel and Virtual Machine 01. 커널 (Kernel) 02. 가상 머신 (Virtual Machine) 운영체제(Operating System)가 제공하는 서비스에는 크게 커널(Kernel)과 사용자 인터페이스(User Interface; UI)가 있다. 그 중에서도 특히 커널은 운영체제의 핵심 서비스를 담당하며, 사용자 인터페이스는 윈도우의 바탕화면 같이 사용자가 컴퓨터와 상호작용할 수 있는 통로다. 커널에 대한 설명은 잠시 미뤄두고, 사용자 인터페이스의 종류는 그래픽 유저 인터페이스(Graphic User Interface; GUI)와 커맨드 라인 인터페이스(Command Line Interface; CLI)가 있다. 전자는 앞서 말한 윈도우의 바탕화면처럼 그래픽을 기반으로 컴퓨터와 작용할 수 있는 인터페이스이며, 후자는 명.. 공감수 0 댓글수 0 2023. 8. 2.
[Overview] 03. Operating Systems - (1) The History of Operating Systems 01. 운영체제의 발전 (The History of Operating Systems) 운영체제(Operating System)는 컴퓨터의 전반적인 운영을 제어하는 소프트웨어다. CPU, 메모리, 보조기억장치, 입출력장치와 같은 시스템 자원(resource)를 실행한 프로그램에 적절히 할당하고 제어하는 중요한 역할을 한다. 01. 운영체제의 발전 (The History of Operating Systems) 운영체제는 아주 단순한 프로그램으로 시작했다. 운영체제는 20세기 중반 큰 방만한 초기 컴퓨터를 조작할 때 작업을 단순화시키기 위해 만들어졌다. 당시 컴퓨터는 하나의 프로그램을 실행시키기 위해 천공 카드나 테이프로 컴퓨터에 명령을 입력해야 하는 등 준비 기간이 길었다. 또한 한 가지 작업이 진행중인 동.. 공감수 0 댓글수 0 2023. 7. 31.
[Overview] 02. Data Manipulation - (2) Program Execution 01. 프로그램의 실행 (Program Execution) 1. 프로그램 로드 2. 인출(Fetch) 3. 해석(Decode) 4. 실행(Execute) CPU의 전체적인 실행과정을 살펴보기 위해서는 레지스터 중 특별한 용도가 지정되어 있는 명령 레지스터(Instruction Register)와 프로그램 카운터(Program Counter)를 살펴봐야 한다. 명령 레지스터는 실행할 명령을 차례대로 저장하는 레지스터이며, 프로그램 카운터는 다음에 실행할 명령의 주소를 가지고 있으며 현재 프로그램이 어디까지 실행됐는지 추적하는 수단으로 사용된다. 01. 프로그램의 실행 (Program Execution) 프로그램의 실행, 즉 CPU의 작업은 기계 주기(machine cycle)이라는 3단계 과정을 반복함으로.. 공감수 0 댓글수 0 2023. 7. 21.
[Overview] 02. Data Manipulation - (1) Computer Architecture and Machine Language 01. CPU 기초 (CPU Basics) 02. 기계어 (Machine Language) RISC (Reduced Instruction Set Computer) VS. CISC (Complex Instruction Set Computer) 명령의 종류 (Type of Instructions) 1장에서는 주저장장치인 메모리에 데이터를 어떻게 저장하는지에 대해 공부했다면 2장에서는 저장된 데이터를 컴퓨터가 어떻게 조작하는지에 대해서 공부할 것이다. 데이터 조작을 제어하는 컴퓨터 안의 회로는 중앙처리장치(Central Processing Unit, CPU) 혹은 프로세서(Processor)라고 불린다. 초기의 ENIAC과 같은 컴퓨터에서 CPU는 선반 여러 개에 나누어진 큰 장치였으나 현대로 오면서 CPU의.. 공감수 0 댓글수 0 2023. 7. 17.
[Overview] 01. Data Storage - (4) Data Compression 01. 일반적인 데이터 압축 기법 (Generic Data Compression Techniques) RLE(Run Length Encoding) 빈도 종속 인코딩(Frequency-dependent Encoding) 차등 인코딩(Differential Encoding) 사전 기반 인코딩(Dictionary Encoding) LZW 압축 알고리즘(Lempel-Ziv-Welsh Compression Algorithm) 데이터의 저장이나 전송을 위해 원래 정보를 유지하면서 데이터의 크기를 줄이는 것이 필수적이다. 각 분야에 맞게 고안된 압축 기법들이 있다. 01. 일반적인 데이터 압축 기법 (Generic Data Compression Techniques) 데이터 압축 방법은 무손실(lossless) 압축 .. 공감수 0 댓글수 0 2023. 7. 14.
[Overview] 01. Data Storage - (3) The Binary System 01. 2의 보수 ( Two's Complement ) 02. 소수의 표현 ( Fractions in Binary ) 0과 1로 표현되는 2진법 체계는 컴퓨터에서 보편적으로 사용된다. 2진법의 표기, 덧셈 같은 기초적인 내용은 건너 뛰도록 한다. 01. 2의 보수(Two's Complement) 2의 보수는 컴퓨터가 음수를 저장하기 위해 사용하는 정수 표현 체계 중에 하나이다. 4개의 bit로 구성된 머신이 있다고 하자. 이 머신은 2^4개의 경우의 수를 나타낼 수 있으므로 0 ~ 15 범위의 수를 저장할 수 있다. 하지만 음수를 표현해야 한다면 어떨까? 이를 위해서 범위의 절반을 음수에 할당한다. 그렇게 되면 4bit 머신의 경우 -8 ~ 7까지의 수를 저장할 수 있다. 또한 최상위 비트는 부호를 나타.. 공감수 0 댓글수 0 2023. 7. 11.
[Overview] 01. Data Storage - (2) Main Memory 컴퓨터는 데이터를 저장하기 위해 수많은 비트를 저장할 수 있는 회로들을 가지고 있다. 이 회로 안에 비트를 저장할 수 있고 이 비트 저장소를 컴퓨터의 주기억장치(Main Memory)라고 한다. 01. 메모리의 구성(Memory Organization) 주기억장치는 8bit로 이루어진 셀(cell)이라는 기초 단위들로 구성된다. 8bit로 된 열은 바이트(byte)라고 부르며, 메모리의 한 셀은 보통 1byte의 용량을 갖는다. 가전제품에 내장된 컴퓨터의 메모리는 수백 개의 셀을 갖지만, PC나 스마트폰의 경우 메모리 안에 수십억 개의 셀을 가질 수도 있다.(1billions cell = 약 1GB) 우리는 메모리 셀 안의 비트들이 한 줄로 배열되어 있다고 생각할 수 있는데, 이때 개념적으로 비트의 가장.. 공감수 0 댓글수 0 2023. 7. 11.
[Overview] 01. Data Storage - (1) Bit 그리고 Bit의 저장 어떤 컴퓨터 관련 수업이든 처음은 bit의 이해부터 시작한다. bit(binary digit)는 컴퓨터 안에서 정보를 나타내기 위한 최소 구성 단위로, 0과 1로 이루어져 있다. 여기까지만 들었을 때 '0, 1로 이루어진 숫자구나'라고 생각하기 쉽지만 사실 전류가 끊겼다 이어졌다 하는 전기적인 신호를 우리가 알아보기 쉽게 0과 1로 나타낸 것 뿐이다. 그래서 bit를 0, 1로 나타낸 것과 마찬가지로 False, True로 나타낼 수도 있다. 아무튼 컴퓨터는 비트의 패턴(Patterns of bits)들을 이용해서 정보를 표현한다. 이 비트의 패턴, 즉 정보는 알파벳과 같은 문자를 나타낼 수도 있고 이미지나 소리를 나타낼 수도 있다. 01. 부울 연산(Boolean Operations) 논리(logic).. 공감수 0 댓글수 0 2023. 7. 9.
[알고리즘] 02. 에라토스테네스의 체 소수를 판별하는데 자주 쓰이는 에라토스테네스의 체를 정리해보자. 벨로그에 정리했었지만 다시 한번 정리해보려고 한다. 소수(Prime number)란? 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수를 소수라고 정의한다. 소수를 작은 순서대로 나열하면 2, 3, 5, 7, 11, 13, 17, 19, 23...이며 코딩테스트를 준비한다면 바로바로 생각할 수 있게 2, 3, 5, 7까진 외워두는 것이 좋다. 소인수분해(소수의 곱) 문제를 풀 때도 소수는 중요한 부분을 차지한다. 반대로 소수가 아닌 수는 합성수라고 한다. 에라토스테네스의 체(Sieve of Eratosthenes) 에라토스테네스의 체는 고대 그리스의 수학자인 에라토스테네스가 발견한 소수를 구하는 방법으로 2의 배수, 3의 배수 등을.. 공감수 4 댓글수 4 2023. 5. 19.
[알고리즘] 01. 정렬 알고리즘(Sorting Algorithm) velog에 정렬 알고리즘을 정리했지만 다시 조금씩 까먹는 것 같아 다시 한번 정리하려고 한다 컴퓨터 과학 분야에서 정렬 알고리즘은 어떤 자료의 요소를 순서대로 배치하는 방법에 관한 것이다. 검색이나 병합 알고리즘을 사용할 때 입력된 데이터가 효율적으로 정렬되어 있는 것이 중요한데, 이 때 정렬의 효율성에 알고리즘이 고려된다 정렬 알고리즘의 아웃풋은 아래의 두가지 조건을 충족해야 해야 한다 1. 아웃풋은 단조(monotonic)로워야 한다 2. 아웃풋은 인풋의 순열(permutations)이어야 한다 즉, 정렬 알고리즘을 사용해 정렬이 끝난 뒤에 결과물의 각 요소는 (1) 이전 요소보다 작거나 크지 않아야 하며(한가지 흐름을 유지한다는 뜻) (2) 인풋의 모든 요소를 유지해야 한다 위와 같이 다양한 정렬.. 공감수 9 댓글수 2 2023. 3. 29.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.