Angievelopment

이진 검색 트리 정의 이진 탐색 + 연결 리스트 이진 탐색 탐색에 소요되는 시간 복잡도는 O(logN) 하지만 삽입, 삭제가 불가능. 연결 리스트 삽입, 삭제의 시간 복잡도: O(1) 탐색하는 시간 복잡도: O(N) 이 두 가지를 합하여 장점을 모두 얻기 위해 고안된 것이 이진 탐색 트리 즉, 효율적인 탐색 능력을 가지고 자료의 삽입, 삭제도 가능하게 만드는 것이다. 조건 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값보다 작아야 한다. 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다. 같은 키 값을 갖는 노드는 없다. 이진 트리의 중위 순회(inorder)로 정렬된 순서를 읽을 수 있다. 작동 원리 1. 검색 루트부터 검색을 진행한다. 이때 선택하는 현..

Tree Tree의 구성요소 Node(노드): 트리를 구성하고 있는 각각의 요소 Edge(간선): 트리에서 노드와 노드 사이를 연결하는 선 Root Node(루트 노드): 트리 구조에서 최상단에 위치한 노드. 부모가 없는 노드 Termanal Node(Leaf Node, 단말 노드): 하위에 더이상 다른 노드가 연결되어 있지 않은 노드. 자식이 없는 노드 Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드. 루트 노드도 포함. 레벨(level, 깊이(depth)): 루트에서 어떤 노드까지의 경로 길이(간선의 수) 트리의 높이(height): 트리의 최고 레벨 부모 노드: 자신과 연결된 상위 노드 자식 노드: 자신과 연결된 하위 노드 형제 노드: 같은 부모를 가지는 노드 크..

Stack 데이터가 입력되면 입력되는 순서대로 쌓고, 나중에 들어온 것부터 먼저 사용하는 자료구조 LIFO(Last in First Out)의 구조. 활용 프로그램을 수행할때 사용 main 프로그램 위에 실행되는 함수가 쌓여서 호출됨 시간복잡도 : O(n) 공간복잡도 : O(n) /* * @ TITLE Stack (배열로 구현한 스택) */ interface Stack{ boolean isEmpty(); boolean isFull(); void push(char item); char pop(); char peek(); void clear(); } public class ArrayStack implements Stack { private int top; private int stackSize; privat..

dynamic array 요소의 개수에 따라서 자동으로 크기를 늘였다 줄이는 배열 종류 c++ : vector java : ArrayList 장점 인덱스를 이용해서 접근, 검색하면 속도가 매우 빠름 : O(1) 맨 앞에 위치한 요소의 주소값 + offset 단점 새로운 값을 삽입하거나 삭제할 땐 임시적으로 배열을 새로 생성하므로 속도가 느림 : O(n) Linked List [head, [tail]] 의 구조를 가지고 있는 형태의 자료구조 head : 데이터 tail : 연결된 다른 linked list 장점 삽입과 삭제를 위해 데이터 복제 없이 단순히 삽입하거나 삭제하고 남은 요소들을 연결하면 되어서 삽입과 삭제가 빠르다 : O(1) 그러나 삽입, 삭제를 하기 위해 그 요소를 찾기 위해 O(n)이 필요..

Array vs Linked List 비교 array linked list 검색 random access 지원 index를 통해 직접적으로 접근 가능, O(1) Sequential Access 지원 처음부터 node를 순회, O(n) 저장 논리적 저장순서와 물리적 저장순서가 일치함 모두 흩어져서 저장됨 [head, [tail]]에서 tail에 연결된 node 정보 저장 삽입, 삭제 데이터를 중간에 삽입 or 맨 앞에 삽입하는 경우 : 이후 데이터를 shift 해야함 -> O(n) 맨 앞 or 맨 뒤에 삽입 -> O(1) 중간에 삽입 : 삽입할 위치를 검색하고 삽입 -> O(n) 메모리 할당 Stack에 할당함 compile time에 할당됨 : Static Memory Allocation Heap에 할당..

지난 몇 년 간 정말 노력했다고 생각했는데 기본도 부족하고 필요한 역량도 부족한데 시간만 흐른 사람이 되어있다고 생각해서 너무 속상했다 뭐 근데 어쩔 수 없지 그냥 사실을 인정하고 개선할 수 있는 방법을 찾는 수 밖에 없는 것 같다 그래서 뭐 공부할거냐면 1. DI 2. DDD + Unit Test 3. 리팩토링 2판 읽어보기 요즘 내일배움카드로 스프링을 공부해보고 있긴 하다. 스프링을 써보고 싶다기 보다는 스프링으로 제공되는 많은 좋은 아티클과 서적들을 이해하기 위해서이다. 나는 Node.js, Django를 이용한 개발이 더 즐겁고 재미를 느끼기 때문에... 위 세 가지는 아마 (특히 javascript로) 공부할 예정! Typescript도 틈틈히 공부하긴 하겠지만 아직 javascript도 턱없이..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net ✨ 문제 풀이 이분탐색은 항상 그렇듯이 무엇을 기준으로 잡고서 탐색할 것인지가 중요하다. 최소 M미터의 나무 토막을 가져갈 때 절단기 높이의 최댓값을 구해야하므로 절단기의 높이를 기준으로 잡고 탐색한다. 그렇다면 탐색할 첫 기준이 중요한데, 절단기가 모든 나무를 자르는 경우인 0을 start로, 아무것도 자르지 않는 최대 높이인 가장 큰 나무의 길이를 end..

AWS Academy Cloud Architecting Module 10 (Automating Your Architecture) Challenge Lab 잘 안 됐던 부분 메모 1. Challenge #3 - Task 4 Network 배포 자동화 하기 전에 update-network-stack 삭제 CafeNetworkPipeline에 연결된 CloudFormation에 이미 update-network-stack이라는 stack이 존재한다. 여기에 VPC, Subnet이 배포되어 있기 때문에, cafe-network.yaml의 템플릿을 업로드해서 CodePipeline에서 배포하면, 새로운 VPC와 Subnet을 배포하지 않는다. 네트워크 배포에는 당장 문제가 생기지 않는다. 그러나 그 다음 어플리케이..

쿼리를 통해 여러 데이터를 불러오고 serializer로 데이터를 직렬화했을 때.. 데이터베이스에 저장된 정적인 값을 그대로 가져오는 것 외에 request로 받은 쿼리들과 어떤 작업을 해서 새로운 동적인 데이터를 가져오고 싶을 때가 있다 가령 현재 위치의 위도, 경도와 데이터베이스에 저장된 장소의 위도, 경도 값을 계산해서 거리를 계산한다던가 등등 어떤 필드에 대해서 각각 데이터에 어떠한 작업을 해준 뒤 응답으로 보내줘야하는 경우가 있다. for문을 통해서 하나하나할 수도 있겠지만! Serializer에서 바로 처리해줄 수 있는 context가 있다. 아래는 request의 GET query로 현재 위치의 위도, 경도 값을 요청 받았을 때, 데이터베이스에 저장되어 있는 장소들과의 거리를 구하고 그 거리..

Node.js(Express)를 이용해 지도를 포함하는 프로젝트를 진행 중이었고, 두 지점 사이의 중앙의 위도, 경도를 구하는 작업이 필요했다. 두 좌표점의 중앙값을 구하는 방법이 뭐 사인값 구하고 코사인값 구하고.. 이런 공식을 사용하면 되긴 했지만 잘 만들어진 라이브러리가 없나 찾아보다 Turf라는 라이브러리를 찾게 되었다. http://turfjs.org/ Turf.js | Advanced Geospatial Analysis Modular Turf is a collection of small modules, you only need to take what you want to use turfjs.org geospatial한 작업을 할 수 있도록 해주는 Node.js 라이브러리다. 위 공식사이트에 들..