요즘 읽고 있는 책 ( 미래를 바꾼 아홉 가지 알고리즘 )

미래를 바꾼 아홉가지 알고리즘

2년전에 한번 도서관에서 빌렸었는데 다시 빌렸다.
대여기간이 11월 18일까지인데 지금 챕터 2개를 읽었음.
- 오류 정정 코드
  - 반복 기법
  - redundant 기법
  - checkSum 기법

- 데이터 압축
  - 비손실 압축
    - 여기서는 공짜 점심이라고 표현한다.
    - hamming code , zip등 압축전과 압축후가 동일
  - 손실압축
    - JPEG가 대표적인 예
    - 압축을 하고 복구를 하게 되면 전과 후가 다름



18일전까지 꾸준히 읽어야 겠다.

palindrome

• DP가 약하기도하고 공부도 하고 내용도 복습할겸 정리합니다.
• 기본에서 true 와 false말고 숫자로 표현하면 응용이 가능하다.
• 참고 링크 https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/

dp 문제를 푸는 나름대로의 방법

• DP 에서 row와 column에 어떤값을 정확하게 넣어야 할지가 분명하게 서지 않을때 그림을 그리는것은 도움이 된다.

문제

• 여러개의 특정 포지션에서 해당 substring이 palindrome인지 체크 하는 로직을 만드세요
• left = 시작 지점 right = 끝 지점
• ex) str = “abad”

풀이

• T = true, F = false로 간주한다.
• table[left][right]에 대한 값을 담을 수 있는 table을 만들고 값을 채워나간다.
• left == right 같을때는 T 로 셋팅
• left != right
  • left +1 <= right-1 ( size가 3이상인 경우)
    • str[left] == str[right] && table[left+1][right-1] 인경우 table[left][right] T 셋팅
  • left +1 > right-1 ( size 가 2인경우 )
    • str[left] == str[right] 인 경우 table[left][right] T 셋팅

사이즈가 1인경우

사이즈가 2이고 left = 0, right =1 인경우

사이즈가 3이고 left = 0 right =2 인경우

코드

String s = "abac";
boolean[][] table = new boolean[s.length()][s.length()];
for(int i=0; i<s.length(); i++){
    table[i][i] = true;
}
for(int size=2; size<s.length(); size++){
    for(int left=0; left<s.length(); left++){
        int right= left+size-1;
        if(right >= s.length()){
            continue;
        }
        if( size == 2){
            table[left][right] = s.charAt(left) == s.charAt(right);
        }else{
            table[left][right] = s.charAt(left) == s.charAt(right) && table[left+1][right-1];
        }
    }
}

Async Await 사용할때 3가지만 알면 모든게 해결됨

1. async function은 promise 를 리턴함
2. promise는 then이나  await 로 기다림
3. await는 async 안에서만 사용한다.

575. distribute candies

https://leetcode.com/problems/distribute-candies/

• 처음 생각해낸 방법은
  두개의 priority qeue 를 생성해서 하나는 asc, 하는 desc 로 생성
  sister 가 asc에서 한개씩 빼고, brother가 desc에서 큰 순으로 하나씩 빼다보면 최대 개수가 나올것 같다고 생각이 들었음.

• 코딩하기 귀찮아서 다른 방법 생각해보니 유니크한 사탕의 종류의 개수에 따라서 간단히 풀수 있었음.

• O(N)

• 종류개수 > length/2 return length/2, else 종류개수

Runtime: 14 ms, faster than 96.34% of Java online submissions for Distribute Candies.

class Solution {
    public int distributeCandies(int[] candies) {
        int [] map = new int[200001];
        int kinds = 0;
        for(int i=0; i<candies.length; i++){
            if(map[candies[i]+100000] == 0){
                kinds ++;
            }
            map[candies[i]+100000]++;
        }
        int maxLen = candies.length/2 ;
        return kinds <= maxLen ? kinds : maxLen;
    }
}

53. Maximum Subarray

https://leetcode.com/problems/maximum-subarray/

Runtime: 1 ms, faster than 85.87% of Java online submissions for Maximum Subarray.

O(N) 코드

class Solution {
    public int maxSubArray(int[] nums) {
        
        int max = nums[0];
        int pre = nums[0];
        for(int i=1; i<nums.length; i++){
            if(pre >0){
                pre += nums[i];
                max = Math.max(pre, max);
            }else{
                pre = nums[i];
                max = Math.max(pre, max);
            }
        }
        return max;
    }
}

Divide and Conquer

2ms

• ide 사용하고 debugging하는데 시간이 오래 걸림
• 2개또는 1개로 자른다.
• 데이터를 머지할때 3가지 데이터를 구한다
  • leftMost = 왼쪽 0번째 인덱스 부터 시작해서 가장 큰 sum을 구한다.
  • rightMost = 오른쪽 0번째 인덱스부터 왼쪽으로 가장 큰 sum을 구한다.
  • full 은 머지한전체 sum, leftMost와 rightMost를 구하기 위해서 필요함.

public class Solution {

    int max =0;
    int[] nums ;
    public int maxSubArray(int[] nums) {
        max = nums[0];
        this.nums = nums;
        divideAndConquer(0, nums.length-1);

        return max;
    }

    public Data divideAndConquer(int start, int end){
        Data data = new Data();
        if(start == end){
            data.full = nums[start];
            data.leftMost = nums[start];
            data.rightMost = nums[start];
            max = Math.max(max ,data.full);
            return data;
        }else if (start == end-1){
            data.full = nums[start] + nums[end];
            data.leftMost = Math.max(nums[start], nums[start] + nums[end]);
            data.rightMost = Math.max(nums[end], nums[start] + nums[end]);
            max = Math.max(max ,data.leftMost);
            max = Math.max(max ,data.rightMost);
            return data;
        }
        int mid = (end-start)/2 + start;
        // left
        Data left = divideAndConquer(start, mid);

        // right
        Data right = divideAndConquer(mid+1 ,end);
            
        if(left.rightMost >0 || right.leftMost >0){
            max = Math.max((Math.max(left.rightMost, 0) + Math.max(right.leftMost, 0)), max);
        }
        
        data.leftMost = Math.max(left.leftMost, left.full + right.leftMost);
        data.rightMost = Math.max(right.rightMost, right.full + left.rightMost);
        data.full = right.full + left.full;
        max = Math.max(max, data.leftMost);
        max = Math.max(max, data.rightMost);
        max = Math.max(max, data.full);
        return data;
    }

  
}

class Data {
    int leftMost;
    int full;
    int rightMost;
}

1009. Complement of Base 10 Integer

https://leetcode.com/problems/complement-of-base-10-integer/

첫번째 방법

• 2 로 나누기 비트연산하면서 0 to 1 , 1 to 0으로 변경한 비트 값을 더해줌
  2번째 방법
• digit을 구한후 해당 xor 연산으로 한번에 풀었음

Runtime: 0 ms, faster than 100.00% of Java online submissions for Complement of Base 10 Integer.

class Solution {
    public int bitwiseComplement(int N) {
        if(N==0){
            return 1;
        }
        
        int digit = 0;
        int sum =0;
        while (N> 0){
            int remainder = N % 2 ;
            N = N>>1;
            if(remainder == 0 ){
                sum += 1<< digit;
            }
            digit++;            
        }
       
        return sum;
    }
}

두번째 코드

class Solution {
    public int bitwiseComplement(int N) {
        int digit =1;
        int n = N;
        while((n= n >> 1) > 0){
            digit++;
        }
        
        int compare = (2 << digit-1) -1;
        return N^compare;        
    }
}

java shift 연산

Shift 연산

• bit 연산은
• 16진수? int를 표현하는 방법
• 아래 예제는 전부다 16을 출력

  int a = 0x010;
  System.out.println(a);
  a = 0x0010;
  System.out.println(a);
  a = 0x0000010;
  System.out.println(a);
  a = 0x000000000000000000000000000000000000000010;
  System.out.println(a);

• 16진수를 표현하는 방법?
  • 0x에 0 to f 까지 표현할수 있다. (0 -15)

<< number , >> number 연산자

• 비트값을 왼쪽으로 number만큼 움직여준다.

int a = 8;
System.out.println(Integer.toBinaryString(a));
// 001000
a = a << 2;
System.out.println(Integer.toBinaryString(a));
// 100000
a = a >> 2;
System.out.println(Integer.toBinaryString(a));
// 001000

• 1을 오른쪽으로 비트 연산하게 되는경우 어떻게 나올까??

int a = 1;
System.out.println(Integer.toBinaryString(a));
// 00001
a = a >> 5;
System.out.println(Integer.toBinaryString(a));
// 0

• 으로나온다.