개발자의 기록습관

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조5-2. Red-Black Tree 02 - INSERT, FIXUPINSERT보통의 BST에서처럼 노드를 INSERT한다.새로운 노드 z를 red노드로 한다.RB-INSERT-FIXUP을 호출한다.1 : 또다른 포인터 y를 사용해서 y가 x의 한칸 뒤를 쫓아 내려오록 해야 새로운 노드를 insert할 자리를 관리할 수 있다. 레드블랙트리에서 특수하게 NIL 노드를 사용하지만, 실제로 구현할때는 null이 된다.3 - 7 : 새로운 노드 z가 들어갈 자리를 찾고,8 : z의 parent를 y로 설정해준다.9 - 10 : 예외적인 경우 y가 nu..

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조5-1. Red-Black Tree 01 - 개요앞서 배운 BST의 search, insert, delete 세 가지 연산모두 O(h)의 시간복잡도를 가진다. (h는 트리의 높이)여기서 문제는, 트리의 높이 h가 최악의 경우 n이 될 수 있다. n은 노드의 총 수.그러나, 이것은 실제 최악의 경우에 해당한다. BST에 데이터들이 random하게 구성된다고 가정했을때, 평균 트리의 높이는 O(logn)이 된다.그럼에도 불구하고, 최악의 경우 O(n)이 되는 경우는 좋은 알고리즘은 아니다. 그리고, 현실에서 이미 정렬된 데이터가 BST에 inser..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크4-2. Binary Search TreeDynamic Set집합이다. 여러개의 데이터의 집합인데, 그것들의 내용이 고정되지 않고, 생성과 삭제를 반복하면서 유동적인 집합이다. 아래와 같은 특징을 가진다. Dynamic Set, Dictionary 또는 Search Structure라고 불린다.여러 개의 키(key)를 저장다음과 같은 연산들을 지원하는 자료구조INSERT - 새로운 키의 삽입SEARCH - 키 탐색DELETE - 키의 삭제예: 심볼 테이블일반적으로 구현할 때 배열 or 연결리스트를 사용한다.각 동작에 있어서 다음과 같은 ..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크4-1. 트리와 이진트리트리(Tree)계층적인 구조를 표현하기 위해 사용하는 자료구조조직도디렉토리와 서브디렉토리 구조가계도용어루트(Root)트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성된다.맨 위의 노드를 루트라고 한다.부모-자식(parent-child) 관계각 노드들의 상하 관계를 부모-자식(parent-child)관계로 나타낸다.형제 관계(sibling)루트노드를 제외한 트리의 모든 노드들은 유일한 부모노드를 가진다.부모가 동일한 노드들을 형제 관계라고 부른다.리프(leaf) 노드자식이 없는 노드들을 leaf노..

알고리즘을 위한 자바 IOcodeplus - 프로그래밍 대회에서 사용하는 Java 참고System.outSystem.out.println();System.out.printf("%d", n)실수형, 문자형 자료 출력 가능Scannernext[자료형]을 이용해서 입력을 받을 수 있고,hasNext[자료형]을 이용해서 입력받을 수 있는 자료형이 있는지 구할 수 있다.두 수 입력 public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int a, b; a = scanner.nextInt(); b = scanner.nextInt(); System.out.println(a + b); } ..

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크3-9. Sorting in Java일반적으로 정렬은 가장 기본적인 알고리즘이기 때문에, 대부분의 프로그래밍 언어가 표준 라이브러리의 일부로 정렬을 제공한다.따라서, 일반적인 상황에서 개발자가 직접 알고리즘을 구현할 경우는 많지 않다고 볼 수 있다.Java에서의 sorting을 알아본다. 기본 타입 데이터의 정렬Arrays 클래스가 primitive 타입 데이터를 위한 정렬 메소드를 제공한다. int[] data = new int[capacity]; ​ //data[0]에서 data[capacity-1]까지 데이터가 꽉 차있는 경우에는 ..