justgo_developer

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

세마포어(Semaphore) Concurrency 문제를 해결하기 위해 semaphore 사용즉, 공유된 자원에 여러 프로세스들이 동시에 접근하면서 문제가 발생하는데,공유된 자원 속 하나의 데이터는 한번에 하나의 프로세스만 접근할수있도록 만들기 위해 사용 Semaphore : integer variable s3가지 연산만 사용 가능- Initialization operation : 음수가 아닌 값으로 초기화- Wait operation : s--- Signal operation : s++ ■ semWait(s)- 세마포어 값 감소- 만약 값이 음수가 되면 프로세스는 블럭(대기)한다- 음수가 아니면 프로세스는 계속 수행한다. ■ semSigna(s)- 세마포어 값 증가- 만약 값이 양수가 아니면 semWa..

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

병행성(concurrency)정의 : 여러개의 프로세스(또는 스레드)가 동시에 실행되는 시스템의 특성 병행 프로세스의 문제점1. 프로세스간 동기화 문제: 프로세스들이 공유 자원을 동시에 사용할 수 없게 프로세스끼리 순서를 맞춰서 임계구역에 입장해야한다.2. 결정성 문제: 프로세스의 실행순서에 따라 결과값이 달라져선 안된다.3. 교착상태: 문제점을 해결하지 못해 아무것도 못하는 상황concurrency 관련 꼭 알아야 할 용어** deadlock: 교착상태/ 한정된 자원을 여러 곳에서 사용할때 발생/ 무한대기상태** race condition: 한정된 자원을 동시에 이용하려는 여러 프로세스가 서로 경쟁하는 상황**starvation: 기다리는 결과를 예방하기 위해 자원할당할때 발생하는 결과**critica..

정렬 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..

process는 실행중인 프로그램 Thread는 경량화된 프로세스/ 프로세스 내에서 실제 작업을 수행 모든 프로세스는 하나의 스레드를 가지며,여러개의 스레드 즉 멀티쓰레드가 가능하다. 장점- 응답시간 단축- 시스템 처리량 향상- 프로세스의 자원과 메모리 공유함으로써 자원소모 줄임 단점- 다른 프로세스에서는 스레드를 제어할 수 없다.- 여러개의 스레드를 사용할때는 자원공유의 문제가 발생 JAVA Thread code보통 한개의 프로세스는 한가지 일을 하지만, 이 쓰레드를 이용하면 한 프로세스 내에서 두기지 이상의 일을 동시에 할 수 있게 된다.

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);}}