심플하고 차분하게

|  LocalDate를 활용해 달력 출력하기

- 먼저 구하려는 날짜의 LocalDate를 생성하고, lenthOfMonth()로 그 달의 일수를 구한다.

// 해당 달의 일수 구하기 : lengthOfMonth()
LocalDate date = LocalDate.of(2012,12,1);
int lengthOfMonth = date.lengthOfMonth();

- 해당 월의 1일자가 몇 요일인지, getDayOfWeek().getValue()로 구한다.

int dayOfWeek = date.getDayOfWeek().getValue(); //월화수목.. = 1234..

- 주차를 구하는 방법은 임의로 만들었는데, (전체월 일수 + (7 - 1일자 요일번호))를 7로 나누어 반올림하였다.

int weeksOfMonth = Math.round((lengthOfMonth + (7 - dayOfWeek))/7f);

- 이 세가지를 구한 후, 2차원 배열을 만들고, 1일자의 시작 요일에 맞춰 입력 후, 출력은 이중 for문으로 했다.

- 전체 코드

- 출력 결과  *한글와 숫자깨짐은 무시한 결과다.

[달력 출력 프로그램]
달력의 년도를 입력해 주세요.(yyyy):2022
달력의 월을 입력해 주세요.(mm):7
[2022년 07월]
일 월 화 수 목 금 토  
               01 02 
03 04 05 06 07 08 09 
10 11 12 13 14 15 16 
17 18 19 20 21 22 23 
24 25 26 27 28 29 30

※ EUC-KR과 UTF-8방식에 대하여 

> 확장된 아스키 코드와 유니코드의 역사
- 유니코드 이전에는 각 나라별로 확장된 아스키코드(Extended Ascii)를 사용했다.(아스키 코드의 문자는 1byte)
- 나라별로 인코딩 방식이 상이하다보니 전 세계의 데이터가 모두 다르게 읽히는 문제가 발생했다.
- 이를 해결하고자 유니코드를 만들었다. (유니코드의 문자는 2byte)
- 하지만 유니코드는 영문자의 경우 사용하는 메모리 공간이 1byte -> 2byte가 된다는 단점이 있어,
  영어권 같은 나라에서는 유니코드를 사용하는 것이 큰 메리트가 되지 않았다.
- 그래서 나온 것이 UTF-8. UTF-8은 가변 길이를 제공하여, 각 나라의 언어별로 최적화된 문자 크기를 할당한다.
  ex. 영문자의 경우 1byte, 한글의 경우 3byte

> EUC-KR과 UTF-8. 
- EUC-KR은 유니코드가 나오기 이전에 사용하던 한글 인코딩 방식(Extended Ascii)이다.
  * 자바의 KSC5601기법은 곧 EUC-KR 인코딩을 말하며, 윈도우OS에서 MS949와 동일한 기법을 사용한다.
  * 윈도우의 기본 인코딩 방식은 MS949다. 이클립스를 키면 늘 이 인코딩이 디폴트로 설정되어 있어 UTF-8로 바꾸는게 필요
- EUC-KR을 사용하면 온전한 한글을 만들기가 어렵다. (ex.'뷁' 이라는 문자가 없음)
- 당연한 얘기지만, 인코딩 방식이 EUC-KR일 때, 디코딩을 UTF-8로 하면 문자가 깨지게 된다. (제대로 인식을 못함)
- 그렇기에 항상 에디터를 쓸 때 사전에 인코딩 방식을 UTF-8로 설정을 해두는 것이다.

1. 최소힙 구현하기

import java.util.ArrayList;

class MinHeap{
    ArrayList<Integer> tree;

    public MinHeap(){
        this.tree = new ArrayList<Integer>();
        this.tree.add(0); // dummy data
    }

    // 삽입 : (1) 트리의 가장 뒤에 삽입 (2) 삽입 위치에서부터 부모와 비교
    public void add(int data){
        this.tree.add(data);

        int curIdx = this.tree.size() - 1; // 현재 위치
        int parentIdx = curIdx / 2; // 부모 위치
        while (curIdx > 1 && tree.get(parentIdx) > tree.get(curIdx)) {
            int tmp = tree.get(parentIdx);
            tree.set(parentIdx, tree.get(curIdx));
            tree.set(curIdx, tmp);
            curIdx = curIdx / 2;
        }
    }

    // 삭제 : (1) 루트를 삭제 (2) 루트에 가장 끝 노드를 삽입 (3) 루트에서부터 비교
    public int remove(){

        if (this.tree.size() == 1){
            System.out.println("this heap is empty!");
            return -1;
        }

        // (1)-(2)
        int min = this.tree.get(1);
        int last = this.tree.remove(this.tree.size() - 1);
        this.tree.set(1, last);

        // (3)
        int curIdx = 1;
        while(true){
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx * 2 + 1;
            int childIdx = -1;

            if (rightIdx < this.tree.size()) { // 자식노드가 둘 다 있는 경우
                childIdx = tree.get(leftIdx) < tree.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < this.tree.size()) { // 자식노드가 하나인 경우
                childIdx = leftIdx;
            } else { // 자식이 하나도 없을 때
                break;
            }
            
            if (tree.get(curIdx) < tree.get(childIdx)){
                break;
            } else {
                int tmp = tree.get(curIdx);
                tree.set(curIdx, tree.get(childIdx));
                tree.set(childIdx, tmp);
                curIdx = childIdx;
            }
        }

        return min;
    }
}

2. 최대힙 구현하기

import java.util.ArrayList;

class MaxHeap{
    ArrayList<Integer> tree;

    public MaxHeap(){
        this.tree = new ArrayList<Integer>();
        this.tree.add(0); // dummy data
    }

    // 삽입 : (1) 트리의 가장 뒤에 삽입 (2) 삽입 위치에서부터 부모와 비교
    public void add(int data){
        this.tree.add(data);

        int curIdx = this.tree.size() - 1; // 현재 위치
        int parentIdx = curIdx / 2; // 부모 위치
        while (curIdx > 1 && tree.get(parentIdx) < tree.get(curIdx)) {
            int tmp = tree.get(parentIdx);
            tree.set(parentIdx, tree.get(curIdx));
            tree.set(curIdx, tmp);
            curIdx = curIdx / 2;
        }
    }

    // 삭제 : (1) 루트를 삭제 (2) 루트에 가장 끝 노드를 삽입 (3) 루트에서부터 비교
    public int remove(){

        if (this.tree.size() == 1){
            System.out.println("this heap is empty!");
            return -1;
        }

        // (1)-(2)
        int max = this.tree.get(1);
        int last = this.tree.remove(this.tree.size() - 1);
        this.tree.set(1, last);

        // (3)
        int curIdx = 1;
        while(true){
            int leftIdx = curIdx * 2;
            int rightIdx = curIdx * 2 + 1;
            int childIdx = -1;

            if (rightIdx < this.tree.size()) { // 자식노드가 둘 다 있는 경우
                childIdx = tree.get(leftIdx) > tree.get(rightIdx) ? leftIdx : rightIdx;
            } else if (leftIdx < this.tree.size()) { // 자식노드가 하나인 경우
                childIdx = leftIdx;
            } else { // 자식이 하나도 없을 때
                break;
            }

            if (tree.get(curIdx) > tree.get(childIdx)){
                break;
            } else {
                int tmp = tree.get(curIdx);
                tree.set(curIdx, tree.get(childIdx));
                tree.set(childIdx, tmp);
                curIdx = childIdx;
            }
        }

        return max;
    }
}

1. 배열을 통한 이진트리 순회

// 배열을 통한 이진트리 구현
class BinaryTree{
    char[] arr;
    
    BinaryTree(char[] data){
    	this.arr = data;
    }
    
    public void preOrer(int idx){      
        System.out.print(arr[idx] + " ");
        
        int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < this.arr.length){
        	preOrder(left);
        }
        
        if (right < this.arr.length){
            preOrder(right);
        }
    }
    
    public void inOrder(int idx){
    	int left = 2 * idx + 1;
        int right = 2 * idx + 2;
        
        if (left < arr.length){
           inOrder(left);
        }
        
        System.out.print(arr[idx] + " ");
        
        if (right < arr.lenght){
           inOrder(right);
        }
    }
    
    public void postOrder(int idx){
    	int left = idx * 2 + 1;
        int right = idx * 2 + 2;
        
        if (left < arr.length) {
           postOrder(left);
        }
        
        if (right < arr.length) {
           postOrder(right);
        }
        
        System.out.print(arr[idx] + " ");
    }
    
    public void levelOrder(int idx){
    	for (int i = idx; i < arr.length; i++){
        	System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
}

public class Main{
   public static void main(String[] args){
      BinaryTree bt = new BinaryTree(new char[]{'A','B','C','D','E','F','G'});
      //     A
      //   B   C
      //  D E F G
   }
}

2. 연결리스트를 통한 이진트리 순회

// 노드의 연결(연결리스트)을 통한 이진트리 구현
class Node{
    char data;
    Node left;
    Node right;
    
    Node(char data){
    	this.data = data;
    }
}

class BinaryTree{
    Node root;
    
    BinaryTree(char[] datas){
    	Node nodes[] = new Node[datas.length];
    
        // 각각의 노드를 생성
    	for (int i = 0; i < datas.length; i++){
        	nodes[i] = new Node(datas[i]);
        }
        
        // 트리 형태로 노드를 연결
        root = nodes[0];
        for (int i = 0; i < nodes.length; i++){
        	int left = i * 2 + 1;
            int right = i * 2 + 2;
            
            nodes[i].left = nodes[left];
            nodes[i].right = nodes[right];
        }
    }
    
    public void preOrder(Node node){
    	if (node == null) {
        	return;
        }
        
        preOrder(node.left);
        System.out.print(node.data + " ");
        preOrder(node.right);
    }
    
    public void inOrder(Node node){
    	if (node == null) {
        	return;
        }
    
    	inOrder(node.left);
        System.out.print(node.data + " ");
        inOrder(node.right);
    }
    
    public void postOrder(Node node){
    	if (node == null){
        	return;
        }
        
        postOrder(node.left);
        postOrder(node.right);
        System.out.print(node.data + " ");
    }
    
    public void levelOrder(Node node){
    	Queue<Node> queue = new LinkedList();
        queue.add(node);
        
        while (!queue.isEmpty()){
			Node cur = queue.poll();
            System.out.print(cur.data + " ");
            
            if (cur.left != null) {
            	queue.offer(cur.left);
            }
            
            if (cur.right != null) {
            	queue.offer(cur.right);
            }
        }
    }
}

public class Main{
   public static void main(String[] args){
      BinaryTree bt = new BinaryTree(new char[]{'A','B','C','D','E','F','G'});
      //     A
      //   B   C
      //  D E F G
   }
}

3. 가중치가 있는 포화이진트리의 루트~리프까지의 가중치 총합을 동일하게 만드는 최소합

BinaryTree{
    int h; //높이
    int sum; //가중치의합
    int[] w; //가중치 배열
    
    BinaryTree(int h, int[] w){
    	this.h = h;
        this.w = new int[(int)(Math.pow(2, (h+1)))];
        
        for (int i = 2; i < this.w.length; i++){
        	this.w[i] = w[i-2];
        }
    }
    
    // 하위 좌우 중 더 큰 가중치에 맞춘 후 -> 상위 좌우 중 더 큰 가중치 합에 맞춘다.
    public int dfs(int h, int idx){
    	if (h == this.h){
        	res += this.w[idx]; //리프 가중치 추가
        	return this.w[idx];
        }
        
        int leftW = dfs(h + 1, idx * 2 + 1); // 좌측 서브 트리의 가중치 합
        int rightW = dfs(h + 1, idx * 2 + 2); // 우측 서브 트리의 가중치 합
        res += this.w[idx] + Math.abs(leftW - rightW); 
        return this.w[idx] + Math.max(leftW, rightW); // 서브 트리에서 더 큰 가중치 합 반환
    }
}

public class Main{

	public static void solution(int h, int[] w) {
    	BinaryTree bt = new BinaryTree(h, w);
		bt.dfs(0, 1);
        System.out.println(bt.res);
    }

	public static void main(String[] args){
    	int h = 2;
        int[] w = new int[]{1, 1, 2, 1, 3, 1};
        solution(h, w);
    }
}

 * 여기서의 탐색은 루트에서부터의 탐색으로, 이진 탐색 트리를 실제로 조회할 때는 4가지 순회 중 하나를 선택하는 것이 더 유리하다.(ex. preOrder/InOrder/....)

class Node{
    int key;
    Node left;
    Node right;
    
    Node(int key, Node left, Node right){
    	this.key = key;
        this.left = left;
        this.right = right;
    }
}

class BinarySearchTree{

    Node root;
	
    BinatySearchTree(int key){
    	this.root = new Node(key, null, null);
    }
    
    // 삽입
    public void add(int key){
    	if (root == null){
        	root = new Node(key, null, null);
        } else {
        	Node cur = this.root;
            Node pre = cur;
            
            while (cur != null) {
            	pre = cur;
            
            	if (key < cur.key){
                	cur = cur.left;
                    
                    if (cur == null){
                    	pre.left = new Node(key, null, null);
                        break;
                    }
                }
                
                if (key > cur.key){
                	cur = cur.right;
                    
                    if (cur == null) {
                    	pre.right = new Node(key, null, null);
                        break;
                    }
                }
            }
        }
    }
    
    // 삭제
    public void remove(int key){
    	// 탐색 (해당 key값을 가진 노드 탐색)
        Node cur = this.root;
        Node parent = null;
        
        while (cur != null){
        	if (cur.key == key){
            	break;
            }
            
            parent = cur;
            if (key < cur.key) {
            	cur = cur.left;
            } else {
            	cur = cur.right;
            }
        }
        
        if (cur == null){ //없을 때
        	System.out.println("BinarySearchTree doesn't have key " + key);
        }
        
        // 세가지 case에 따라 삭제 진행
        Node child = null;
        Node leftRightMax = null;
        Node ex;
        
        // case 1 : 삭제 노드가 leaf 일 때
        if (cur.left == null && cur.right == null){
        	if (cur == this.root){
            	this.root = null;
            } else {
            	if (parent.left == cur){
                	parent.left = null;
                } else {
                	parent.right = null;
                }
            }
        } 
        // case 2 : 삭제 노드에 자식이 하나 있을 때
        else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null) {
        	// 자식 위치를 먼저 확인
            if (cur.left != null) {
            	child = cur.left;
            } else {
            	child = cur.right;
            }
            
            // 자식 노드를 현재 위치로 올린다.
            if (parent == null){ // = cur 가 root
            	this.root = child;
            } else {
            	if (parent.left == cur){
                    parent.left = child;
                } else {
                    parent.right = child;
                }
            }
        }
        // case 3 : 삭제 노드에 자식이 둘 있을 때
        else {
        	// 나의 좌측 노드 중 가장 큰 노드를 찾는다.
            ex = cur;
            leftRightMax = cur.left;
            
            while (now.right != null){
            	ex = leftRightMax;
            	leftRightMax = leftRightMax.right;
            }
            
            // 나의 위치에 찾은 노드를 넣어준다.
            ex.right = leftRightMax.left; // 먼저, 찾은 노드에 좌측노드가 있는 경우
            leftRightMax.left = cur.left;
            leftRightMax.right = cur.right;
            
            if (parent == null){
            	this.root = leftRightMax;
            } else {
            	if (parent.left == cur) {
                	parent.left = leftRightMax;
                } else {
                	parent.right = leftRightMax;
                }
            }
        }
    }
    
}

ext2_inode 구조

• i_blocks: 파일이 몇 개의 데이터 블록을 가지고 있는지 나타냄.
• i_mode: 이 inode가 관리하는 파일의 속성 및 접근 제어 정보 유지
• i_links_count: 이 inode를 가리키고 있는 파일 수(또는 링크 수)를 의미. (파일 이름 -- inode)
• i_uid, i_gid: 파일을 생성한 소유자의 userID, groupID 의미.
• i_atime, i_ctime, imtime: 파일의 접근 시간, 생성 시간, 수정 시간 의미.
• i_block[15]: 파일에 속한 디스크 블록들의 위치를 관리.

[ 출처 ] https://velog.io/@jinh2352/inode-%EA%B5%AC%EC%A1%B0