알고리즘12 5. 알고리즘 알고리즘 문제를 해결해나가면서 알면 문제를 더 빠르고 쉽고 정확하게 풀 수 있는 알고리즘을 정리해보겠다. ● 제곱근 구하기 → 바빌로니아 법 a는 제곱근을 원하고자 입력되는 값이고, x는 0~a 사이에 존재하는 임의의 값이다. 이 수식을 원하는 근사치가 나올 때까지 반복 루프를 돌린다. 루프를 많이 돌릴수록 제곱근의 정확도가 높아진다. ● 소수인지 판별하는 알고리즘 → 에라토스테네스의 체 (Sieve of Eratosthenes) #include bool isPrime(int a) { if (a == 1) return false; else { int end = sqrt(a); for (int j = 2; j 2020. 5. 3. [Algorithm] 6-3. Red-Black Tree 이번 시간에는 balanced search tree 중 하나인 red-black tree에 대해 알아보도록 하겠다. ● Red-Black Tree - red-black tree는 binary search tree로써, 아래의 4가지 조건을 만족한다. ① Root Property : root는 검은색이다. ② External Property : 모든 leaf node들은 검은색이다. ③ Internal Property : 빨간 노드의 자식들은 검은 노드이다. (부모와 자식이 모두 빨간색인 경우는 없다.) ④ Depth Property : 모든 leaf node들은 같은 black depth를 가져야한다. * black depth - 어떤 노드에서 root까지 가는 경로에 있는 black 노드들의 수. - .. 2020. 4. 28. [Algorithm] 6-2. Binary Search Tree 저번 시간에는 어려운 개념인 amortized analysis라는 알고리즘 분석 방법에 대한 내용에 대해 알아보았다. 이번 시간에는 binary search tree, 그 중에서도 Red-Black Tree에 대해 알아보도록 하겠다. ● Binary Search Trees - binary search tree는 주로 dictionary라는 추상 자료형을 표현하기 위해 주로 사용된다. 임의의 key를 가진 원소를 삽입, 삭제, 탐색할 수 있고, 최악수행시간은 O(n)이다. - 하지만 balanced binary search tree일 경우에는 최악수행시간이 O(log(n))일 것이다. - 순서가 있는 집합에서의 key를 가지는 노드를 가진 트리이고, 자식은 최대 2개이다. - 왼쪽 서브트리의 모든 키들은 .. 2020. 4. 28. [Algorithm] 1-1. Analyzing Algorithms and Problems - Introduction [Algorithm 카테고리에는 알고리즘을 배우면서 얻은 지식에 관해 주로 다루겠다. 이번 시간에는 알고리즘과 문제를 분석하는 방법의 소개를 하겠다. ● Computer Algorithm - 컴퓨터 알고리즘이란 컴퓨터를 이용하여 문제를 해결하는 잘 정의된 절차, 방법이다. - 컴퓨터를 이용하여 문제를 해결하기 위해서는 먼저 문제를 명확하게 정의해야한다. 그렇지 않으면 문제를 정확히 해결할 수 없고, 엉뚱한 답이 나올 수 있다. - 문제는 입력과 출력을 이용하면 명확하게 정의된다. → 어떤 상황, 즉 입력을 주고 원하는 결과, 즉 출력을 물어보는 것이 문제이다. - 문제를 해결한다는 것은 입력을 출력으로 변환하는 잘 정의된 절차로, 입력을 이용하여 출력을 만들어내는 것이다. ● Problem Solving.. 2020. 4. 26. 이전 1 2 3 다음
