공부기록/알고리즘 (15) 썸네일형 리스트형 [알고리즘] P2143. 두 배열의 합 package day02.P2143; // 두 배열의 합 풀다가 못풀었음 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Scanner; import java.util.StringTokenizer; public class Main { static int[] A, B, SubA, SubB; static int num1, num2, T; public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer.. 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch3.레드블랙트리 12. 레드블랙트리 – 레드-블랙 트리 - 이진탐색트리의 일종 - 균형잡힌 트리 : 높이가 O(logn) - SEARCH, INSERT, DELETE 연산을 최악의 경우에도 O(logn) 시간 - 각 노드의 하나의 키(key), 왼쪽자식(left), 오른쪽 자식(right) 그리고 부모노드(p)의 주소를 저장 - 자식노드가 존재하지 않을 경우 NIL 노드라고 부르는 특수한 노드가 있다고 가정 - 따라서 모든 리프노드는 NIL노드라고 가정 - 노드들은 내부노드와 NIL 노드로 분류 레드-블랙 트리 : 정의 - 다음의 조건을 만족하는 이진탐색트리 : 1. 각 노드는 red 혹은 black이고, 2. 루트노드는 black이고, 3. 모든 리프노드(즉, NIL노드)는 black이고, 4. red노드의 자식노드들.. 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch2.이진검색트리 10. 트리와 이진트리 – 트리(Tree) 계층적인 구조를 표현 (ex. 조직도, 디렉토리와 서브디렉토리 구조, 가계도) 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨 용어 부모-자식 관계 형제관계 - 루트노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가짐 리프(leaf node)노드 : 자식이 없는 노드 조상-자손 관계 부트리 트리에서 어떤 한 노드와 그 노드의 자손들로 이루어진 트리를 부트리(subtree)라고 부른다 - 트리의 기본적인 성질 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다 트리에서 루트에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다(같은 노드를 두 번 이상 방문하지 않는다는 조건하에) – 이진트리(Bi.. 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch1.정렬 #8~11 섹션 1. 정렬 7. 정렬의 lower bound 저번에 배웠던 정렬 알고리즘! nlogn 이 최선일까? 결론 : O(nlogn) 보다 더 작아질 수는 없다(comparison sort 인 경우에는!) 정렬 알고리즘 - Bubble sort - Insertion sort - Selection sort simple, slow - Quicksort - Merge sort - Heap sort fast - Radix sort O(N) – Comparision sort - 데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘 - 따라서 데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능(문자열, 알파벳, 사용자 정의 객체 등) - 버블 소트, 삽입 정렬, 합병 정렬, 퀵소트, 힙정렬 등 - .. 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch1.정렬 #1~7 섹션 1. 정렬 3. 기본적인 정렬 알고리즘 정렬 알고리즘 - Bubble sort - Insertion sort - Selection sort simple, slow - Quicksort - Merge sort - Heap sort fast - Radix sort O(N) – Selection Sort 각 루프마다 - 최대 원소를 찾는다 - 최대 원소와 맨 오른쪽 원소를 교환한다 - 맨 오른쪽 원소를 제외한다 하나의 원소만 남을 때까지 위 루프를 반복 selectionSort(A[], n) // 배열 A[1...n]을 정렬한다. { for last A[k] 와 A[last]의 값을 교환 ---3 } } 실행시간 : ①의 for 루프는 n-1번 반복 ②에서 가장 큰 수를 찾기 위한 비교 횟수 : n-1,.. 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch0.순환 #4~7 섹션 0. 순환(Recursion) 2-1. Recursion의 응용 : 미로찾기 - Recursive Thinking 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 - 미로찾기(Decision Problem [답이 yes or no인 문제]) 더보기 boolean findPath(x, y) if (x, y) is the exit // 현재 위치가 출구라면 return true else for each neighbouring cell (x', y') of (x, y) do // 인접한 셀 각각에 대해서 if (x', y') is on the pathway if findPath (x', y'.. 영리한 프로그래밍을 위한 알고리즘 강좌 - Ch0.순환 #1~3 섹션 0. 순환(Recursion) 1-1. Recursion의 개념과 기본 예제 1 Recursion : 자기 자신을 호출하는 함수 public class Code01{ public static void main(String [] args){ } public static void func(){ System.out.println("Hello..."); func(); } } -> 무한 루프에 빠지게 됨 recursion은 항상 무한루프에 빠질까? 아니다 recursion이 항상 무한루프에 빠지는 것은 아님. public class Code02{ public static void main(String [] args){ int n = 4; func(n); } public static void func(int .. 이전 1 2 다음
