전체 글 (86) 썸네일형 리스트형 [Medium] 703. Kth Largest Element in a Stream (아마존 코딩 테스트 기출 문제) #문제 설명 Leetcode 703번문제는 int k 와 정수 array가 주어진다. 또한 이 array는 stream이기때문에 계속 정수들을 array에 추가 시킨다. 이 문제에서는 주어진 array에 여러개의 정수를 add하고, add가 끝난뒤 array에서 k번째로 큰 정수값을 반환시켜주면된다. #문제 풀이 class KthLargest { private PriorityQueue minHeap; private int k; public KthLargest(int k, int[] nums) { minHeap = new PriorityQueue(); this.k = k; for(int i = 0; i < nums.length;i++){ minHeap.add(nums[i]); if(minHeap.size(.. [Lecture 21] HTTP #개요 이번 포스트에서는 현대 웹 기반 애플리케이션뿐만 아니라 전 세계 웹의 기본 프로토콜인 Hypertext Transfer Protocol HTTP에 대해 알아보자. HTTP란 인터넷에서 하이퍼텍스트(hypertext) 문서를 교환하기 위하여 사용되는 통신규약이다. 하이퍼텍스트는 문서 중간중간에 특정 키워드를 두고 문자나 그림을 상호 유기적으로 결합하여 연결시킴으로써, 서로 다른 문서라 할지라도 하나의 문서인 것처럼 보이면서 참조하기 쉽도록 하는 방식을 의미한다. http는 1989년 팀 버너스 리(Tim Berners Lee)에 의하여 처음 설계되어 인터넷을 통한 월드 와이드 웹(World-Wide Web) 기반에서 전 세계적인 정보공유를 이루는데 큰 역할을 하였다. http의 첫번째 버전은 인터넷.. [Lecture 10] Heap / 힙 #Heap 이란 컴퓨터의 기억 장소에서 그 일부분이 프로그램들에 할당되었다가 회수되는 작용이 되풀이되는 영역. 스택 영역은 엄격하게 후입 선출(LIFO) 방식으로 운영되는 데 비해 히프는 프로그램들이 요구하는 블록의 크기나 요구/횟수 순서가 일정한 규칙이 없다는 점이 다르다. 대개 히프의 기억 장소는 지시자(pointer) 변수를 통해 동적으로 할당받고 돌려준다. 이는 연결 목록이나 나무, 그래프 등의 동적인 자료 구조를 만드는 데 꼭 필요한 것이다. 쉽게 말해 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 이진 트리이다. 짧게 힙(Heap)이라고 줄여서 부른다 영단어 힙(heap)은 '무엇인가를 차곡차곡 쌓아올린 더미'라는 뜻을 지니고 있다. 힙은 항상 완전 이진 트리의 형태를 띠.. [Lecture 17] Automatic Memory Management, Performance # Performence of Automatic Memory Management 실제 garbage collector들은 그들이 만드는 절충안에 매우 다양하다. 개발자들은 수십 년 동안 그것들을 설계하는 데 소비되어 왔다. 예를 들어, 자바 10은 4개의 다른 컬렉터와 함께 사용된다. ZGC는 2018년에 추가된 5번째 컬렉터이다 프로그램 처리량, 메모리 오버헤드, GC 처리량, 확장성 등 많은 특성이 다르다 garbage collector의 정책을 적절히 조정하고 성능에 미치는 영향을 이해하려면 작업 부하를 잘 이해해야 한다 #Modeling the Cost of GC Compacting Collectors: Garbage collector는 객체 그래프, 특히 다른 객체에 대한 포인터가 저장되는 위치.. [Lecture 20] Sorting Analysis / 정렬 알고리즘 분석 #개요 이번 포스트에서는 정렬 알고리즘들의 시간 복잡도 / time complexity를 분석해보자 #Insertion Sort 이제 정렬 알고리즘 하나인 삽입 정렬에 대해 알아보자. 삽입 정렬 알고리즘이란 한 번에 한 개씩 적당한 위치를 찾아 삽입·배치하는 알고리즘이다. 배열 내 데이터를 순회하며 정렬이 필요한 요소를 적당한 위치에 삽입하는 알고리즘이다. 즉 새로운 데이터를 이미 정렬된 데이터들 사이의 적절한 자리에 집어넣는 정렬방식이다. 삽입 정렬 자바 코드: public void insertionSort(T[] A) { int j; for (int p = 1; p 0 && temp.compareTo(A[j-1].. [Lecture 18] Sorting Algorithm / 정렬 알고리즘 #정렬 알고리즘 컴퓨터 분야에서 중요시되는 알고리즘 가운데 하나로 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 알고리즘이다. 실제 컴퓨터 분야에서 사용하는 데이터의 경우 숫자의 순서나 어휘의 순서대로 정렬한 다음 사용해야 되는 경우가 거의 항상 발생하는데 이걸 얼마나 효과적으로 해결할 수 있느냐가 정렬 알고리즘의 핵심이다. 정렬 알고리즘이란 데이터 요소의 집합을 일정한 순서로 배열하는 알고리즘이다. 쉽게 말해 정렬(sort)이란 데이터를 일정한 규칙에 따라 재배열하는 것을 의미한다. 각 요소 내의 1개 또는 복수의 1개 또는 복수의 키값을 바탕으로 하여 배열하는 경우도 있다. 정렬 알고리즘으로는 버블 정렬, 분산 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬 등이 있다. [네이버 지식백과 / 나.. [Lecture 16] Weighted Graph / 가중 그래프 #Weighted Graph 수학의 그래프 이론 분야에서, 그래프 번호매김(graph labeling)은 전통적을 정수로 표현되는 라벨을 그래프의 모서리나 꼭짓점, 또는 둘 다에다 붙이는 것이다. 공식으로 표현하면 그래프 G = (V, E)가 주어졌을 때, 꼭짓점 번호매김(vertex labeling)은 V에서 라벨의 집합으로 가는 함수이다. 이런 함수가 정의된 그래프는 꼭짓점-라벨 그래프(vertex-labeled graph)라고 부른다. 유사하게, 모서리 번호매김(edge labeling)은 E에서 라벨의 집합으로 가는 함수이다. 이 경우에, 그래프는 모서리-라벨 그래프(edge-labeled graph)라고 부른다. 모서리 라벨이 순서 집합(예, 실수)의 원소라면, 이 그래프는 가중 그래프(weig.. [Lecture 15] Graph Traversal / 그래프 운행법 #Graph Traversal 그래프 운행법, 그래프 트래버설 또는 그래프 순회란 그래프를 구성하는 모든 정점들을 체계적으로 방문하는 방법이다. 큐를 이용한 넓이 우선 탐색 방법과 스택을 이용한 깊이 우선 탐색 방법이 있다. 또 부모 노드를 먼저 검사하고 왼쪽 노드에서 오른쪽 노드의 순으로 방문하는 방법인 전위 운행법과 왼쪽 노드, 부모 노드, 오른쪽 노드의 순으로 방문하는 방법인 중위 운행법, 왼쪽 노드에서 오른쪽 노드의 순으로 방문한 후 부모 노드를 검사하는 방법인 후위 운행법이 있다. [네이버 지식백과] 그래프 운행법 [graph traversal] 일부 알고리즘은 그래프의 모든 정점을 정확히 한 번 방문해야 한다.정점이 방문되는 순서는 중요할 수 있으며 특정 알고리즘에 따라 달라질 수 있다. 이 .. 이전 1 2 3 4 5 ··· 11 다음
