그 외 알고리즘 팁들 (java)

Mendel·2024년 5월 24일

Java 알고리즘 팁

알고리즘

목록 보기

59/85

우선, 이 글은 제가 나중에 다시 보기 위해 작성한 것이라서 그렇게 읽기 편하지 않으실 수 있습니다. 나중에 다시 기회가 되면 정리하겠습니다....

비트 연산자

현대 소프티어 코테 중 비트 연산자를 써야 쉽게 풀리는 문제가 나왔다. C언어 말고 자바에서는 처음 써봐서 여기에 정리한다. 사용법은 사실 똑같다.

9&1 -> 1이다. 9&8 -> 8이다. 9&2 -> 0, 9&4 -> 0
| or 연산을 통해 합치는 것이 가능하다. 이는 비트마스크에서 또 나온다.
9|2 -> 11이다. 9|8 -> 그대로 9다.
^ XOR연산이다.
Integer.toBinaryString()을 쓰면 쉽게 이진수로 변환이 가능하다.
"<<" 왼쪽으로 밀어버리는 것으로 N<<1은 2*N이 된다.
나중에 2에 대한 제곱수가 필요할때, 1<<10 하면 2^10이다. 물론, Math.pow(2,10) 으로 구할 수도 있다.
">>" 오른쪽으로 밀어버리는 연산, 왼쪽의 빈자리는 기존의 MST 비트와 같은 값으로 채워진다.
">>>" 오른쪽으로 밀지만, 왼쪽의 빈자리를 항상 0으로 채운다.

비트 마스크

dp에서 많은 데이터를 미리 계산해서 저장하기 위해 쓰인다고 한다. (아직 그런 dp문제를 만나본 적은 없다.)
집합 표시하는 것은 나중에 다시 정리하자.

제곱근 연산자로 아리스토테스의 체 쓰기

Math.sqrt(16) -> 4.0 이다.
이걸 활용해서 아리스토테네스의 체를 작성하자.
i=2부터, (int)Math.sqrt(N)까지 수행하면 된다.

    static void primes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        for (int i = 2; i <= (int) Math.sqrt(n); i++) {
            if (!isPrime[i]) continue;
            System.out.println(i);
            for (int k = i * 2; k <= n; k += i) {
                isPrime[k] = false;
            }
        }
        
        // 뒤에꺼 마저 살아남은 애들 소수 출력
        for (int i = (int) Math.sqrt(n) + 1; i <= n; i++) {
            if (isPrime[i]) System.out.println(i);
        }
    }

이진탐색으로 lowerBound, upperBound 구하기

이 알고리즘은 LIS 알고리즘 구현할때도 쓰이고 구현 문제에서도 쓰일 수 있으니 알아두면 좋다.
https://innovation123.tistory.com/65

핵심은, min=0, max=arr.length 로 설정해서 그 안에 있는 어떤 값보다도 큰 경우는 arr.length 인덱스 자리에 새롭게 추가될 수 있도록 max=arr.length로 잡아야 한다는 것.
그리고, 둘 다 target과 arr[mid]를 비교할 때 등호는 붙이지 않는다. 그리고, min = mid+1 로, max = mid로 이동시키고,
반환은 lowerBound는 mid반환, upperBound는 mid-1 반환한다.

위상정렬

인접리스트를 먼저 만든다.
fan-in 정보를 관리할 배열도 따로 있어야 함.
그냥 fan-in이 0인 시작 노드를 찾고, 그 시작노드부터 큐에 담아서 큐가 빌때까지 계속 돌린다.
매 턴마다 방문한 노드의 인접리스트를 방문하며 그 노드들의 fan-in을 1씩 감소시키고(현재 노드를 처리했으므로) 새롭게 0이 됐다면 다시 큐에 넣는다.
이걸 반복하면 자연스럽게 위상 정렬 결과가 나온다.

자릿수 별로 따로 추출해서 배열로 변환하기

생각보다 기업 코테에서 자주 출제되는 유형이다.
Stack을 사용해서 맨 뒷자리 수부터 스택에 넣고, 나중에 꺼낼때 스택의 성질인 역순을 활용해서 꺼내면서 배열에 넣는다.

중위 표기법을 후위 표기법으로 변환하기

후위 표기법으로 변환하면 컴퓨터가 연산하기 편하다는 장점이 있다. 하지만 이 알고리즘은 기업용 코테에선 자주 등장하지 않는다.
https://todaycode.tistory.com/73

간단하게 정하면 다음과 같다.

해당 알고리즘은 () 괄호가 없는 중위 연산자에 대한 알고리즘이다.

숫자면 바로 출력

연산자면 스택에 넣을건데, 만약 스택의 top연산자보다 이번 연산자가 우선순위가 더 크면 (+보다 *가 우선순위가 더 높다),스택에 그냥 넣는다. 만약 그게 아니라면 스택에서 제거하고 출력한다 계속(while문으로).

마지막에 스택에 남은 모든 연산자를 출력하면 끝난다.

만약 괄호가 있는 중위 연산자를 후위연산자로 바꾸려는 것이면, 아래의 두 가지 규칙이 더 추가된다.

여는 괄호는 바로 스택에 넣는다. 혹은 여는 괄호가 스택의 top이면 다음 연산자는 바로 스택에 넣는다.

닫는 괄호가 나오면 여는 괄호가 나올때까지 스택에서 꺼내서 출력한다.