본문 바로가기

부트캠프/백28

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.
11.18 JSON(미완성) ㅇ JSON JavaScript Object Notation의 약자. 데이터 교환을 위해 만들어진 객체 형태의 포맷이다. 자바에서 자바스크립트간, 파이썬에서 자바간, 다양하게 데이터를 교환할 수 있게 해준다. 저번에 읽은 책에서 나와서 대충 개념은 알았지만, 써보는 것은 처음이었다. Map message = new HashMap(){{ put("a","b"); put("c","d"); put("e","f"); }}; 이런 해시맵의 데이터를 어떻게 전송할까? 전송조건은 수신자 발신자는 같은 프로그램을 사용하거나, 문자열처럼 범용성있게 읽기 가능해야한다는 것이다. ObjectMapper mapper = new ObjectMapper(); String json = mapper.writeValueAsString.. 2022. 11. 19.

티스토리툴바