justgo_developer

정렬 selection sort(선택 정렬)1.가장큰값을찾는다.2.맨끝의 자리와 바꾼다.3.똑같은일은 나머지 데이터와 반복한다.시간복잡도 O(n^2) for last

순환 Recursion자기자신을 호출무한루프에 빠진다적절한 구조를 갖추고 있다면 항상 무한루프에 빠지는 것은 아님.적절한 구조란?->base case:적어도 하나의 리커전으로 빠지지 않고 종료되는 경우가 존재해야한다.->recursive case:recursion을 반복하다보면 결국 base case로 수렴해야한다.ex) 피보나치,팩토리얼,최대공약수,X^n 수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다. ex)문자열의 길이 계산public static int length(String str){if(str.equals(""))return 0;elsereturn 1+length(str.substring(1)); }ex)문자열의 프린트public static void printCh..

그래프 순회 -순회(traversal) :그래프의 모든 노드들을 방문하는 일-두가지방법1. BFS(Breath-First Search, 너비우선순회)2. DFS(Depth-First Search, 깊이우선순회) 너비우선순회(BFS) ■ 큐를 이용한 너비우선순회 1. check the start node(체크는 이미 방문된 노드라는 표시)2. insert the start node into the queue 3. while the queue is not empty doremove a node v from queue;for each unchecked neighbour w of v docheck and insert w into the queue;반복한다.노드 방문 순서 : 1,2,3,4,5,7,8,6 ■ BF..

import java.util.*; public class Main {private static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int N = sc.nextInt();int kim = sc.nextInt();int lim = sc.nextInt();int cnt = 0;while(kim!=lim){kim = kim/2 + kim%2;lim = lim/2 + lim%2;cnt++;}System.out.print(cnt);}}

■ (무방향) 그래프(Graph)G=(V,E)- V : 노드(node) 혹은 정점(vertex)- E : 노드쌍을 연결하는 에지(edge) 혹은 링크(link)- 개체(object)들 간의 이진관계를 표현- n=|V|, m=|E| ■ 방향그래프(Directed Graph) G=(V,E)-에지(u,v)는 u로부터 v로의 방향을 가짐 ■ 가중치(weighted) 그래프- 에지마다 가중치(weight)가 지정 ■ 그래프의 표현- 인접행렬(adjacency matrix) - 인접리스트(adjacency list) : 정점 집합을 표현하는 하나의 배열과 각 정점마다 인접한 정점들의 연결리스트m(edge 개수) if 방향그래프라면- 인접행렬은 비대칭- 인접 리스트는 m개의 노드를 가짐 ** 가중치 그래프의 인접행렬..

import java.util.Arrays;import java.util.Scanner; public class Main {private static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int [] in = new int[4];int [] out = new int[4];int [] result = new int[4];for(int i=0;i

레드블랙트리(Red-Black Tree)- 이진탐색트리의 일종- 균형잡힌 트리 : 높이가 O(logn)- SEARCH,INSERT,DELETE를 수정함으로써 균형을 잡히도록 만듬 -각 노드는 하나의키(key),왼쪽자식(left),오른쪽자식(right),그리고 부모노드(p)의 주소를 저장- 자식노드가 존재하지 않을 경우 NIL 노드라고 부르는 특수한 노드가 있다고 가정- 따라서 모든 리프노드는 NIL노드- 루트의 부모도 NIL노드라고 가정- 노드들은 내부노드와 NIL노드로 분류 다음 조건을 만족하는 이진탐색트리 :1. 각 노드는 red 혹은 black이고,2. 루트노드는 black이고 3. 모든 리프노드(즉 NIL노드)는 black이다.4. red노드의 자식노드들은 전부 black이고(즉, red노듣 연속..

이진검색트리(Binary Search Tree)-Dynamic set을 트리의 형태로 구현 정의-이진트리이면서 각 노드에 하나의 키를 저장- 각 노드 v에 대해서 그 노드의 왼쪽 부트리(subtree)에 있는 키들은 key[v]보다 작거나 같고, 오른쪽 부트리에 있는 값은 크거나 같다.**Binary Search Tree하고 heap은 다르다. 최소값 찾기: 왼쪽 자식이 없어야 하고 어떤 노드의 오른쪽 서브트리이면 안된다. TREE-MINIMUM(x)while left[x]≠NILdo x