Daniel's blog

Heapify :Heapify is the process of creating a heap data structure from a binary tree represented using an array. : Heapify란 배열(Array)로 표현된 이진 트리(Binary tree)의 자료구조를 갖는 힙(Heap)을 생성하는 과정이다. 알고리즘 과제로 Heap을 Build하는 문제에 대해 알고리즘을 제시해야했고, 목표 시간복잡도(Time-Complexity)는 Linear time(O(n))이었다. Heap을 접할 때 기본적으로 함께 알게 되는 함수 중 하나가 Insert() 함수다. Insert() 함수의 시간복잡도는 Tree의 Height(높이)만큼 비교가 필요해 O(log n)이다. 이를 n개의 노드..

MST를 알아보기에 앞서 Spanning Tree에 대해 알아보자. Wikipedia에 따르면 Spanning Tree에 대한 정의는 아래와 같다. In the mathematical field of graph theory, a spanning tree T of an undirected graph G is a subgraph that is a tree which includes all of the vertices of G. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see spanning forests below). If all of..

한 블로그에 따르면 Higher order function에 대한 설명은 아래와 같다. A higher order function is a function that takes a function as an argument, or returns a function. Higher order function is in contrast to first order functions, which don't take a function as an argument or return a function as output. : 고차 함수는 인자로 함수를 가지거나 함수를 반환하는 함수이다. 고차 함수의 반대는 first order functions으로 함수를 인자로 가지거나 함수를 반환하지 않는다. Java의 관점에서 Hi..

GeeksforGeeks에 따르면 Lowest Common Ancestor(LCA)의 정의는 아래와 같다. : The lowest common ancestor is the lowest node in the tree that has both n1 and n2 as descendants, where n1 and n2 are the nodes for which we wish to find the LCA. Hence, the LCA of a binary tree with nodes n1 and n2 is the shared ancestor of n1 and n2 that is located farthest from the root. : LCA는 트리에서 n1과 n2를 자손(descendants)으로 가지는 가장..

1. 블랙 박스 테스트(외부) : 내부 구조를 참고하지 않고 AUT(Application Under Test)를 테스트 하는 것으로 응용 프로그램(어플리케이션)을 시각화하여 수행한다. 시스템의 내부 구조는 고려하지 않고 응용 프로그램의 기능을 기반으로 테스트 케이스를 도출해 진행한다. - 실행 파일 형태로 테스트 - 의도된 대로 동작하는지 테스트 - 기술적인 지식 불필요 - 화이트 박스 테스트보다 많은 비용 - 내부에 적용된 보안 기술 알 수 없음 - 종류: 동치 분할 검사(Equivalence Partitioning), 경계값 분석(Boundary Value Analysis), 원인-결과 그래프 검사(Cause Effect Graph), 비교 검사, 오류 예측 검사(Error Guessing), 의사 ..

테스트 주도 개발은 소프트웨어 개발 방법론 중 하나로, 설계한 프로그램의 코드 외에 테스트 코드를 따로 작성해 반복 테스트를 진행하고, 테스트가 실패하면 해당 코드를 수정하고, 이를 리팩토링 하는 방식으로 반복적으로 적용되는 개발 방법이다. 짧은 개발 사이클과 작은 유닛을 추가하는 방식으로 진행된다. 출처 1. https://marsner.com/blog/why-test-driven-development-tdd/ Why Test-Driven Development (TDD) | Marsner Technologies % marsner.com 2. https://ko.wikipedia.org/wiki/%ED%85%8C%EC%8A%A4%ED%8A%B8_%EC%A3%BC%EB%8F%84_%EA%B0%9C%EB%B..

공식 사이트에 따르면 JUnit에 대한 설명은 다음과 같다. : JUnit is a simple framework to write repeatable tests. It is an instance of the xUnit architecture for unit testing frameworks. : JUnit은 반복 테스트를 작성하는 간단한 프레임워크다. xUnit 아키텍처의 인스턴스 중 하나로 유닛 테스트(단위 테스트)용 프레임워크다. 위키백과에 따르면 JUnit은 자바 프로그래밍 언어용 유닛 테스트 프레임워크고, Test-driven development(TDD) 측면에서 중요하며 SUnit과 함께 시작된 XUnit이라는 유닛 테스트 프레임워크의 계열이다. JUnit은 현제 5번째 버전인 JUnit 5까..

Leetcode 문제를 풀기 위한 언어 선택 중 Python과 Python3 두 가지 옵션이 있어 알아보게 됐다. 기본적으로 모든 Python은 Open Source이고 대부분 GPL-compatible 하다. 실제로 안드로이드 개발 당시 설치했던 파이썬 3.x 버전에선 필요로했던 기능이 동작하지 않아 지우고 2.7 버전으로 재설치했던 일이 있었다. Python 2 1. Python 2.7은 2020년 1월 1일을 마지막으로 더는 지원하지 않음 2. 2000년 Python 2.0이 처음 배포되고 마지막 버전은 2.7로 2010년에 배포 Python3 1. Python 3.0은 2008년 처음 배포됐고, 가장 최신 버전은 현재 3.10.4 2. https://www.python.org/downloads/ ..

계산 가능성 이론(computability theory)에 따르면, 원시 재귀 함수는 대략적으로 반복문이 모두 "for"문인 컴퓨터 프로그램에 의해 계산되는 함수를 말한다. 원시 재귀 함수는 전역 함수(total function)이자 일반 재귀 함수들로 이뤄진 진부분집합(strict subset, proper subset)을 가진다. 원시 재귀 함수의 중요성은 수학에서 계산 가능한 대부분의 함수들이 원시 재귀라는 것에 있고, 더하기, 나누기, 팩토리얼, 지수 함수가 그 예다. 참고 - Primitivec recursive function(원시 재귀 함수): 반복 수를 알아 for loop 가능 - Recursive function(일반 재귀 함수): 반복 수를 몰라 for loop 불가 ex) 아커만 함..

계산 가능성 이론에 따르면 아커만 함수는 빌헬름 아커만(Wilhelm Ackermann)의 이름을 딴 함수로, 가장 간단하고 먼저 발견된 완전 계산 가능(total computable function) 함수이며 비원시 귀납 함수(not primitive recursive function)이다. 모든 원시 귀납 함수는 완전(total)하고 계산 가능하지만, 아커만 함수는 모든 완전 계산 가능 함수가 원시 재귀 함수는 아니라는 것을 설명한다. 아커만의 발표 이후, 3개의 음수가 아닌 정수를 인자로 갖는 아커만 함수에 대해 많은 사람들이 다양한 목적으로 변형했다. 흔한 예정 하나로는 두 개의 인자를 갖는 아커만 피터 함수(Ackermann-Peter function)이 있는데 음수가 아닌 두 정수 m과 n에 ..