반응형

* 운영체제란?

제한된 컴퓨터 각종 자원을 효율적으로 관리하여 사용자에게 편리한 환경을 제공하는 소프트웨어

* 운영체제 목적 

  • 처리 능력 : 일정 시간 내에 시스템이 처리하는 일의 양
  • 반환 시간 : 시스템에 작업을 의뢰한 시간부터 처리가 완료될 때까지 소요되는 시간
  • 사용 가능도 : 시스템 사용할 필요가 있을 때 즉시 가용 가능한 정도
  • 신뢰도 : 시스템이 주어진 문제를 정확하게 해결하는 정도

* 운영체제 기능

  • 프로세서 관리
  • 기억장치 관리
  • 프로세스 관리
  • 주변장치 관리
  • 파일 및 데이터 관리

* 프로세스

현재 실행중이거나 곧 실행 가능한 PCB를 가진 프로그램

cf) PCB(Process Control Block) : OS가 프로세스의 대한 중요한 정보를 저장하는 곳으로 각 프로세스가 생성될 때 고유 PCB가 생성되고, 프로세스가 완료되면 PCB는 제거된다.

* 스레드(Thread)

  • 프로세스 내에서의 작업 단위로서 시스템의 여러 자원을 할당받아 실행하는 프로그램 단위 
  • 스레드 기반 시스템에서 스레드는 독립적인 스케줄링의 최소 단위로서 프로세스 역할 담당 
  • 하나의 프로세스를 여러 개의 스레드로 생성하여 병행성을 증진시킬 수 있다. 
  • 공통적으로 접근 가능한 기억장치를 통해 효율적으로 통신한다.


CPU 스케줄링

* 개념

프로세스가 생성되어 실행될 때 필요한 시스템의 자원을 해당 프로세스에 할당하는 것

cf) 문맥 교환(Context Switching) : 하나의 프로세스에서 다른 프로세스로 전환할 때 실행하던 프로세스의 상태를 보관하고 새로운 프로세스 정보를 적재하여 실행을 준비하는 것

cf) 준비상태 큐(Ready Queue) : 주기억장치에 적재되어 있으면서 CPU에 의해 실행되기를 준비하는 프로세스들로 구성된 리스트


* 비선점 스케쥴링

이미 할당된 CPU를 다른 프로세스가 강제로 빼앗아 사용할 수 없는 스케쥴링 기법

프로세스가 CPU를 할당받으면 해당 프로세스가 완료될 때까지 CPU를 사용한다.

프로세스의 요구를 공정하게 처리할 수 있지만 중요한 작업이 중요하지 않은 작업을 기다리는 경우가 발생한다.

# FCFS(First Come First Service)

  • 준비상태 큐에 먼저 도착한 순서대로 CPU에 할당하는 기법
  • 공평성은 유지되지만 중요한 작업이 중요하지 않은 작업을 기다리게 된다.

# SJF(Short Job First)

  • 준비상태 큐에서 실행 시간이 가장 짧은 프로세스에게 먼저 CPU를 할당하는 기법
  • 실행 시간이 긴 프로세스는 실행 시간이 짧은 프로세스에 할당 순위가 밀려 무한 연기(기아) 상태가 발생할 수 있다.

# HRN(Hightest Response-ratio Next)

  • SJF 기법을 보완한 것으로 대기 중인 프로세스들의 대기시간과 실행시간을 고려하여 우선순위를 결정한다.
  • 우선순위 계산식 : (대기시간 + 수행시간) / 수행시간


* 선점 스케쥴링

하나의 프로세스가 CPU를 할당받아 실행중일 때 우선순위가 높은 다른 프로세스가 CPU를 강제로 빼앗아 사용할 수 있는 스케쥴링 기법

우선순위가 높은 프로세스를 빠르게 처리할 수 있지만 많은 Overhead를 초래한다.

# Round  Robin

  • 각 프로세스느 시간 할당량(Time Slice)만큼 CPU를 점유하고 실행이 완료되지 않으면 CPU를 반환하고 준비상태 큐의 가장 뒤로 배치
  • 문맥 교환(Context Switching) 효과를 고려하여 시간 할당량을 정한다.
  • 시간 할당량이 클수록 FCFS와 같아지고, 시간 할당량이 작을 수록 문맥 교환 및 오버헤드가 자주발생

# SRT(Shortest Remaining Time)

  • SJF 기법을 선점 형태로 변경한 기법으로 프로세스들 중 남아있는 실행시간이 가장 짧은 프로세스를 다음 프로세스로 선택

# 다단계 큐 스케쥴링

  • 준비완료 큐를 다수의 별도의 큐로 분리하여 각 큐의 독자적인 스케쥴링에 따라 CPU를 할당받는 기법
  • 각각의 서로 다른 작업들이 다른 묶음으로 분리될 수 있을 때 사용한다.
  • 이전 작업이 실행 중이더라도 우선 순위가 높은 큐에 작업이 들어오면 CPU를 반환해야 한다.
  • cf) 우선순위 : 시스템 프로세스 > 대화형 프로세스 > 일괄처리 프로세스

# 다단계 피드백 큐 스케쥴링

  • 프로세스가 큐들 사이를 이동하는 것을 허용하는 기법이다.
  • 프로세스를 CPU 성격에 따라 구분하고 어떤 프로세스가 CPU 시간을 너무 많이 사용하면 한 단계 낮은 우선순위 준비큐로 강등된다.
  • 즉, 짧은 프로세스의 경우 FCFS 방식으로 신속하게 실행되고, 긴 프로세스는 낮은 단계의 준비단계 큐로 밀린다.
  • 낮은 우선순위 큐에서 너무 오래 대기하는 프로세스는 높은 우선순위 큐로 이동한다. (Aging 기법) -> 기아 상태 예방



반응형
저작자표시 비영리 변경금지

'∙Operating System' 카테고리의 다른 글

[정보처리기사]기억장치 관리  (0) 2020.06.30
[정보처리기사]프로세스 동기화  (0) 2020.06.30
[정보처리기사]운영체제와 CPU 스케쥴링  (0) 2020.06.30
[OS] 프로세스 동기화  (0) 2019.04.09
반응형

* 핵심 개념

4월 삼성역테 기출문제이다.

1. 3명의 궁수의 위치를 지정하기 위해 m개 가로열 중 3자리 선택(DFS로 구현)

2. 각 궁수의 위치가 정해지면 3명의 궁수를 BFS 탐색

주의1) 같은 길이면 왼쪽에 있는 몬스터를 먼저 잡기 때문에 dx, dy를 왼쪽, 가운데, 오른쪽 순서대로 해야한다.

주의2) 궁수가 같은 몬스터를 공격할 수도 있기 때문에 찾은 몬스터를 바로 0으로 바꾸지 말것

* 문제

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성 위의 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c2), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {0, -1, 0};
    public static int[] dy = {-1, 0, 1};
    public static int n, m, d, ans = 0;
    public static boolean[] used;   //nCr 구할 때 사용하는 배열
    public static int[][] map;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        d = Integer.parseInt(stk.nextToken());
        map = new int[n + 1][m];
        used = new boolean[m];
        for (int i = 0; i < n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 0; j < m; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        nCr(0, 0);
        System.out.println(ans);
    }
 
    //m개의 자리중 3개의 궁수 자리 선택
    public static void nCr(int idx, int cnt) {
        if (cnt == 3) {
            int[][] nmap = new int[n + 1][m];
            for (int i = 0; i < n + 1; i++) {
                for (int j = 0; j < m; j++) {
                    nmap[i][j] = map[i][j];
                }
            }
            bfs(nmap);
            return;
        }
        for (int i = idx; i < m; i++) {
            if (!used[i]) {
                used[i] = true;
                nCr(i, cnt + 1);
                used[i] = false;
            }
        }
    }
 
    public static void bfs(int[][] nmap) {
        int cnt = 0;
        for (int i = n; i > 0; i--) {   //궁수의 포지션을 한칸씩 앞으로 이동
            int archerIdx = 0;
            Queue<Pair> q = new LinkedList<>();
            for (int j = 0; j < m; j++) {
                //nmap에서 궁수 위치는 2
                if (used[j]) {
                    nmap[i][j] = 2;
                    q.add(new Pair(i - 1, j, 1, archerIdx++));
                } else {    //궁수 위치가 아니면 0
                    nmap[i][j] = 0;
                }
            }
 
            boolean[] isEnemyFind = new boolean[3];     //각 궁수가 몬스터를 찾았는지
            boolean[][][] visited = new boolean[n][m][3];   //각 궁수가 해당 좌표를 방문했는지
            boolean[][] isAlreadyFindLocation = new boolean[n][m];  //이미 다른 궁수가 찾은 목표물인지
            ArrayList<Pair> alist = new ArrayList<>();
 
            while (!q.isEmpty()) {
                Pair p = q.poll();
                if (isEnemyFind[p.idx]) continue;
                if (nmap[p.x][p.y] == 1) {
                    isEnemyFind[p.idx] = true;
                    if (!isAlreadyFindLocation[p.x][p.y]) {
                        isAlreadyFindLocation[p.x][p.y] = true;
                        alist.add(p);
                        cnt++;
                    }
                    continue;
                }
                if (!isEnemyFind[p.idx]) {
                    visited[p.x][p.y][p.idx] = true;
                    for (int j = 0; j < 3; j++) {
                        int nx = p.x + dx[j];
                        int ny = p.y + dy[j];
                        if (nx >= 0 && nx < n && ny >= 0 && ny < m && !visited[nx][ny][p.idx] && p.depth < d) {
                            q.add(new Pair(nx, ny, p.depth + 1, p.idx));
                        }
                    }
                }
            }
            for (int j = 0; j < alist.size(); j++) {
                Pair p = alist.get(j);
                nmap[p.x][p.y] = 0;
            }
        }
        ans = Math.max(ans, cnt);
    }
 
    public static class Pair {
        int x, y, depth, idx;
 
        public Pair(int x, int y, int depth, int idx) {
            this.x = x;
            this.y = y;
            this.depth = depth;
            this.idx = idx;
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/17143 :: 낚시왕  (0) 2019.04.15
[Algorithm] 백준/17136 :: 색종이 붙이기  (1) 2019.04.13
[Algorithm] 백준/15685 :: 드래곤 커브  (0) 2019.04.05
[Algorithm] 백준/15686 :: 치킨 배달  (1) 2019.03.27
반응형

* 핵심 개념

풀어왔던 삼성 기출문제중에서 BFS, DFS 개념이 필요없는 문제

1. 규칙

이전 방향을 Stack에 저장해서(필자는 String에 붙이는 방식 사용) 뒤에서부터 가져다 쓰는 규칙을 찾으면 쉽게 풀림

ex) 1세대를 움직이는데, 이전 이동한 방향이 3, 0 이라면 다음 이동은 1, 0((3+1)%4)이 된다.

2. 0세대

n번째 세대는 2^n번 움직이지만 0세대는 예외로 그냥 움직인다.

이때는 움직임을 저장하지 않고 현재 x,y 좌표만 변경하면 된다.


* 문제

문제

드래곤 커브는 다음과 같은 세 가지 속성으로 이루어져 있으며, 이차원 좌표 평면 위에서 정의된다. 좌표 평면의 x축은 → 방향, y축은 ↓ 방향이다.

  1. 시작 점
  2. 시작 방향
  3. 세대

0세대 드래곤 커브는 아래 그림과 같은 길이가 1인 선분이다. 아래 그림은 (0, 0)에서 시작하고, 시작 방향은 오른쪽인 0세대 드래곤 커브이다.

... 생략

즉, K(K > 1)세대 드래곤 커브는 K-1세대 드래곤 커브를 끝 점을 기준으로 90도 시계 방향 회전 시킨 다음, 그것을 끝 점에 붙인 것이다.

크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오. 격자의 좌표는 (x, y)로 나타내며, 0 ≤ x ≤ 100, 0 ≤ y ≤ 100만 유효한 좌표이다.

입력

첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10)

입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. 드래곤 커브는 서로 겹칠 수 있다.

방향은 0, 1, 2, 3 중 하나이고, 다음을 의미한다.

  • 0: x좌표가 증가하는 방향 (→)
  • 1: y좌표가 감소하는 방향 (↑)
  • 2: x좌표가 감소하는 방향 (←)
  • 3: y좌표가 증가하는 방향 (↓)

출력

첫째 줄에 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 것의 개수를 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {1, 0, -1, 0};
    public static int[] dy = {0, -1, 0, 1};
    public static boolean[][] visited = new boolean[101][101];
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int i = 1; i <= t; i++) {
            stk = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(stk.nextToken());
            int y = Integer.parseInt(stk.nextToken());
            int d = Integer.parseInt(stk.nextToken());
            int g = Integer.parseInt(stk.nextToken());
            String s = String.valueOf(d);
            visited[x][y] = true;
 
            for (int j = 0; j <= g; j++) {
                //1세대마다 2의 제곱으로 늘어남
                if (j != 0 && s.length() >= Math.pow(2, j)) continue;
                for (int k = s.length() - 1; k >= 0; k--) {
                    int nd;
                    if (j == 0) nd = s.charAt(k) - '0';
                    else nd = (s.charAt(k) - '0' + 1) % 4;
 
                    int nx = x + dx[nd];
                    int ny = y + dy[nd];
                    visited[nx][ny] = true;
                    x = nx;
                    y = ny;
                    if (j != 0) s += nd;
                }
            }
        }
        System.out.println(check());
    }
 
    public static int check() {
        int ans = 0;
        for (int i = 0; i < 100; i++) {
            for (int j = 0; j < 100; j++) {
                if (visited[i][j] && visited[i + 1][j] && visited[i][j + 1] && visited[i + 1][j + 1]) ans++;
            }
        }
        return ans;
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/17136 :: 색종이 붙이기  (1) 2019.04.13
[Algorithm] 백준/17135 :: 캐슬 디펜스  (0) 2019.04.06
[Algorithm] 백준/15686 :: 치킨 배달  (1) 2019.03.27
[Algorithm] 백준/16234 :: 인구 이동  (0) 2019.03.24
반응형

* 핵심

1. DFS 를 이용하여 nCr 개의 치킨집을 선택 (순서 상관 x)

# 주의할 점 

nCr을 구할 때 for문을 처음부터 시작하면 시간 초과가 발생한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
// 시간초과 발생
public static void nCr(int cnt) {
    if (cnt == m) {
        dist();
        return;
    }
    for (int i = 1; i <= chickList.size(); i++) {
        if (!chickVisited[i]) {
            chickVisited[i] = true;
            nCr(i, cnt + 1);
            chickVisited[i] = false;
        }
    }
}
 
// 시간 줄이는 nCr
public static void nCr(int idx, int cnt) {
    if (cnt == m) {
        dist();
        return;
    }
    for (int i = idx; i <= chickList.size(); i++) {
        if (!chickVisited[i]) {
            chickVisited[i] = true;
            nCr(i, cnt + 1);
            chickVisited[i] = false;
        }
    }
}
cs

idx값을 추가로 넘겨주고 for문을 idx부터 시작해야 시간을 단축시킬 수 있다.

2. 선택된 치킨집에서 집까지의 단순 좌표값을 빼서 치킨 거리 저장

선택된 치킨집에서 BFS를 사용하여 풀 수 도 있지만, 시간 초과 발생    -> map에 장애물이 없으므로 BFS보단 좌표계산이 훨씬 빠름

* 문제

문제

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸, 왼쪽에서부터 c번째 칸을 의미한다. r과 c는 1부터 시작한다.

이 도시에 사는 사람들은 치킨을 매우 좋아한다. 따라서, 사람들은 "치킨 거리"라는 말을 주로 사용한다. 치킨 거리는 집과 가장 가까운 치킨집 사이의 거리이다. 즉, 치킨 거리는 집을 기준으로 정해지며, 각각의 집은 치킨 거리를 가지고 있다. 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.

임의의 두 칸 (r1, c1)과 (r2, c2) 사이의 거리는 |r1-r2| + |c1-c2|로 구한다.

예를 들어, 아래와 같은 지도를 갖는 도시를 살펴보자.

0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
0 0 0 1 1
0 0 0 1 2

0은 빈 칸, 1은 집, 2는 치킨집이다.

(2, 1)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |2-1| + |1-2| = 2, (5, 5)에 있는 치킨집과의 거리는 |2-5| + |1-5| = 7이다. 따라서, (2, 1)에 있는 집의 치킨 거리는 2이다.

(5, 4)에 있는 집과 (1, 2)에 있는 치킨집과의 거리는 |5-1| + |4-2| = 6, (5, 5)에 있는 치킨집과의 거리는 |5-5| + |4-5| = 1이다. 따라서, (5, 4)에 있는 집의 치킨 거리는 1이다.

이 도시에 있는 치킨집은 모두 같은 프랜차이즈이다. 프렌차이즈 본사에서는 수익을 증가시키기 위해 일부 치킨집을 폐업시키려고 한다. 오랜 연구 끝에 이 도시에서 가장 수익을 많이 낼 수 있는  치킨집의 개수는 최대 M개라는 사실을 알아내었다.

도시에 있는 치킨집 중에서 최대 M개를 고르고, 나머지 치킨집은 모두 폐업시켜야 한다. 어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 13)이 주어진다.

둘째 줄부터 N개의 줄에는 도시의 정보가 주어진다.

도시의 정보는 0, 1, 2로 이루어져 있고, 0은 빈 칸, 1은 집, 2는 치킨집을 의미한다. 집의 개수는 2N개를 넘지 않으며, 적어도 1개는 존재한다. 치킨집의 개수는 M보다 크거나 같고, 13보다 작거나 같다.

출력

첫째 줄에 폐업시키지 않을 치킨집을 최대 M개를 골랐을 때, 도시의 치킨 거리의 최솟값을 출력한다.


* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int n, m, ans = Integer.MAX_VALUE;
    public static int[][] map;  //지도
    public static boolean[] chickVisited;       //nCr에서 방문한 치킨집
    public static ArrayList<Pair> homeList = new ArrayList<>();     //집 위치
    public static ArrayList<Pair> chickList = new ArrayList<>();    //치킨집 위치
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        n = Integer.parseInt(stk.nextToken());
        m = Integer.parseInt(stk.nextToken());
        map = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
                if (map[i][j] == 1) {
                    homeList.add(new Pair(i, j));
                } else if (map[i][j] == 2) {
                    chickList.add(new Pair(i, j));
                }
            }
        }
        chickVisited = new boolean[chickList.size() + 1];
 
        nCr(1, 0);
        System.out.println(ans);
    }
 
    public static void nCr(int idx, int cnt) {
        if (cnt == m) {
            dist();
            return;
        }
        for (int i = idx; i <= chickList.size(); i++) {
            if (!chickVisited[i]) {
                chickVisited[i] = true;
                nCr(i, cnt + 1);
                chickVisited[i] = false;
            }
        }
    }
 
    public static void dist() {
        int sum = 0;
        for (int i = 0; i < homeList.size(); i++) {
            Pair homeInfo = homeList.get(i);
            int tmp = Integer.MAX_VALUE;
            for (int j = 1; j < chickVisited.length; j++) {
                if (chickVisited[j]) {
                    Pair chickInfo = chickList.get(j - 1);
                    int chickDist = Math.abs(homeInfo.x - chickInfo.x) + Math.abs(homeInfo.y - chickInfo.y);
                    tmp = Math.min(tmp, chickDist);
                }
            }
            sum += tmp;
        }
        ans = Math.min(ans, sum);
    }
 
    public static class Pair {
        int x, y;
 
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/17135 :: 캐슬 디펜스  (0) 2019.04.06
[Algorithm] 백준/15685 :: 드래곤 커브  (0) 2019.04.05
[Algorithm] 백준/16234 :: 인구 이동  (0) 2019.03.24
[Algorithm] 백준/13460 :: 구슬 탈출 2  (0) 2019.03.10
반응형

* 핵심 개념

서류 등수나 면접 등수중 하나만 높으면 뽑을 수 있다.

서류 등수 순으로 정렬하고, 면접 등수의 최소값을 계속 비교하면서 cnt를 증가하면 된다.

* 문제

문제

언제나 최고만을 지향하는 굴지의 대기업 진영 주식회사가 신규 사원 채용을 실시한다. 인재 선발 시험은 1차 서류심사와 2차 면접시험으로 이루어진다. 최고만을 지향한다는 기업의 이념에 따라 그들은 최고의 인재들만을 사원으로 선발하고 싶어 한다.

그래서 진영 주식회사는, 다른 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다는 원칙을 세웠다. 즉, 어떤 지원자 A의 성적이 다른 어떤 지원자 B의 성적에 비해 서류 심사 결과와 면접 성적이 모두 떨어진다면 A는 결코 선발되지 않는다.

이러한 조건을 만족시키면서, 진영 주식회사가 이번 신규 사원 채용에서 선발할 수 있는 신입사원의 최대 인원수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성적, 면접 성적의 순위가 공백을 사이에 두고 한 줄에 주어진다. 두 성적 순위는 모두 1위부터 N위까지 동석차 없이 결정된다고 가정한다.

출력

각 테스트 케이스에 대해서 진영 주식회사가 선발할 수 있는 신입사원의 최대 인원수를 한 줄에 하나씩 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int test = 1; test <= t; test++) {
            int n = Integer.parseInt(br.readLine());
            Pair[] pair = new Pair[n];
 
            for (int i = 0; i < n; i++) {
                stk = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(stk.nextToken());
                int y = Integer.parseInt(stk.nextToken());
                pair[i] = new Pair(x, y);
            }
            Arrays.sort(pair, new Comparator<Pair>() {
                @Override
                public int compare(Pair o1, Pair o2) {
                    return o1.x - o2.x;
                }
            });
            int min = pair[0].y;
            int cnt = 1;
            for (int i = 1; i < n; i++) {
                if (pair[i].y < min) {
                    min = pair[i].y;
                    cnt++;
                }
            }
            sb.append(cnt + "\n");
        }
        System.out.println(sb);
    }
 
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm' 카테고리의 다른 글

[Algorithm] 백준/2493 :: 탑  (0) 2019.04.27
[Algorithm] 백준/1655 :: 가운데를 말해요  (0) 2019.04.21
[Algorithm] 백준/1931 :: 회의실배정  (0) 2019.03.07
[Algorithm] 백준/16985 :: Maaaaaaaaaze  (0) 2019.03.01
반응형

* 핵심

삼성기출중 쉬운편에 속하는 문제이다.

2중 For문을 돌면서 BFS로 탐색하면 된다.

문제에서 설명이 조금 애매한데, 몇 번이라기보다는 몇 일이 걸린다고 이해하는게 편하다.

하루에 인구 이동한 나라는 그 날은 또 다른 나라랑 연합을 맺을 수 없다.

문제에 주어진 마지막 예시를 보면,

1일차

2일차

3일차

위 예제를 보면 6번의 인구 이동이 있지만 3일에 걸쳐 인구 이동되었기 때문에 3을 출력하는 것이 맞다.

* 문제

문제

N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모든 나라는 1×1 크기이기 때문에, 모든 국경선은 정사각형 형태이다.

오늘부터 인구 이동이 시작되는 날이다.

인구 이동은 다음과 같이 진행되고, 더 이상 아래 방법에 의해 인구 이동이 없을 때까지 지속된다.

  • 국경선을 공유하는 두 나라의 인구 차이가 L명 이상, R명 이하라면, 두 나라가 공유하는 국경선을 오늘 하루동안 연다.
  • 위의 조건에 의해 열어야하는 국경선이 모두 열렸다면, 인구 이동을 시작한다.
  • 국경선이 열려있어 인접한 칸만을 이용해 이동할 수 있으면, 그 나라를 오늘 하루 동안은 연합이라고 한다.
  • 연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)가 된다. 편의상 소수점은 버린다.
  • 연합을 해체하고, 모든 국경선을 닫는다.

각 나라의 인구수가 주어졌을 때, 인구 이동이 몇 번 발생하는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, L, R이 주어진다. (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)

둘째 줄부터 N개의 줄에 각 나라의 인구수가 주어진다. r행 c열에 주어지는 정수는 A[r][c]의 값이다. (1 ≤ A[r][c] ≤ 100)

인구 이동이 발생하는 횟수가 2,000번 보다 작거나 같은 입력만 주어진다.

출력

인구 이동이 몇 번 발생하는지 첫째 줄에 출력한다.

* 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.io.*;
import java.util.*;
 
public class Main {
    public static StringTokenizer stk;
    public static StringBuilder sb = new StringBuilder();
    public static int[] dx = {1, -1, 0, 0};
    public static int[] dy = {0, 0, 1, -1};
    public static int min, max, ans = 0;
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        stk = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(stk.nextToken());
        min = Integer.parseInt(stk.nextToken());
        max = Integer.parseInt(stk.nextToken());
        int[][] map = new int[n + 1][n + 1];
        boolean[][] visited = new boolean[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            stk = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                map[i][j] = Integer.parseInt(stk.nextToken());
            }
        }
        boolean hasMoreMoving = false;  //while문에서 인구이동 발생 여부 확인
        while (!hasMoreMoving) {
            Queue<Pair> q = new LinkedList<>();
            int sum = 0, cnt = 0;                           //sum = 인구 이동할 나라의 사람수, cnt = 인구 이동한 나라 개수
            ArrayList<Pair> alist = new ArrayList<>();      //해당 점을 방문했을 때 이동한 점의 좌표 정보
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    q.add(new Pair(i, j));
                    while (!q.isEmpty()) {
                        Pair p = q.poll();
                        if (!visited[p.x][p.y]) {
                            visited[p.x][p.y] = true;
                            cnt++;
                            sum += map[p.x][p.y];
                            alist.add(new Pair(p.x, p.y));
                            for (int k = 0; k < 4; k++) {
                                int nx = p.x + dx[k];
                                int ny = p.y + dy[k];
                                if (nx > 0 && nx <= n && ny > 0 && ny <= n && !visited[nx][ny] && checkPerson(map[p.x][p.y], map[nx][ny])) {
                                    q.add(new Pair(nx, ny));
                                }
                            }
                        }
                    }
 
                    //방문한 좌표가 인구 이동이 필요한 경우
                    if (alist.size() > 1) {
                        int movingSum = sum / cnt;
                        for (int k = 0; k < alist.size(); k++) {
                            Pair p = alist.get(k);
                            map[p.x][p.y] = movingSum;
                        }
                        hasMoreMoving = true;
                    }
                    //매 시작점마다 초기화
                    alist = new ArrayList<>();
                    sum = 0;
                    cnt = 0;
                }
            }   //end of for
            if (hasMoreMoving) {        //더이상 움직일 게 있다면 visited배열 초기화
                ans++;
                hasMoreMoving = false;
                visited = new boolean[n + 1][n + 1];
            } else break;
        }
        System.out.println(ans);
    }
 
    //현재 인구와 이동할 인구의 차이 계산
    public static boolean checkPerson(int curCnt, int nextCnt) {
        int absCnt = Math.abs(curCnt - nextCnt);
        if (absCnt >= min && absCnt <= max) return true;
        else return false;
    }
 
    public static class Pair {
        int x, y;
 
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}
cs


반응형
저작자표시 비영리 변경금지

'∙Algorithm > 삼성 SW 역량테스트' 카테고리의 다른 글

[Algorithm] 백준/15685 :: 드래곤 커브  (0) 2019.04.05
[Algorithm] 백준/15686 :: 치킨 배달  (1) 2019.03.27
[Algorithm] 백준/13460 :: 구슬 탈출 2  (0) 2019.03.10
[Algorithm] 백준/16236 :: 아기 상어  (0) 2019.03.10
반응형

* TCP((Transmission Control Protocol) 

- 인터넷 상에서 데이터를 패킷 형태로 보내기 위해 IP와 함께 사용하는 프로토콜이다. 

- TCP와 IP를 함께 사용하는데, TCP는 발신지에서 수신지로 패킷을 전송하기 위한 논리적 경로를 배정한다.

- 연결형 서비스로 가상 회선 방식을 제공한다. 

>> 연결 시 3-way Handshaking 사용, 해체 시 4-way Handshaking 사용

- 흐름제어(송신하는 곳에서 감당이 안되게 많은 데이터를 빠르게 보내 수신하는 곳에서 문제가 일어나는 것을 막는다.)

- 혼잡제어(네트워크 내의 패킷 수가 넘치게 증가하지 않도록 방지하는 것)

- 높은 신뢰성을 보장하지만 UDP보다 느린 속도를 가진다. ( 신뢰성 > 속도 )


* UDP(User Datagram Protocol)

- 데이터를 데이터그램 단위로 처리하는 프로토콜, 데이터그램이란 독립적인 관계를 지니는 패킷

- 비연결형 프로토콜로 연결을 위한 논리적인 경로가 없다. 즉, 각각 다른 경로로 패킷을 전송하여 빠른 속도를 보여준다.

- UDP Header의 CheckSum 필드를 통해 최소한의 오류만 검출한다.

- 흐름제어를 못하기 때문에 패킷이 재대로 전송 되었는지, 오류가 없는지 확인할 수 없다.

- 빠른 속도를 보여주지만 신뢰성이 없다. 스트리밍같은 서비스에 주로 사용된다.


반응형
저작자표시 비영리 변경금지

'∙Network' 카테고리의 다른 글

[정보처리기사]TCP/IP  (0) 2020.06.30
[Network] OSI 7 Layer란?  (0) 2019.03.22
[Network] HTTP와 REST API  (0) 2019.02.13
[Network] 주소창에 www.naver.com을 치면 일어나는 일  (0) 2018.12.13
반응형

OSI 7 Layer이란?

- 개방형 시스템 상호연결(Open System Intercon-nection, OSI) 모델

- 상호 이질적인 네트워크간의 연결에 어려움이 많은데 이러한 호환성의 결여를 막기위해 ISO(국제 표준화 기구)에서는 OSI 참조모델을 제시함

- 네트워크에서 통신이 일어나는 과정을 7단계로 나눈 것

Why? 네트워크 통신 과정을 7단계로 나눈 이유는?

>> 계층을 나눈 이유는 통신이 일어나는 과정이 단계별로 파악할 수 있기 때문이다!

>> 문제가 발생하더라도 해당 계층만 고치면 된다


OSI 7 Layer 구조

1단계 : 물리 계층(Physical)

- 말 그대로 시스템의 물리적 표현을 나타낸다. (=물리적 장비)

2단계 : 데이터 링크 계층 (Data Link)

- 노드 간 데이터 전송을 제공하며 물리 계층의 오류 수정도 처리한다. 

- 주소 값은 물리적으로 할당 받는데, 이는 네트워크 카드가 만들어질 때부터 맥 주소(MAC address)가 정해져 있다는 뜻이다. ex) 이더넷

3단계 : 네트워크 계층(Network)

- 여러개의 노드를 거칠때마다 경로를 찾아주는 역할을 하는 계층

- 데이터를 목적지까지 가장 안전하고 빠르게 전달하는 기능(라우팅)

- 보스턴에 있는 컴퓨터가 캘리포니아에 있는 서버에 연결하려고 할 때 그 경로는 수백 만 가지다. 이 계층의 라우터가 이 작업을 효율적으로 처리한다. 

4단계 : 전송 계층(Transport)

- 양 끝단(End to end)의 사용자들이 신뢰성있는 데이터를 주고 받을 수 있도록 해 주어, 상위 계층들이 데이터 전달의 유효성이나 효율성을 생각하지 않도록 해준다.

- 전송 계층은 특정 연결의 유효성을 제어하고, 일부 프로토콜은 상태 개념이 있고(stateful), 연결 기반(connection oriented)이다. 대표적인 예로 TCP가 있다.

5단계 : 세션 계층(Session)

- 양 끝단의 응용 프로세스가 통신을 관리하기 위한 방법을 제공한다.

- TCP/IP 세션을 만들고 없애는 책임을 진다.

6단계 : 표현 계층(Presentation)

- 코드 간의 번역을 담당하여 사용자의 명령어를 완성 및 결과 표현한다. 

- 데이터를 안전하게 전송하기 위해 암호화/복호화 하는 역할 수행

7단계 : 응용 계층(Application)

- HTTP, FTP, SMTP, POP3, IMAP, Telnet 등과 같은 프로토콜이 있다.

- 사용자는 용도에 맞는 프로토콜을 선택하고 응용 프로세스와 직접 관계하여 일반적인 응용 서비스를 수행한다. ex) MS Office, Chrome ...


OSI 7 Layer 쉽게 외우는 방법

CIOKorea에 재미있는 방법이 있어 공유!

물리 계층에서 응용 계층까지(아래에서 위로)(P-D-N-T-S-P-A) 

소시지 피자를 버리지 말아 주세요(Please-Do-Not-Throw-Sausage-Pizza-Away) 


* 참고

https://github.com/WeareSoft/tech-interview/

https://shlee0882.tistory.com/110

http://www.ciokorea.com/news/36536



반응형
저작자표시 비영리 변경금지

'∙Network' 카테고리의 다른 글

[정보처리기사]TCP/IP  (0) 2020.06.30
[Network] TCP/UDP란?  (0) 2019.03.22
[Network] HTTP와 REST API  (0) 2019.02.13
[Network] 주소창에 www.naver.com을 치면 일어나는 일  (0) 2018.12.13

티스토리툴바