Computer Science
-
Queue in SwiftComputer Science/DataStructure 2021. 2. 5. 14:45
- 선형 자료구조 - FIFO (선입선출) - 구현 - LinkedList - DoubleStack Swift에서는 Queue와 LinkedList를 기본 자료구조로 제공하지 않고 있는데요, array를 사용해 queue를 만들면 enqueue 작업이 O(n)이 걸려서 비효율적입니다. 특히 코딩테스트 문제를 풀다보면 queue가 필요한 상황이 많기 때문에 미리 알아두고 구현해둔다면 좋겠죠? 오늘은 간단하게 Queue 에 대해 알아보고 swift에서는 어떻게 구현할 수 있을지 알아보겠습니다. LinkedList를 사용한 구현과, stack 두 개를 사용한 doubleStack 구현을 알아볼텐데요, LinkedList는 제가 구현해서 그런지 doubleStack과 복잡도 차이가 꽤 나더라구요... 😢 코딩테..
-
TreeComputer Science/DataStructure 2021. 1. 14. 18:00
- 객체간의 계층적인 관계를 나타낸다 - 빠르고 효율적으로 탐색할 수 있다 - 데이터의 정렬된 형태를 보여준다 - 사이클이 없는 그래프 - 텍스트의 prefix 매칭을 빠르게 할 수 있다. ex) - 회사나 정부의 조직 구조 - 나라, 지방, 시•군별 등 계층적인 데이터 - 인덱스 오늘은 기본적이지만 아주 중요한 Tree에 대해 알아보겠습니다. Tree 자체보다도 여기서 파생된 트리들이 더 중요하지만 그래도 기본부터 정리해보려고 해요 :) 자료구조란 데이터들을 잘 관리하게 생겨났을텐데요, 트리는 왜, 언제 필요할까요? 트리는 계층적인 관계를 나타내기 위해 사용합니다. 계층 관계는 우리 일상 생활과 아주 많이 밀접해있습니다. 먼저 우리 가족의 관계도를 그려본다고 생각해봅시다. 부모님 형제 자매가 있고, 다..
-
Process 와 ThreadComputer Science/Operating System 2020. 8. 11. 18:03
Process 와 Thread를 초간단 정리해보겠습니다. Process 컴퓨터에서 연속적으로 실행되고 있는 컴퓨터 프로그램 실행중인 프로그램의 instance 로 운영체제에서 가장 기본적인 실행단위. 각 프로세스는 Code, Data, Stack, Heap의 구조로 된 독립된 메모리영역을 갖는다. 각 프로세스는 일정 생애주기를 갖는다. 하나의 작업을 여러 프로세스에서 병렬로 처리하는 걸 멀티프로세싱이라고 한다. 멀티 프로세싱 하나의 작업을 여러 프로세스에서 병렬로 처리하는 걸 의미합니다. CPU에서 여러 프로세스를 돌면서 처리합니다. 다음 프로세스로 넘어갈 때 동작중인 프로세스는 현재 상태(Context)를 보관하고, 대기하고 있던 다음 프로세스의 상태(Context)를 복구합니다. 이 과정을 Conte..
-
운영체제 OS (Operating System)Computer Science/Operating System 2020. 8. 11. 17:06
우리가 많이 듣고 사용하는 윈도우, 맥os, iOS, 안드로이드, 리눅스, MS-DOS 등이 바로 운영체제 입니다. 오늘은 운영체제가 뭔지 아주 간단하게 공부해보겠습니다. 운영체제 운영체제(Operating System)란 밑으로는 하드웨어 자원들(cpu, memory, disk, tty)을 관리하고 위로는 프로그램들을 지원(support) 해주는 역할을 합니다. 하드웨어 자원들을 잘 관리해서 프로그램들이 효율적으로 동작할 수 있도록 만들어주는 중간 관리자 입니다. 운영체제의 목적 운영체제가 하는 일을 이해했다면 자연스럽게 그 목적은 프로그램들이 효율적으로 동작하는 데 있습니다. 그렇다면 효율적이라는 건 어떤 걸까요? 크게 다음 4가지의 척도로 판단해볼 수 있습니다. 처리능력(Throughput): 일정..
-
StackComputer Science/DataStructure 2020. 3. 3. 14:54
- 선형 자료구조 - LIFO (후입선출) 선형 자료구조의 일종. Last In First Out (LIFO) 방식으로, 나중에 들어온(push) 원소가 먼저 나온다.(pop) 접시를 위로 쌓아놓은 형태를 떠올리면 쉽다. 따라서 스택의 앞에 원소를 넣는 것은 O(n)이고 스택의 뒤에 추가하는 것은 O(1)의 시간복잡도를 갖는다. 참고로 CPU는 function 이나 method의 return 주소를 스택에 넣는데, 재귀 함수 등과 같이 함수가 종료되기 전에 너무 많은 함수를 호출해 CPU의 스택이 부족해지면 "stack over flow"가 발생한다. Implement Swift는 사실상 내부적으로 Stack을 이미 지원하고 있다고 볼 수 있다. public struct Stack { fileprivat..
-
HeapComputer Science/DataStructure 2019. 12. 31. 20:32
Heap 이란? 힙은 루트에 가장 힙한 녀석을 두는 이진 트리이다. (응?) 루트에 항상 최대 또는 최소값을 두기 때문에 최대 최소값을 빠르게 얻을 수 있다. O(1) 힙은 완전 이진트리의 모습을 띄는데, 부모 노드가 자식 노드보다 크거나(최대힙) 작은지(최소힙) 만을 보장한다. 즉, 자식노드 끼리는 큰지 작은지를 비교할 수가 없다. 힙은 배열로 구현하면 공간, 시간 복잡도 측면에서 좋기 때문에 배열로 많이 구현한다. 배열로 구현했을 때 다음과 같이 인덱스를 구할 수 있다. parent: floor((i-1) / 2) left: 2i + 1 right: 2i + 2 인덱스를 1부터 시작하면 parent: i/2, left: 2i, right: 2i+1 로 구할 수도 있다. 잘 보면 오른쪽 노드 = 왼쪽노..
-
Array vs LinkedListComputer Science/DataStructure 2019. 12. 16. 15:53
둘다 선형 방식의 자료구조이다. 배열(Array): 인덱스를 가지고 있는 데이터의 모음. 리스트(List): 순서가 있는 데이터의 모음. 각 원소는 다음이 어떤 원소인지만 알고 있음. 배열은 인덱스를 가지고 있기 때문에 인덱스를 알고 있으면 원소에 직접 접근이 가능해 빠르게 조회할 수 있다.(O(1)) 대신 인덱스는 고정되어야 하고 만약 엘리먼트가 삭제되더라도 빈 공간으로 남겨둬야 한다. → 이는 메모리 낭비를 초래할 수 있고, 엘리먼트가 비었는지 확인하는 로직이 필요하다. 리스트는 인덱스가 없기 때문에 각각의 원소는 다음 원소만 알고 있기 때문에 순차적으로 접근해야 한다. (O(n)) 인덱스가 고정이 아니고 순서 정도의 의미만 지니기 때문에 추가, 삭제가 빠르다.(O(1)) → 하지만 추가 삭제를 위한..
-
JPG 와 PNGComputer Science 2019. 12. 16. 15:48
JPG와 PNG 방식의 차이는 한마디로 압축방식의 차이다. PNG는 비 손실 압축방식으로 몇 번을 저장하든 화질의 변화가 없지만 JPG는 손실 압축방식으로 압축할 때 마다 손실이 일어나 여러번 저장할수록 화질이 점점 떨어진다. JPEG 알고리즘은 쉽게 말해 사람의 눈에 거슬리지 않을 정도로 원본을 훼손해 압축 효과를 극대화 시키는 것이다. 좀 더 자세히 보면, DCT(discrete consine transform, 이산 코사인 변환)를 적용한 후 데이터를 줄이기 위해 Quantization(양자화)를 한다. 양자화는 자연스러운 색상을 단순화 시켜 색 수가 줄어들고 이때 데이터의 손실이 발생한다. 따라서 디지털 카메라로 찍은 사진일 경우 JPG로 압축하면 원본 이미지와 흡사한 퀄리티를 유지하면서 데이터의..