알고리즘 (25) 썸네일형 리스트형 백준 1761번(JAVA) - 정점들의 거리 import java.util.*; import java.io.*; class Node { int v; int w; Node(int v, int w) { this.v=v; this.w=w; } } public class Main { public static ArrayList[] arr; public static int N; public static int[] Depth; // 깊이 public static int[][] parent;// parent[0][3] 은 3번 노드의 2의0승 부모, //parent[5][3]은 3번 노드의 2의 5승부모, 즉 32번째 부모 public static int[][] length;// length[5][3] 은 3번 노드부터 2의0승 부모까지의 길이 public st.. 운영체제(6) - CPU 스케줄링 CPU bound job CPU를 길게 쓰는 프로그램들 I / O bound job 입출력이 많은 작업들, 키보드 입력같은거 여러 종류의 JOB( = process)이 섞여 있기 때문에 CPU 스케줄링이 필요하다 CPU Scheduler Ready 상태의 프로세스 중에서 이번에 CPU를 줄 프로세스를 고른다. Dispactcher CPU의 제어권을 CPU Scheduler에 의해 선택된 프로세스에게 넘긴다 이 과정을 context switch(문맥교환)라고 한다 CPU스케줄링이 필요할 때 Running - > Blocked ( 예 : I / O 요청을 위한 시스템 콜) - > 자진 반납 Running - > Ready ( 예 : 할당시간만료로 timer interrupt) - > 강제 Blocked - .. 운영체제(5) - 프로세스의 생성과 관련 시스템콜 프로세스 생성 부모 프로세스가 자식프로세스를 생성, fork() 시스템콜을 통하여.. 프로세스의 트리 ( 계층 구조 ) 형성 프로세스는 자원을 필요로 함 운영체제로부터 받는다 부모와 공유 자원의 공유 부모와 자식이 모든 자원을 공유하는 모델 일부를 공유하는 모델 전혀 공유하지 않는 모델 새로운 프로세스 생성시 수행 ( Execution) 상황 2가지 부모와 자식은 공존하며 수행되는 모델 자식이 종료( terminate)될 때까지 부모가 기다리는( wait ) 모델 새로운 프로세스 생성시 주소 공간( Address space) 상황 2가지 자식은 부모의공간을 복사함 자식은 그 공간에 새로운 프로그램을 올림 프로세스 종료 프로세스가 마지막 명령을 수행한 후 운영체제에게 이를 알려준다( exit ) - > 자.. 운영체제(4) - 스케줄러와 Thread 스케줄러 어떤 프로세스에게 자원을 할당할지를 결정하는 운영체제의 모듈을 지칭한다. Long - term Scheduler ( Job Scheduler) 시작 프로세스 중 어떤 것들을 ready queue로 보낼지 결정 프로세스에 memory를 주는 문제 Short - term Scheduler ( CPU Scheduler) 어떤 프로세스를 다음번에 running 시킬지 결정 프로세스에 CPU를 주는 문제 충분히 빨라야 함( millisecond 단위) Medium - term Scheduler ( Swapper) 여유공간 마련을 위해 프로세스를 통째로 메모리에서 디스크로 쫓아냄 프로세스에게서 Memory를 뺏는 문제, Suspended( Stopped) 라는 프로세스의 상태를 일으킬 수 있다. 외부적인 .. 백준 13907번(JAVA)-세금 2차원 DP를 활용한 다익스트라 문제이 import java.util.*; import java.io.*; class Node implements Comparable { int v; int w; int c; Node(int v,int w,int c) { this.v=v; this.w=w; this.c=c; } public int compareTo(Node o) { return w-o.w; } } public class Main { public static int[][] dp; public static int N; public static int S; public static int D; public static void main(String[] args) throws IOException{ // TODO.. 백준 10217번(JAVA) - KCM Travel, 재채점 후 새로운 풀이 분명히 맞았던 문제인데 갑자기 재채점 되면서 시간초과로 틀렸다. 알고보니 어떤 분이 질문게시판에 예시로 어떤 입력을 보여주면서, 이걸로 하면은 대부분의 코드들이 시간초과가 나온다고 질문글을 올렸고(1년전) 그게 최근에 검토가되서 재채점이 된 것이다. 내 기억이 맞다면 이 문제는 꽤 많은 사람들이 맞춰가지고, 다익스트라 분류로 들어가면 상위권에 노출되던 문제였다. 그런데 재채점 후 저~~ 하위권으로 내려갔을 정도로 재채점 후 많은 분들이 틀렸다 그래서 내 다익스트라를 조금 더 다듬어봤다. import java.util.*; import java.io.*; class Node implements Comparable { int v; int c; int d; Node(int v,int c,int d) { thi.. 백준 1194번 달이 차오른다, 가자(JAVA) 비트연산, 비트마스킹과 문자만 좀 다룰 줄 알면 쉽게 풀 수 있는 BFS문제 출처 : https://www.acmicpc.net/problem/1194 1194번: 달이 차오른다, 가자. 첫째 줄에 미로의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 50) 둘째 줄부터 N개의 줄에 미로의 모양이 주어진다. 같은 타입의 열쇠가 여러 개 있을 수 있고, 문도 마찬가지이다. 그리고, www.acmicpc.net import java.util.*; import java.io.*; class Node { int y;//y좌표 int x;//x좌표 int count;//여태까지 움직인 횟수 int bit;//가지고 있는 열쇠 Node(int y,int x,int count,int bit) { t.. 백준 16236번 -아기상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net BFS이지만 신경써줘야 할게 많아서 까다로운 문제이다. 필자도 몇번의 시도끝에 풀었다. 많은 풀이들이 있지만 나는 나만의 방식으로 풀었다. 먹이의 최단거리는 어떻게 구했는가?? 우선순위 큐를 사용해서 count, y좌표 ,x 좌표 순서로 오름차순으로 정렬했다. 이렇게 되면 같은 거리일때 더 위쪽에 있고, 만약 같은 y좌표라면 더 왼쪽에 있는 좌표를 선택하게 될것이다. 처음 Node를 만들 .. 이전 1 2 3 4 다음
