justgo_developer

import java.util.*; public class Main {private static Scanner sc = new Scanner(System.in);public static void main(String[] args) {Queue q = new LinkedList();int N = sc.nextInt();for(int i=1;i

DAG는 방향 사이클이 없는 방향 그래프.ex)작업들의 우선순위 위상정렬(topological ordering)-DAG에서 노드들의 순서화 v1,v2 ....vn, 단, 모든 에지(vi,vj)에 대해서 i

import java.util.*; public class Main {private static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int M = sc.nextInt();int[] cup = new int[4];cup[1]=1;for(int i=0;i

import java.util.Scanner; public class Main {private static Scanner sc = new Scanner(System.in);public static void main(String[] args) {int bar = 64;int x = sc.nextInt();int cnt=0;while(x!=0){if(bar>x){bar=bar/2;}else{x=x-bar;cnt++;}}System.out.print(cnt);}}

1. 출발점 s에서 시작한다.2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다.3. 2번을 계속 반복한다. 4. 만약 unvisited인 이웃노드가 존재하지 않는 동간 계속해서 직전 노드로 되돌아간다.5. 다시 2번을 반복한다.6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. DFS(G, v)visited[v]

정렬 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개의 노드를 가짐 ** 가중치 그래프의 인접행렬..