CS 공부/CS Study 원본 검색 결과

해당 글 19건

CS - 20일차

int와 short 두 가지 모두 정수형 타입이다. 그렇다면 어떤 차이가 있는지 알아보자. char, short 형 : 이와 같은 정수 자료형 타입으로 표현하면 메모리 공간을 효율적으로 사용할수는 있으나 연산의 효율성은 떨어진다. size : 2byte(16bits) int 형 : int형보다 작은 크기의 데이터를 가지고 연산을 진행할 경우, 그 데이터를 일단 int형으로 바꿔서 연산을 진행한다. 따라서 산술 연산시, 자료형을 int형으로 선언해야 중간에 불필요한 변환 과정을 거치지 않게 되어 연산 효율이 좋다. size : 4byte(32bits) int (Primitive) vs Integer (Wrapper Class) 1. Primitive 자료형 - Wrapper 클래스 관계 int primit..
CS 공부/CS Study 원본 2021. 3. 5. 21:42

CS 19일차

Exception & Error Exception 프로그램이 핸들링 할 수 있는 경우. 처리가 가능. checked exception ( compile time ) 실행하기 이전 예측 가능. 파일 확인할 때 에러, SQL 관련. 이클립스, 인텔리제이 등 IDE가 컴파일 할 때 체크 해줌. unchecked exception ( runtime ) 실행해야 알 수 있음. 실행 시 객체 생성이 없는 경우 ( NullPointer ), Array 싸이즈가 안 맞는 에러, 잘못된 인덱스 접근 등. Error 런타임에서 실행 시 발생되며 전부 예측 불가능한 Unchecked Error 핸들링이 불가능해 수정 없이 회복, 처리가 불가능하다. 대표적으로 Out Of Memory, Stack Overflow 문제. Ex..
CS 공부/CS Study 원본 2021. 2. 26. 22:42

CS 18일차

async vs sync / blocking vs non-blocking mangocode.tistory.com/84 (17차 스터디에서 진행) KMP 알고리즘 (출처 - baeharam.github.io/posts/algorithm/kmp/ ) KMP 알고리즘은 어떤 문자열 HH와 SS가 주어졌고 HH가 SS보다 긴 경우에, HH 안에 SS가 포함되어 있는지를 탐색하는 알고리즘이다. 자, 생각을 해보자. 예를 들어 단순 브루트 포스로 SS를 탐색한다면 상당히 오랜 시간이 걸릴 수밖에 없다. 예를 들어, ABAABAA라는 문자열 HH에서 부분문자열 ABAC를 찾기 위해선 아래와 같이 찾아야 한다. 당연하게도 시간복잡도는 HH의 길이를 n, SS의 길이를 m이라고 했을 때 O(nm)O(nm)이 나오게 되기..
CS 공부/CS Study 원본 2021. 2. 22. 22:37

CS 17일차

Blocking & Non-Blocking I/O async : 이벤트 핸들러 (callback)에 의해 처리 (callback 함수가 호출되기까지 다른 작업 가능) sync : 이벤트를 자신이 직접 처리(확인의 주체가 유저 프로세스이며, 다 될때까지 기다리거나 스스로 확인) block : 완료까지 대기(리턴되기 전까지 멈춤) non-block : 미완료라도 즉시 리턴 간단히 까페에서 커피를 주문하는 것을 예로 들어보면, 1. 커피를 타달라는 요청이 왔다. 2-1. 이 때 커피가 있으면 타준다(블로킹/넌블로킹 모두) 2-2. 커피가 없는 경우 블로킹 : '잠깐만요'하고 사러 간다. / 넌블로킹 : 커피가 없다고 말하고 사러 간다. 3-1. 동기 : 커피가 타졌는지 안타졌는지 내가 확인한다. 3-2. 비동..
CS 공부/CS Study 원본 2021. 2. 19. 22:46

CS 16일차

세그먼트 트리(Segment Tree)란? 배열에 부분 합을 구할 때 사용하는 개념입니다. 이 때 문제는 배열의 값이 지속적으로 바뀔 수 있기 때문에 매 순간 배열의 부분 길이 만큼, 즉 O(N) 만큼의 시간이 걸리기 때문에 이를 트리로 구현하여 O(logN) 의 시간으로 해결하는 방법입니다. 배열을 세그먼트 트리로 세그먼트 트리 를 사용하기 위해서는 주어진 배열을 이진 트리 구조로 만들어야 합니다. 이 때 트리를 구현하는 알고리즘은 다음과 같습니다. 부모노드의 값은 양 쪽 자식 노드 값의 합 배열의 요소들은 리프 노드에 위치 위 알고리즘을 통해 N = 10 일 때의 세그먼트 트리를 그리면 다음과 같습니다. 이 때 기존 데이터의 배열의 크기를 통해서 트리 배열의 최대 크기를 알 수 있습니다. 기존 데이터..
CS 공부/CS Study 원본 2021. 2. 15. 22:45

CS 15일차

유니온 파인드(Union Find)란? 정의 유니온 파인드(Union Find): 서로소 집합(Disjoint Set) 그리고 병합 찾기 집합(Merge Find Set)이라고도 불리며 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미합니다. 예시 다음 아래와 같이 원소들이 있다고 가정을 했을 때 각각의 원소들이 어떤 원소들과 연결이 되어있는지 입력을 받는다고 가정하면(1-2, 2-5, 5-6, 5-8, 3-4 이런 방식으로) 아래와 같이 3개의 서로소 집합이 나올 수 있다. 구현 원리 배열을 이용해서 Tree 자료구조를 만들어 구현하며 위에 나와 있는 {1, 2, 5, 6, 8}, {3, 4}, {7}의 경우에는 아래처럼 표현 및 구현이 가능합니다. 즉, 최상단 노드인 Root노드를 집합을 구분..
CS 공부/CS Study 원본 2021. 2. 8. 22:47

CS 13일차

Minimum Spanning Tree 그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다. Kruskal Algorithm 초기화 작업으로 edge 없이 vertex 들만으로 그래프를 구성한다. 그리고 weight 가 제일 작은 edge 부터 검토한다. 그러기 위해선 Edge Set 을 non-decreasing 으로 sorting 해야 한다. 그리고 가장 작은 weight 에 해당하는 edge 를 추가하는데 추가할 때 그래프에 cycle 이 생기지 않는 경우에만 추가한다. spanning tree 가 완성되면 모든 ver..
CS 공부/CS Study 원본 2021. 2. 1. 22:32

CS 12일차

Red Black Tree RBT(Red-Black Tree)는 BST 를 기반으로하는 트리 형식의 자료구조이다. 결론부터 말하자면 Red-Black Tree 에 데이터를 저장하게되면 Search, Insert, Delete 에 O(log n)의 시간 복잡도가 소요된다. 동일한 노드의 개수일 때, depth 를 최소화하여 시간 복잡도를 줄이는 것이 핵심 아이디어이다. 동일한 노드의 개수일 때, depth 가 최소가 되는 경우는 tree 가 complete binary tree 인 경우이다. Red-Black Tree 의 정의 Red-Black Tree 는 다음의 성질들을 만족하는 BST 이다. 각 노드는 Red or Black이라는 색깔을 갖는다. Root node 의 색깔은 Black이다. 각 leaf..
CS 공부/CS Study 원본 2021. 1. 29. 22:42