하루에 하나씩 개발 공부

chaining node structure 이의 구성은 각각의 vertex를 설정한 후에 link각각의 vertex에 따른 link 또한 설정한다. bfs, dfs dfs는 preorder 형식으로 VLR 형태로 순환한다. bfs는 levelorder 형식으로 너비우선탐색을 진행한다. 스패닝 트리 minimum cost spanning tree은 세가지 algoritm에 사용된다. - Kurscal's algoritm 가중치가 작은 간선중에 사이클이 만들어지지 않을 때에만 연결한다. - Prim's algoritm 루트 노드 부터 시작해서 가중치가 작은 노드만을 연결해서 나간다. disjoint union 분리 집합 트리들을 합칠 때에 있어서 부모 노드 끼리 연결을 함으로서 합쳐주는 방식이다. aoe,a..

graph는 트리와 구성요소가 같지만, 사이클을 이루는 자료구조이다. 그래프에는 두가지 종류가 있는데, undirected graph와 directed graph가 있다. undirected graph는 방향성이 없는 그래프이고, directed graph는 방향성이 있는 그래프를 말한다. completed graph는 모든 node(vertex)들이 연결되어 있는 그래프를 뜻한다. 따라서 completed graph의 edge, 간선의 최대 개수는 undirected의 경우에는 방향이 없으므로 노드개수가 n이라고 하였을때에, n(n-1)/2로 나타낼수 있다. 방향이 있는 경우에는 최대 개수가 n(n-1)이다. 표현 같은 경우에는 아래와 같이 나타낸다. multi graph : 두 꼭짓점 사이에 여러 간..

complete binary tree : 마지막 level을 제외하고 모두 채워져 있고, 왼쪽 부터 차례로 채워진 경우를 뜻한다. full binary tree : 모든 노드가 0 아니면 2의 값을 가지도 있는 경우를 말한다. 따라서 leaf 노드를 제외한 모든 노드들이 자식을 두개씩 가지고 있다는 뜻이다. perfect binary tree : 마지막 level 까지 완벽하게 채워진 경우를 뜻한다. skewed binary tree : 한 쪽으로 치우진 노드를 뜻한다. Tree Traversal - inorder traversal : LVR - preorder traversal : VLR - postorder traversal : LRV 이를 재귀적으로 수행한다. 따라서 위와 같은 트리의 경우에는 po..

1. 검정 검정이란 가설을 세운 후에 표본에 기초하여 가설을 채택하거나 기각하는 방식이다. 검정에서는 귀무가설(원래의 가설) 그에 대립하는 대립 가설을 세운다. 귀무가설의 경우는 모평균이나 예상하는 값이 표본의 그 값과 같다고 가정한다. 이때 두가지 오류가 존재하게 되는데, 제 1종오류와 제 2종오류가 있다. 제1종 오류는 귀무가설이 참인데, 대립가설을 채택하는 경우이고 제 2종오류는 대립가설이 참인데, 귀무가설을 채택을 하는 오류이다. 이 둘을 동시에 관리할 수 는 없다 1종 오류를 줄이기 위해 유효 범위를 높이게 된다면, 2종오류의 가능성이 높아진다. 하지만, 반대의 경우는 1종오류의 확률이 높아진다. 이러한 표본에서의 검정은 두가지 케이스가 있다. 대표본에서의 검정과 소표본의 검정이 있다. 대표본에..

부동 소수점은 소수점이 떠서 돌아다닌다는 의미이다. 이를 나타내는 식이 존재하는데, 다음과 같다. fraction은 소수부를 뜻하고, exponent 는 지수부를 뜻한다. single인 경우에는 exponent에 8bit, fraction에 23bit, 부호표현에 1bit 가 사용된다. 총 32bit double인 경우에는 exponent에 11bit, fraction에 52bit, 부호표현에 1bit 가 사용된다. 총 64bit 이다. bias 는 보통 127을 사용하는데, 그 이유는 지수부가 음수를 표현하지 않게 하기 위함이다. 따라서 -127을 함으로서 음수를 표현한다. exponent 에는 예약 또한 걸려있는데, 아래와 같다. 십진수를 이진수로 나타내는 방법은 2로 나누면 된다. 그러면 십진수 소..

프로세서란 cpu의 한 부분으로 명령을 해석하는 부분이다. 우선 프로세서의 성능을 알아보자. 프로세서의 성능은 CPU Time으로 알아볼 수 있는데, CPU Time = CPU Clocks Cycles * Clock Cycle Time 이다. 이때에 Clock cycle Time 은 Clock rate의 역수와 같다. 따라서 CPU Time = CPU Clocks Cycles / Clock rate 와 같다. clock rate = Clock Cycles / seconds 또한 이때의 CPU Clock Cycles = Instruction Count * Cycles Count Per Instruction 과 같다. 이때 줄여서 IC * CPI 로 나타낸다. 따라서 CPI = Clock Cycles / I..

redis는 단어 자체로 본다면 remote dictionary server로 외부의 dictionary 서버이다. redis.io에서는 redis는 인메모리 데이터 저장소로 소개한다. 인메모리 데이터 저장소란 컴퓨터의 메인 메모리인 ram에 데이터를 올려서 사용하는 방법을 뜻한다. 이렇게 하는 이유는 당연히 속도가 빠르기 때문이다. 하지만, ram의 가격은 비싸기 때문에 일반적인 db로 사용할 수는 없다. 따라서 캐시데이터베이스의 역할로 사용한다. 이때 캐시란 자주 사용하는 값들을 미리 가지고 있다가 요청하였을때 빠르게 주는 것이다. 이러한 캐시에 사용되는 인메모리 데이터 저장소에는 대표적으로 두가지 서비스가 존재하는데, Redis와 Memcached 이다. 이들은 nosql로 key - value 패..

우테코 1주차로 7문제를 풀었다. java를 사용한지가 오래 되어서 공부를 다시하면서 문제를 풀었다. 5번까지는 자료형 변환과 간단한 로직을 사용하여 문제를 해결하였다. 하지만 6번, 7번은 쉽게 풀리지 않았는데, 6번의 경우는 사람들의 이름이 2자 이상 겹치는지에 대해 판별해야 했기 때문에 이름을 두글자씩 잘라서 모든 이름에 대해서 포함하는지를 판단하였다. 7번의 경우는 우선 set을 활용해서 사용자들의 이름을 1차적으로 뽑아낸 후에 각자의 친구들을 2차원 배열로 구분하였다. 그 후에 user 친구들과 얼마나 겹치는지를 각각의 친구들 배열과 비교하여 친구들마다 점수를 매겼다. 그 후 방문자에서 새로운 사람을 추가한 후에 전체 정렬을 하여 답을 나타내었다. 소감 우테코에서 추구하는 클린코드 라는 것이 무..

합병정렬이란 퀵정렬을 보완해서 나온 정렬 방법이라고 생각된다. 퀵 정렬은 기준값을 세운 후 왼쪽 오른쪽에 각각에 나누면서 정렬을 한다. 따라서 나누면서 이진트리 형태를 띄게 된다. 이에 최악의 경우에는 시간복잡도가 N^2이다. 이를 개선하여 처음부터 나누어진 수들을 합치면서 정렬을 한다. 나뉜상태에서 하기 때문에 NlogN으로 시간 복잡도가 일정하다. 코드로 표현하자면 위의 설명과 같이 시간 복잡도는 NlogN이다.

execute of r-format 위는 add instruction의 계산 과정을 나타낸 그림이다. 위의 진행 상황을 본다면 우선 instruction fetch, read register, alu operation, write data 순으로 실행된다. 그러면서 pc 의 값은 따로 병렬적으로 계산된다. 한편, 아래는 alu operation의 진리표이다. 위의 x는 전 포스트에서 언급하였듯이 don't care 이다. don't care 을 활용할 수 있는 이유는 alu op 가 11 이 없기 떄문이다. 이렇게 don't care 을 활용하면 시간이 빨라지는 이점이 있다. jump instruction의 경우는 위에 mux를 달아주면 된다. clock 의 cycle 은 combinationl logi..