본문 바로가기

분류 전체보기227

11.24 시간복잡도, Greedy, 구현 시간복잡도를 표현하는 방식은 여러가지다. 그중 가장 많이 쓰이는 Big-O 기법에대해 살펴보겠다. ㅇ O(1) constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나진 않는다. ㅇ O(n) linear complexity. 입력값이 증가함에 따라 시간증가. 입력값 1증가 2초증가하면 O(2n) ㅇ O(log n) logarithmic complexity. BST처럼 경우의수를 절반씩 줄어든다. 입력값이 크면클수록 빠르다. O(n)보다 빠를수도 있다. ㅇ O(n^2) quadratic complexity. 입력값늘때마다 n^2만큼 시간이 늘어남. ㅇ O(2^n) exponential complexity. 가장 느린 시간복잡도를 가진다. 복리라고 생각하면 편함. ㅇ Greedy A.. 2022. 11. 25.
11.22 자료구조-Tree, 그래프, BinarySearchTree(BST), BFS/DFS ㅇ Tree 루트 라는 꼭지점 데이터에서 시작해 간선(edge)로 연결시킨다. 부모노드, 자식노드가 존재하고 자식이 없는 노드는 리프노드라고 한다. 깊이 : 루트 - 0, 그밑의 노드들 - 1, . . . 레벨 : 같은 깊이를 가진 노드들을 묶음 높이 - 리프노드를 기준으로 루트까지의 길이 서브트리 - 루트에서 뻗어 나오는 큰 트리의 내부에 트리구조를 갖춘 작은 트리 ㅇ 그래프 우리가 흔히 아는 수학적인 그런 그래프와는 거리가 멀다. 여러개의 점들이 복잡하게 연결되어 있는 관계를 표현한 자료구조다. 직접적 관계는 두 점 사이를 이어주는 선이 있고, 간접적인 관계는 몇개의 점과 선에 걸쳐 이어진다. 하나의 점은 정점(vertex), 하나의 선은 간선(edge)라고 함. ㅇ 그래프의 표현 방식 인접행렬 - .. 2022. 11. 25.
11.21 자료구조 - Stack, Queue 나도모르게 블로깅이 밀렸다. 정신차리고 다시 해야겠다. ㅇ 자료구조 데이터의 묶음을 저장하고 사용하는 방법을 정의한 것. 대부분의 자료구조는 문제해결에 특화되어있음. 알고리즘 문제에 자주 사용된는자료구조는 Stack, Queue, Tree, Graph ㅇ Stack 말 그대로 쌓이는 자료구조다. 정말 간단히 생각해 프링글스 과자 통이라고 생각하면 된다. 가장 먼저 들어간 자료가 가장 나중에 나오는 후입선출(LIFO - Last In First Out) 구조다. 스택구조에서 데이터를 넣는 것은 push, 꺼내는 것은 pop stack.push(1); stack.push(2); stack.push(3); - - - - - - - - - - - 1 2 3 stack.pop(); stack.pop(); stac.. 2022. 11. 25.
클린코드4 요며칠 배우는게 너무나 어려워 고전을 했다. 고전하며 클린코드도 안읽었다. 오늘은 금요일이니 밀린 클린코드를 읽으며 블로그를 쓴다. 이번엔 함수에 관한 내용을 봤다. 예시로 보여준 코드가 아직은 이해하기 너무 어려웠지만 겉으로보기에도 확실히 너무 장황한게 보였다. 저자는 함수를 만드는 첫규칙으로 작게만들라고 강조한다. if/else/while문의 블록에는 한줄만 쓰라고 한다. 아직 나에겐 정말 쉽지않다고 생각됐다. 저자는 함수는 한가지만 하라고 강조했다. 여러가지를 하지 말고 한가지만 하고 한가지만 잘해야 한다고 한다. 한가지만 하려면, 함수당 하나의 추상화수준을 가져야한다고 한다. 코드는 위에서 아래로 글을 읽듯이 작성되야 한다. 아래로 내려가면서 추상화도 한단계씩 낮아져야 한다. 저번처럼 이름에대해서.. 2022. 11. 25.

티스토리툴바