오늘의 계획을 다 실행해보자
공부하게 하시는 하나님께 감사드린다..!
Part. CS
스레싱
메모리의 페이지 폴트율이 높은 것을 의미하며, 컴퓨터의 심각한 성능 저하를 초래한다.
스레싱은 메모리에 너무 많은 프로세스가 동시에 올라가게 되면 스와핑이 많이 일어나서 발생하는 것이다.
페이지 폴트가 일어나면 CPU 이용률이 낮아진다.
CPU 이용률이 낮아지게 되면 운영체제는 "CPU가 한가한가?"라고 생각하여 가용성을 더 높이기 위해 더 많은 프로세스를 메모리에 올리게 된다. 이러한 상황이 악순환이 반복되면 스레싱이 일어나게 된다.
해결 방안
메모리를 늘리거나, HDD를 사용한다면 HDD를 SSD로 바꾸는 방법이 있다.
운영체제에서 이를 해결할 수 있는 방법은 작업 세트, PFF가 있다.
작업 세트
프로세스의 과거 사용 이력인 지역성을 통해 결정된 페이지 집합을 만들어서 미리 메모리에 로드하는 것이다.
미리 메모리에 로드하면 탐색에 드는 비용을 줄일 수 있고, 스와핑 또한 줄일 수 있다.
PFF
페이지 폴트 빈도를 조절하는 방법으로 상한선과 하한선을 만드는 방법
상한선에 도달한다면 프레임을 늘리고, 하한선에 도달한다면 프레임을 줄이는 것
메모리 할당
메모리에 프로그램을 할당할 때는 시작 메모리 위치, 메모리의 할당 크기를 기반으로 할당한다.
연속 할당과 불연속 할당으로 나뉜다.
연속 할당
메모리에 연속적으로 공간을 할당하는 것을 말한다.
메모리를 미리 나누어 관리하는 고정 분할 방식과 매 시점 프로그램의 크기에 맞게 메모리를 분할하여 사용하는 가변 분할 방식이 있다.
고정 분할 방식
메모리를 미리 나누어 관리하는 방식, 메모리가 미리 나뉘어 있기 때문에 융통성이 없다. 내부 단편화가 발생한다.
가변 분할 방식
매 시점 프로그램의 크기에 맞게 동적으로 메모리를 나눠 사용한다.
내부 단편화는 발생하지 않고, 외부 단편화는 발생할 수 있다.
최초적합(first fit), 최적적합(best fit), 최악적합(worst fit)이 있다.
| 이름 | 설명 |
| 최초 적합 | 위쪽이나 아래쪽부터 시작해서 홀을 찾으면 바로 할당 |
| 최적 적합 | 프로세스의 크기 이상인 공간 중 가장 작은 홀부터 할당 |
| 최악 적합 | 프로세스의 크기와 가장 많이 차이가 나는 홀에 할당 |
내부 단편화 : 메모리를 나눈 크기보다 프로그램이 작아서 들어가지 못하는 공간이 많이 발생하는 현상
외부 단편화 : 메모리를 나눈 크기보다 프로그램이 커서 들어가지 못하는 공간이 많이 발생하는 현상
홀 : 할당할 수 있는 비어 있는 메모리 공간
불연속 할당
메모리를 연속적으로 할당하지 않는 불연속 할당은 현대 운영체제가 쓰는 방법으로 불연속 할당인 페이징 기법이 있다.
메모리를 동일한 크기의 페이지로 나누고 프로그램마다 페이지 테이블을 두어 이를 통해 메모리에 프로그램을 할당하는 것이다.
페이징 기법 말고도 세그멘테이션, 페이지드 세그멘테이션이 있다.
페이징
동일한 크기의 페이지 단위로 나누어 메모리의 서로 다른 위치에 프로세스를 할당한다.
홀의 크기가 균일하지 않은 문제가 없어지지만 주소 변환이 복잡해진다.
세그멘테이션
페이지 단위가 아닌 의미 단위인 세그먼트로 나누는 방식이다.
프로세스를 이루는 메모리는 코드 영역, 데이터 영역, 스택 영역, 힙 영역으로 이루어지는데, 코드와 데이터로 나누거나 코드 내의 작은 함수를 세그먼트로 놓고 나눌 수도 있다.
공유와 보안 측면에서 장점을 가지지만 홀 크기가 균일하지 않다는 단점이 있다.
페이지드 세그멘테이션
프로그램을 의미 단위인 세그먼트로 나눠 공유나 보안 측면에 강점을 두고 임의의 길이가 아닌 동일한 크기의 페이지 단위로 나누는 것
페이지 교체 알고리즘
메모리는 한정되어 있기 때문에 스와핑이 많이 일어난다.
스와핑은 많이 일어나지 않도록 설계되어야 하며 이는 페이지 교체 알고리즘 기반으롸 스와핑이 일어난다.
오프라인 알고리즘
먼 미래에 참조되는 페이지와 현재 할당하는 페이지를 바꾸는 알고리즘, 가장 좋은 방법
그러나, 미래에 사용되는 프로세스를 우리가 알 수 있을까? 알 수 없다.
사용할 수 없는 알고리즘이지만 가장 좋은 알고리즘이므로 다른 알고리즘과의 성능 비교에 대한 상한 기준을 제공한다.
FIFO
FIFO(First In First Out)은 가장 먼저 온 페이지를 교체 영역에 가장 먼저 놓는 방법
LRU
LRU(Least Recent Used)는 참조가 가장 오래된 페이지를 바꾼다.
오래된 것을 파악하기 위해 각 페이지마다 계수기, 스택을 두어야 하는 문제점이 있다.
LRU를 구현할 때는 보통 두 개의 자료 구조로 구현한다. 해시 테이블, 이중 연결 리스트이다.
해시 테이블은 이중 연결 리스트에서 빠르게 찾을 수 있도록 쓰고, 이중 연결 리스트는 한정된 메모리를 나타낸다.
C++로 구현한 코드
#include<bits/stdc++.h>
using namespace std;
class LRUCache {
list<int> li;
unorderd_map<int, list<int>::iterator> hash;
int csize;
public:
LRUCache(int);
void refer(int);
void display();
};
LRUCache::LRUCache(int n){
csize = n;
}
void LRUCache::refer(int x){
if(hash.find(x) == hash.end()){
if(li.size() == csize){
// 가장 끝에 있는 것을 뽑아낸다.
int last = li.back();
li.pop_back();
hash.erase(last);
}
}else {
li.erase(hash[x]);
}
// 해당 페이지를 참조할 때
// 가장 앞에 붙인다. 또한 이를 해시 테이블에 저장한다.
li.push_front(x);
hash[x] = li.begin();
}
NUR
LRU에서 발전한 NUR(Not Used Recently) 알고리즘이 있다.
일명 clock 알고리즘이라고 하며 먼저 0과 1을 가진 비트를 둔다. 1은 최근에 참조되었고 0은 참조되지 않음을 의미한다.
시계 방향으로 돌면서 0을 찾고 0을 찾은 순간 해당 프로세스를 교체하고, 해당 부분을 1로 바꾸는 알고리즘이다.
LFU
LFU(Least Frequently Used)는 가장 참조 횟수가 적은 페이지를 교체한다.
많이 사용되지 않은 것을 교체한다.
프로세스와 스레드
프로세스는 컴퓨터에서 실행되고 있는 프로그램을 말하며, CPU 스케줄링의 대상이 되는 작업이라는 용어와 같은 의미
스레드는 프로세스 내 작업의 흐름을 지칭
프로그램이 메모리에 올라가면 프로세스가 되는 인스턴스화가 일어나고, 이후 운영체제의 CPU 스케줄러에 따라 CPU가 프로세스를 실행한다.
프로세스와 컴파일 과정
프로세스는 프로그램이 메모리에 올라가 인스턴스화된 것을 말한다.
ex) 구글 크롬 프로그램을 두번 클릭하면 구글 크롬 프로세스로 변환되는 것
컴파일 과정
C언어를 기준으로 봤을때, 컴파일러가 컴파일 과정을 통해 컴퓨터가 이해할 수 있는 기계어로 번역하여 실행할 수 있는 파일을 만들게 된다.
전처리
소스 코드의 주석을 제거하고 #include 등 헤더 파일을 병합하여 매크로를 치환한다.
컴파일러
오류 처리, 코드 최적화 작업을 하며 어셈블리어로 변환한다.
어셈블러
어셈블리어는 목적 코드로 변환된다. 이때 확장자는 운영체제마다 다른데 리눅스에서는 .o이다.
링커
프로그램 내에 있는 라이브러리 함수 또는 다른 파일들과 목적 코드를 결합하여 파일을 만든다.
실행 파일의 확장자는 .exe 또는 .out이라는 확장자를 갖는다.
Part. Java
Generic
와일드 카드
class Juicer {
static Juice makeJuice(FruitBox<Fruit> box) { // <Fruit>로 지정
String tmp = "";
for(Fruit f : box.getList()) {
tmp += f + " ";
}
return new Juice(tmp);
}
}과일박스를 대입하면 주스를 만들어서 반환하는 Juicer라는 클래스가 있고, 이 클래스에는 과일을 주스로 만들어서 반환하는 makeJuice()라는 static 메서드가 정의되어 있다.
Juicer 클래스는 지네릭 클래스가 아닌데다, 지네릭 클래스라고 해도 static 메서드에는 타입 매개변수 T를 매개변수에 사용할 수 없으므로 아예 지네릭스를 적용하지 않던가, 타입 매개변수 대신, 특정 타입을 지정해줘야 한다.
Juicer.makeJuice(appleBox); // 에러 FruitBox<Apple>
지네릭 타입을 FruitBox<Fruit>로 고정해 놓으면, 위의 코드에서 알 수 있듯이 FruitBox<Apple> 타입의 객체는 makeJuice()의 매개변수가 될 수 없으므로, 여러 가지 타입의 매개변수를 가지는 makeJuice()를 만들 수밖에 없다.
static Juice makeJuice(FruitBox<Fruit> box) { // <Fruit>로 지정
String tmp = "";
for(Fruit f : box.getList()) {
tmp += f + " ";
}
return new Juice(tmp);
}
static Juice makeJuice(FruitBox<Apple> box) {
String tmp = "";
for(Fruit f : box.getList()) {
tmp += f + " ";
}
return new Juice(tmp);
}이렇게 오버로딩하면, 컴파일 에러가 발생한다. 지네릭 타입이 다른 것만으로는 오버로딩이 성립하지 않기 때문이다.
지네릭 타입은 컴파일러가 컴파일 할 때만 사용하고 제거해버린다. 그래서 위의 두 메서드는 오버로딩이 아니라 '메서드 중복 정의'이다.
이럴 때 사용하기 위해 고안 된것이 바로 '와일드 카드'이다. 와일드 카드는 기호 "?"로 표현하는데, 와일드 카드는 어떠한 타입도 될 수 있다.
"?"는 Object타입과 다를 게 없다.
'extends'와 'super'로 상한과 하한을 제한할 수 있다.
<? extends T> 와일드 카드의 상한 제한, T와 그 자손들만 가능
<? super T> 와일드 카드의 하한 제한, T와 그 조상들만 가능
<?> 제한 없음. 모든 타입이 가능 <?extends Object>와 동일
makeJuice()의 매개변수 타입을 FruitBox<Fruit>에서 FruitBox <? extends Fruit>으로 변경
class Juicer {
static Juice makeJuice(FruitBox<? extends Fruit> box) { // <Fruit>로 지정
String tmp = "";
for(Fruit f : box.getList()) {
tmp += f + " ";
}
return new Juice(tmp);
}
}
오류 발생하지 않는다.
FruitBox<Fruit> fruitBox = new FruitBox<Fruit>();
FruitBox<Apple> appleBox = new FruitBox<Apple>();
FruitBox<Fruit> 뿐만 아니라 FruitBox<Apple>와 FruitBox<Grape>도 가능하게 된다.
매개변수 타입을 FruitBox<? extends Object>로 하면, 모든 종류의 FruitBox가 이 메서드의 매개변수로 가능해진다.
box의 요소가 Fruit의 자손이라는 보장이 없으므로 아래의 for문에서 box에 저장된 요소를 Fruit타입의 참조변수로 못받는다.
static Juice makeJuice(FruitBox<? extends Object> box) { // <Fruit>로 지정
String tmp = "";
for(Fruit f : box.getList()) {
tmp += f + " ";
}
return new Juice(tmp);
}
실제 테스트 해보면 문제없이 컴파일 된다. 이유는 바로 지네릭 클래스 FruitBox를 제한했기 때문이다.
class FruitBox<T extends Fruit> extends Box<T> {}
컴파일러는 위 코드로부터 모든 FruitBox의 요소들이 Fruit의 자손이라는 것을 알고 있으므로 문제 삼지 않는 것이다.
package com.example.javabible.ch12_지네릭스.FruitBoxEx4;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
class Fruit {
String name;
int weight;
public Fruit(String name, int weight) {
this.name = name;
this.weight = weight;
}
public String toString(){
return name + "("+weight+")";
}
}
class Apple extends Fruit {
public Apple(String name, int weight) {
super(name, weight);
}
}
class Grape extends Fruit {
public Grape(String name, int weight) {
super(name, weight);
}
}
class AppleComp implements Comparator<Apple> {
@Override
public int compare(Apple o1, Apple o2) {
return o2.weight - o1.weight;
}
}
class GrapeComp implements Comparator<Grape> {
@Override
public int compare(Grape o1, Grape o2) {
return o2.weight - o1.weight;
}
}
class FruitComp implements Comparator<Fruit> {
@Override
public int compare(Fruit o1, Fruit o2) {
return o1.weight - o2.weight;
}
}
public class FruitBoxEx4 {
public static void main(String[] args) {
FruitBox<Apple> appleBox = new FruitBox<Apple>();
FruitBox<Grape> grapeBox = new FruitBox<Grape>();
appleBox.add(new Apple("GreenApple", 300));
appleBox.add(new Apple("GreenApple", 100));
appleBox.add(new Apple("GreenApple", 200));
grapeBox.add(new Grape("GreenGrape", 400));
grapeBox.add(new Grape("GreenGrape", 300));
grapeBox.add(new Grape("GreenGrape", 200));
Collections.sort(appleBox.getList(), new AppleComp()); // 내림차순
Collections.sort(grapeBox.getList(), new GrapeComp()); // 오름차순
System.out.println(appleBox);
System.out.println(grapeBox);
System.out.println();
Collections.sort(appleBox.getList(), new FruitComp()); // 오름차순
Collections.sort(grapeBox.getList(), new FruitComp()); // 오름차순
System.out.println(appleBox);
System.out.println(grapeBox);
}
}
class FruitBox<T extends Fruit> extends Box<T> {}
class Box<T> {
ArrayList<T> list = new ArrayList<>();
void add(T item) {
list.add(item);
}
T get(int i) {
return list.get(i);
}
ArrayList<T> getList(){
return list;
}
int size(){
return list.size();
}
public String toString(){
return list.toString();
}
}
Collections.sort()를 이용해서 appleBox와 grapeBox에 담긴 과일을 무게별로 정렬한다.
static <T> void sort(List<T> list, Comparator<? super T> c)
static 옆에 있는 <T>는 메서드에 선언된 지네릭 타입이다.
이런 메서드를 지네릭 메서드라고 한다.
첫 번째 매개변수 정렬한 대상이고, 두 번째 매개변수는 정렬할 방법이 정의된 Comparator이다.
Comparator의 지네릭 타입에 하한 제한이 걸려있는 와일드 카드가 사용된다.
static <T> void sort(List<T> list, Comparator<T> c)
Part. Algorithm
알고리즘 너어무 소홀히 대했다.
알고리즘도 틈틈히 꾸준히 공부해야한다. 네카라쿠배를 가기위해선 최선을 다하자!
DP
백준 2098 - 외판원 순회
https://www.acmicpc.net/problem/2098
2098번: 외판원 순회
첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j
www.acmicpc.net
TSP 알고리즘
public static int tsp(int now, int visited) {
if (visited == (1 << N) - 1) { // 모든 도시를 지난 경우
// now -> 0(출발도시)로 가는 경로가 존재해야 돌아갈 수 있음
if (W[now][0] == 0) {
return INF;
}
return W[now][0];
}
if (dp[now][visited] != -1) {
return dp[now][visited];
}
dp[now][visited] = INF; // 최솟값은 최댓값부터 시작한다.
for (int i = 0; i < N; i++) {
if ((visited & (1 << i)) == 0 && W[now][i] != 0) { // 방문을하지 않았고, 경로가 존재한다면
dp[now][visited] = Math.min(dp[now][visited], tsp(i, visited | (1 << i)) + W[now][i]);
}
}
return dp[now][visited];
}
tsp 알고리즘을 분석해보자..!
첫번째 조건문이다.
if (visited == (1 << N) - 1) { // 모든 도시를 지난 경우
// now -> 0(출발도시)로 가는 경로가 존재해야 돌아갈 수 있음
if (W[now][0] == 0) {
return INF;
}
return W[now][0];
}
if (visited == (1 << N) - 1)왜 이 로직이 모든 도시를 지난 경우라고 표현이 될까?
N=3이라고, 가정을 할때, 모든 도시를 방문하는 경우의 수는 2(방문o,방문x)*2*2 - 1(전부다 방문하지 않은 경우)로 7이된다.
if (W[now][0] == 0) {
return INF;
}모든 도시를 지난 경우, 출발도시로 다시 돌아가는 경로가 존재해야 돌아갈 수 있다.
W[now][0] 여기서 0은 출발지점을 의미한다.
W[now][0] == 0 이라는 것이 의미하는 것은 다시 돌아가는 경로가 존재하지 않는 것이다.
if (dp[now][visited] != -1) {
return dp[now][visited];
}방문지의 누적된 최적경로가 존재하는 경우 누적된 최적경로의 가중치 값을 반환해준다.
for (int i = 0; i < N; i++) {
// visited는 이미 도시를 방문했는지 여부를 나타내고, and 연산을 했을때, 방문을 하지 않은 경우는 전부 0이 나와야 한다.
if ((visited & (1 << i)) == 0 && W[now][i] != 0) { // 방문을하지 않았고, 경로가 존재한다면
dp[now][visited] = Math.min(dp[now][visited], tsp(i, visited | (1 << i)) + W[now][i]);
}
}모든 도시를 탐색하면서, 방문여부와 경로 존재 여부를 파악해서 최적의 경로를 누적시켜준다.
이분탐색과 LIS
백준 - 용돈 관리
https://www.acmicpc.net/problem/6236
6236번: 용돈 관리
현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로
www.acmicpc.net
3%만 맞고 틀렸다.
언제 완전히 맞을 수 있을까?
내가 놓친 부분은 어디일까..? 다시 확인해보자
1차 풀이
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int M;
public static int answer;
public static int[] money;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
money = new int[N];
for (int i = 0; i < N; i++) {
money[i] = Integer.parseInt(br.readLine());
}
int start = 1;
int end = 10_000;
// 최소 금액을 찾으면 된다.
while (start <= end) {
int mid = (start + end) / 2;
if (check(mid)) {
end = mid - 1;
answer = mid;
} else {
start = mid + 1;
}
}
bw.write(answer + "\n");
bw.flush();
bw.close();
br.close();
}
public static boolean check(int mid) {
int k = 1; // 1번 인출
int value = mid;
for (int i = 0; i < N; i++) {
if (value >= money[i]) {
value -= money[i];
} else {
k++;
value = mid - money[i]; // 인출하고 초기화
}
}
return k <= M; // 돈이 많이 남아돈다 -> 돈의 크기를 줄여야한다.
}
}
찾았다..!
end의 시작 값이 문제였다...!
end의 최대 값은 10,000씩 100,000번이므로 10,000 * 100,000으로 해주어야 한다!
범위를 잘 지켜보자
아래 코드가 더 깔끔하다고 생각한다!
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int M;
public static int answer;
public static int[] money;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
money = new int[N];
int start = 1;
int end = 10_000 * 100_000;
for (int i = 0; i < N; i++) {
money[i] = Integer.parseInt(br.readLine());
start = Math.max(start, money[i]);
}
// 최소 금액을 찾으면 된다.
while (start <= end) {
int mid = (start + end) / 2;
if (check(mid)) {
end = mid - 1;
answer = mid;
} else {
start = mid + 1;
}
}
bw.write(answer + "\n");
bw.flush();
bw.close();
br.close();
}
public static boolean check(int mid) {
int k = 1; // 맨 처음 1번 인출
int value = mid; // 값 초기화
for (int i = 0; i < N; i++) {
if (value - money[i] < 0) {
value = mid;
k++;
}
value -= money[i];
}
return k <= M; // 인출 횟수가 적다 = 돈이 많이 남아돈다 -> 돈의 크기를 줄여야한다.
}
}
DFS & BFS
백준 - 안전 영역
https://www.acmicpc.net/problem/2468
2468번: 안전 영역
재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는
www.acmicpc.net
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[][] map;
public static int[][] initMap;
public static int[][] visited;
public static int answer;
public static int rain = Integer.MIN_VALUE;
public static int[] dy = {-1, 0, 1, 0};
public static int[] dx = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
rain = Math.max(rain, map[i][j]);
}
}
initMap = map.clone();
answer = Integer.MIN_VALUE;
for (int i = 1; i <= rain; i++) { // 1~8
rainDrop(i); // 비와서 잠기는 지역 -1로 초기화
int k = 0;
for (int j = 0; j < N; j++) {
for (int l = 0; l < N; l++) {
if (map[j][l] != -1 && visited[j][l] == 0) {
k++;
bfs(new Node(j, l));
}
}
}
answer = Math.max(answer, k);
map = initMap.clone(); // 맵 초기화
visited = new int[N][N]; // 방문 초기화
}
bw.write(answer + "\n");
bw.flush();
bw.close();
br.close();
}
public static void rainDrop(int rain) { // 주어진 비보다 작은 지역 초기화
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (map[i][j] <= rain) {
map[i][j] = -1;
}
}
}
}
public static void bfs(Node node) {
Queue<Node> queue = new LinkedList<>();
queue.add(node);
visited[node.y][node.x] = 1; // 현재 노드 방문 추가
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (int i = 0; i < 4; i++) {
int ny = cur.y + dy[i];
int nx = cur.x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) {
continue;
}
if (visited[ny][nx] == 0 && map[ny][nx] != -1) {
visited[ny][nx] = 1;
queue.add(new Node(ny, nx));
}
}
}
}
public static class Node {
int y;
int x;
public Node(int y, int x) {
this.y = y;
this.x = x;
}
}
}
아... 69%까지 정답..!
비가 안오는 경우도 고려를 해주어야 하는데.. 고려해주지 않았다.
문제를 똑바로 읽자
정답 풀이 (코드를 좀 더 다듬었다)
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static int[][] map;
public static int[][] visited;
public static int answer;
public static int rain = Integer.MIN_VALUE;
public static int[] dy = {-1, 0, 1, 0};
public static int[] dx = {0, 1, 0, -1};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
map = new int[N][N];
visited = new int[N][N];
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
rain = Math.max(rain, map[i][j]);
}
}
answer = 0;
for (int i = 0; i <= rain; i++) { // 1~8
int k = 0;
for (int j = 0; j < N; j++) {
for (int l = 0; l < N; l++) {
if (map[j][l] > i && visited[j][l] == 0) {
k++;
bfs(new Node(j, l), i);
}
}
}
answer = Math.max(answer, k);
visited = new int[N][N]; // 방문 초기화
}
bw.write(answer + "\n");
bw.flush();
bw.close();
br.close();
}
public static void bfs(Node node, int rain) {
Queue<Node> queue = new LinkedList<>();
queue.add(node);
visited[node.y][node.x] = 1; // 현재 노드 방문 추가
while (!queue.isEmpty()) {
Node cur = queue.poll();
for (int i = 0; i < 4; i++) {
int ny = cur.y + dy[i];
int nx = cur.x + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= N) {
continue;
}
if (visited[ny][nx] == 0 && map[ny][nx] > rain) {
visited[ny][nx] = 1;
queue.add(new Node(ny, nx));
}
}
}
}
public static class Node {
int y;
int x;
public Node(int y, int x) {
this.y = y;
this.x = x;
}
}
}
비가 0인 경우도 추가해주어야 한다.
맞왜틀팁
예제가 잘 출력된다고 해서 제출하지 말자, 반례를 항상 생각하고 코드를 짜고, 제출을 해야한다.
다른 테스트 케이스도 생각을 해야된다.
반례를 구성하는 팁
최소, 최대
없거나, 있거나
변수명의 통일
변수를 만들때 변수명을 통일 해라!
dy, dx
y, x
ny, nx
cnt : 카운팅
ret : 최종 결과물
mx : 최댓값
mn : 최솟값
백준 1931번 - 회의실 배정
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
뭔가 문제를 다시 푼다고 해서 생각하고 푼게 아니라, 무턱대고 기억나는 내용으로 풀었다.
문제를 풀때는 생각하고 풀자! 아무리 다시 푸는 문제라해도 암기해서 푸는 것이 아닌 이해를 바탕으로 풀자..!
문제 풀이
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;
public class Main {
public static int N;
public static List<Node> list;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
N = Integer.parseInt(br.readLine());
list = new ArrayList<>();
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
Node node = new Node(start, end);
list.add(node);
}
Collections.sort(list);
int ret = 1;
int end = list.get(0).end;
for (int i = 1; i < list.size(); i++) {
if (list.get(i).start >= end) {
ret++;
end = list.get(i).end;
}
}
bw.write(ret + "\n");
bw.flush();
bw.close();
br.close();
}
public static class Node implements Comparable<Node> {
int start;
int end;
public Node(int start, int end) {
this.start = start;
this.end = end;
}
@Override
public int compareTo(Node o) {
if (this.end == o.end) {
return this.start - o.start;
}
return this.end - o.end;
}
}
}
백준 2618번 - 경찰차
https://www.acmicpc.net/problem/2618
2618번: 경찰차
첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1 ≤ W ≤ 1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄
www.acmicpc.net
난이도 : 플래티넘4
다익스트라 알고리즘을 사용한다고 생각한다..
다익스트라 알고리즘에 대해 다시 정리해보자!
다익스트라 알고리즘
음의 가중치(음의 간선, 음의 값)가 없는 그래프의 한 노드에서 각 모든 노드까지의 최단거리를 구하는 알고리즘
초기 모델의 시간 복잡도 O(V^2)를 가진다.
이후 우선순위 큐 등을 이용한 고안된 알고리즘으로 인해, O((V+E)logV)의 시간복잡도를 가진다.
음의 가중치를 가지면 안되는 이유
최소 비용의 음의 무한대 발산, 그리디 알고리즘 적용 불가능
알고리즘 매커니즘
- 기본적으로 그리디 알고리즘이자 다이나믹 프로그래밍 기법을 사용한 알고리즘이다.
- 아래 두 단계를 반복하여 임의의 노드에서 각 모든 노드까지의 최단 거리를 구한다.
(1) 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.(그리디 알고리즘)
(2) 해당 노드로부터 갈 수 있는 노드들의 비용을 갱신한다. (다이나믹 프로그래밍)
문제는 내일 푸는 걸로 하자..!
우선 여기까지~!
Part. MySQL
MySQL 8.0
MySQL 서버는 사람의 머리 역할을 담당하는 MySQL 엔진과 손발 역할을 담당하는 스토리지 엔진으로 구분할 수 있다.
4.1 MySQL 엔진 아키텍처
MySQL은 대부분의 프로그래밍 언어로부터 접근 방법을 모두 지원한다.
MySQL 서버는 크게 MySQL 엔진과 스토리지 엔진으로 구분할 수 있다.
MySQL 엔진
클라이언트로부터의 접속 및 쿼리 요청을 처리하는 커넥션 핸들러와 SQL 파서 및 전처리기, 쿼리의 최적화된 실행을 위한 옵티마이저가 중심을 이룬다.
SQL문장을 분석하거나 최적화하는 등 DBMS의 두뇌에 해당한다.
스토리지 엔진
실제 데이터를 디스크 스토리지에 저장하거나 디스크 스토리지로부터 데이터를 읽어오는 부분은 스토리지 엔진이 전담한다.
MySQL 서버에서 MySQL 엔진은 하나지만 스토리지 엔진은 여러 개를 동시에 사용할 수 있다.
create table test_table (fd1, INT, fd2, INT) ENGINE=INNODB;
test_table은 InnoDB 스토리지 엔진을 사용하도록 정의
test_table에 대해 INSERT, UPDATE, DELETE, SELECT, ... 등의 작업이 발생하면 InnoDB 스토리지 엔진이 그러한 처리를 담당한다.
각 스토리지 엔진은 성능 향상을 위해 캐시(MyISAM 스토리지 엔진)나 InnoDB 버퍼 풀(InnoDB 스토리지 엔진)과 같은 기능을 내장하고 있다.
핸들러 API
MySQL 엔진의 쿼리 실행기에서 데이터를 쓰거나 읽어야 할 때는 각 스토리지 엔진에 쓰기 또는 읽기를 요청하는데, 이러한 요청을 핸들러(Handler) 요청이라 하고, 여기서 사용되는 API를 핸들러 API라고 한다.
InnoDB 스토리지 엔진 또한 이 핸들러 API를 이용해 MySQL 엔진과 데이터를 주고 받는다.
MySQL 스레딩 구조
MySQL 서버는 프로세스 기반이 아니라 스레드 기반으로 작동하며, 크게 포그라운드 스레드와 백그라운드 스레드로 구분한다.
포그라운드 스레드(클라이언트 스레드)
최소한 MySQL 서버에서 접속된 클라이언트의 수만큼 존재하며, 주로 각 클라이언트 사용자가 요청하는 쿼리 문장을 처리한다.
클라이언트 사용자가 작업을 마치고 커넥션을 종료하면 해당 커넥션을 담당하던 스레드는 다시 스레드 캐시(Thread cache)로 되돌아간다. 이때 이미 스레드 캐시에 일정 개수 이상의 대기 중인 스레드가 있으면 스레드 캐시에 넣지 않고 스레드를 종료시켜 일정 개수의 스레드만 스레드 캐시에 존재하게 한다. 스래드 캐시에 유지할 수 있는 최대 스레드 개수는 thread_cache_size 시스템 변수로 설정한다.
데이터를 MySQL의 데이터 버퍼나 캐시로부터 가져오며, 버퍼나 캐시에 없는 경우에는 직접 디스크 데이터나 인덱스 파일로부터 데이터를 읽어와서 작업을 처리한다.
MyISAM 테이블은 디스크 쓰기 작업까지 포그라운드 스레드가 처리하지만
InnoDB 테이블은 데이터 버퍼나 캐시까지만 포그라운드 스레드가 처리하고, 나머지 버퍼로부터 디스크까지 기록하는 작업은 백그라운드 스레드가 처리한다.
사용자(클라이언트)와 통신하기 때문에 포그라운드 스레드라고 하며, 사용자가 요청한 작업을 처리하기 때문에
사용자 스레드라고도 한다.
백그라운드 스레드
InnoDB
- 인서트 버퍼(Insert Buffer)를 병합하는 스레드
- 로그를 디스크로 기록하는 스레드
- InnoDB 버퍼 풀의 데이터를 디스크에 기록하는 스레드
- 데이터를 버퍼로 읽어 오는 스레드
- 잠금이나 데드락을 모니터링하는 스레드
가장 중요한 것은 로그 스레드와 버퍼의 데이터를 디스크로 내려쓰는 작업을 처리하는 쓰기 스레드이다.
데이터를 읽는 작업은 주로 클라이언트 스레드에서 처리되기 때문에 읽기 스레드는 많이 설정할 필요가 없다.
사용자의 요청을 처리하는 도중 데이터의 쓰기 작업은 지연(버퍼링)되어 처리될 수 있지만 데이터의 읽기 작업은 절대 지연될 수 없다.
일반적인 상용 DBMS에는 대부분 쓰기 작업을 버퍼링해서 일괄 처리하는 기능이 탑재돼 있으며, InnoDB 또한 이러한 방식으로 처리한다.
MyISAM은 사용자 스레드가 쓰기 작업까지 함께 처리하도록 설계되어 있다. 이러한 이유로 InnoDB에서는 INSERT, UPDATE, DELETE 쿼리로 데이터가 변경되는 경우 데이터가 디스크의 데이터 파일로 완전히 저장될 때 가지 기다리지 않아도 된다.
MyISAM에서 일반적인 쿼리는 쓰기 버퍼링 기능을 사용할 수 없다.
메모리 할당 및 사용 구조
MYSQL에서 사용되는 메모리 공간
(1) 글로벌 메모리 영역
MySQL 서버가 시작되면 운영체제로부터 할당된다.
MySQL의 시스템 변수로 설정해 둔 만큼 운영체제로부터 메모리를 할당받는다.
클라이언트 스레드의 수와 무관하게 하나의 메모리 공간만 할당한다.
필요에 따라 2개 이상의 메모리 공간을 할당받을 수도 있지만 클라이언트의 스레드 수와는 무관하며, 생성된 글로벌 영역이 N개라 하더라도 모든 스레드에 의해 공유된다.
대표적인 글로벌 메모리 영역
- 테이블 캐시
- InnoDB 버퍼 풀
- InnoDB 어댑티브 해시 인덱스
- InnoDB 리두 로그 버퍼
(2) 로컬 메모리 영역
세션 메모리 영역이라고도 표현하며, MySQL 서버상에 존재하는 클라이언트 스레드가 쿼리를 처리하는 데 사용하는 메모리 영역
대표적으로 커넥션 버퍼와 정렬(소트)버퍼 등이 있다.
클라이언트 스레드가 사용하는 메모리 공간이라고 해서 클라이언트 메모리 영역이라고도 한다.
클라이언트와 MySQL 서버와의 커넥션을 세션이라고 하기 때문에 로컬 메모리 영역을 세션 메모리 영역이라고도 표현한다.
로컬 메모리는 각 클라이언트 스레드별로 독립적으로 할당되며 절대 공유되어 사용하지 않는다는 특징이 있다.
로컬 메모리 공간은 커넥션이 열려 있는 동안 계속 할당된 상태로 남아 있는 공간도 있고(커넥션 버퍼, 결과 버퍼) 그렇지 않고
쿼리를 실행하는 순간에만 할당했다가 다시 해제하는 공간(소트 버퍼나 조인 버퍼)도 있다.
대표적인 로컬 메모리 영역
- 정렬 버퍼(Sort Buffer)
- 조인 버퍼
- 바이너리 로그 캐시
- 네트워크 버퍼
Part. IT Infra
책만 한번 봤다.
Part. Project(졸업작품)
Kotlin, Java 코드를 Spring 프로젝트에 적용해보자!
'Backend > 공부 일지' 카테고리의 다른 글
| 2024/04/04(목) (0) | 2024.04.05 |
|---|---|
| 2024/04/03(수) (1) | 2024.04.04 |
| 2024/04/01(월) (0) | 2024.04.01 |
| 2024/03/31(일) (1) | 2024.04.01 |
| 2024/03/30(토) (0) | 2024.03.31 |
