삼성 SDS 대학생 알고리즘 특강 4일차 - 트라이 트리, 정수론

트리의 응용 - 트라이

 

 

9202: Boggle

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static int[] mx = {-1, 1, 0, 0, -1, 1, -1, 1};
    static int[] my = {0, 0, -1, 1, -1, -1, 1, 1};
    static int[] score = {0, 0, 0, 1, 1, 2, 3, 5, 11};

    static int W, N;
    static char[][] map;
    static boolean[][] visited;
    static String answer;
    static int sum;
    static int count;
    static StringBuilder sb = new StringBuilder();
    static TrieNode root = new TrieNode();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        W = Integer.parseInt(br.readLine());

        for (int i = 0; i < W; i++) {
            insertTireNode(br.readLine());
        }

        br.readLine();
        N = Integer.parseInt(br.readLine());
        StringBuilder resultSb = new StringBuilder();
        for (int n = 0; n < N; n++) {
            map = new char[4][4];
            visited = new boolean[4][4];
            answer = "";
            sum = 0;
            count = 0;
            sb = new StringBuilder();

            for (int i = 0; i < 4; i++) {
                String in = br.readLine();
                for (int k = 0; k < 4; k++) {
                    map[i][k] = in.charAt(k);
                }
            }
            br.readLine();
            for (int y = 0; y < 4; y++) {
                for (int x = 0; x < 4; x++) {
                    //출발 가능 조건 -> root가 해당 child를 가지면
                    if (root.hasChild(map[y][x])) {
                        search(y, x, root.getChild(map[y][x]));
                    }
                }
            }
            //결과 출력
            root.clearHit();
        }
        System.out.println(resultSb.toString());

    }

    static void search(int y, int x, TrieNode node) {
        // 1. 체크인 -> visited
        visited[y][x] = true;
        sb.append(map[y][x]);
        // 2. 목적지에 도달하였는가? -> isWord == true, isHit == false
        if (node.isWord == true && node.isHit == false) {
            node.isHit = true;
            //답 작업 -> 길이, 단어
            String foundWord = sb.toString();
            int length = foundWord.length();
        }
        // 3. 연결된 곳을 순회 -> 8방
        for (int i = 0; i < 8; i++) {
            int ty = y + my[i];
            int tx = x + mx[i];
            // 4. 가능한가? - map경계, 방문하지 않았는지, node가 해당 자식을 가지고 있는지
            if (0 <= ty && ty < 4 && 0 <= tx && tx < 4) {
                if (visited[ty][tx] == false && node.hasChild(map[ty][tx])) {
                    // 5. 간다
                    search(ty, tx, node.getChild(map[ty][tx]));
                }
            }
        }
        // 6. 체크아웃
        visited[y][x] = false;
        sb.deleteCharAt(sb.length() - 1);
    }

    static void insertTireNode(String word) {
        TrieNode current = root;
        for (int i = 0; i < word.length(); i++) {
            char a = word.charAt(i);
            int index = a - 'A';
            if (current.chlid[index] == null) {
                current.chlid[index] = new TrieNode();
            }
            current = current.chlid[index];
        }
        current.isWord = true;
    }
}

class TrieNode {
    boolean isWord = false;
    boolean isHit = false;
    TrieNode[] chlid = new TrieNode[26];

    void clearHit() {
        isHit = false;
        for (int i = 0; i < chlid.length; i++) {
            if (chlid[i] != null) {
                chlid[i].clearHit();
            }
        }
    }

    boolean hasChild(char c) {
        return chlid[c - 'A'] != null;
    }

    TrieNode getChild(char c) {
        return chlid[c - 'A'];
    }
}

 

 

정수론

유클리드 호제법 - 최대공약수

유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘.

2개의 자연수 a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (단 a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

//기억할 것
gcd(a,b) == gcd(b,r) == gcd(b, a%b), stop when a % b == 0

 

gcd(a,b) = gcd(b, a%b)

gcd(36, 24)
 = gcd(24, 12)
 = gcd(12, 0)
 //최대공약수: 12

 

14476: 최대공약수 하나 빼기

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int N;
    static int[] nums;
    static int[] gcdLtoR;
    static int[] gcdRtoL;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        gcdLtoR = new int[N];
        gcdRtoL = new int[N];
        nums = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        for(int i=0; i<N; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }

        //LtoR 만들기
        gcdLtoR[0] = nums[0];
        for (int i = 1; i < N; i++) {
            gcdLtoR[i] = gcd(gcdLtoR[i - 1], nums[i]);
        }
        //RtoL 만들기
        gcdRtoL[N - 1] = nums[N - 1];
        for (int i = N - 2; i >= 0; i--) {
            gcdRtoL[i] = gcd(gcdRtoL[i + 1], nums[i]);
        }

        //k 선정하기
        int max = 0;
        int maxIndex = 0;
        for (int i = 0; i < N; i++) {
            int gcd = 0;
            // 0
            if (i == 0) {
                gcd = gcdRtoL[1];
            }
            // N - 1
            else if (i == N - 1) {
                gcd = gcdLtoR[N - 2];
            }
            // 중간
            else {
                gcd = gcd(gcdLtoR[i - 1], gcdRtoL[i + 1]);
            }
            if (nums[i] % gcd != 0 && gcd > max) {
                max = gcd;
                maxIndex = i;
            }
        }

        if(max ==0)
            System.out.println(-1);
        else{
            System.out.println(max + " "+ nums[maxIndex]);
        }
    }

        //gcd(a,b) == gcd(b,r) == gcd(b, a%b), stop when a % b == 0
        static int gcd(int a, int b) {
            while(b != 0){
                int r = a % b;
                a = b;
                b = r;
            }
            return a;
    }
}

확장 유클리드 호제법 - 방정식의 해

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

    static int N, A, B;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        // X : 인당 나눠줄 사탕의 수
        // Y : 사탕 봉지의 수
        // A * x + 1 = B * y
        // Ax + By = C 의 형태로 변환.
        // -Ax + By = 1
        // A(-x) + By = 1 의 형태로 변환
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            A = Integer.parseInt(st.nextToken());
            B = Integer.parseInt(st.nextToken());
            // 1. 해 검증
            // D = gcd(A, B) = egcd(A, B).r
            // Ax + By = C 일때 C % D == 0 이어야 해를 가질 수 있음 : 베주 항등식
            // C % D != 0 -> 해가 없음
            EGResult result = extendedGcd(A, B);
            if (result.r != 1) {
                System.out.println("IMPOSSIBLE");
            } else {
                // 2. 초기 해 구하기
                // x0 = s * C / D
                // y0 = t * C / D
                long x0 = result.s;
                long y0 = result.t;

                // 3. 일반해 구하기
                // x = x0 + B / D * k
                // y = y0 - A / D * k

                //while  <- k ->

                // 4. k의 범위
                // x < 0
                // x0 + B * k < 0
                // k < - x0 / B

                // 0 < y <= 1e9
                // 0 < y0 - A * k <= 1e9
                // -y0 < -A * k <= 1e9 - y0
                // ( y0 - 1e9 ) / A <= k < y0 / A

                // ( y0 - 1e9 ) / A <= k < y0 / A
                //                     k < - x0 / B

                // 5. 만족하는 k가 있는지 찾고 k를 통해 y를 구한다.
                long kFromY = (long) Math.ceil((double) y0 / (double) A) - 1;
                long kFromX = (long) Math.ceil((double) -x0 / (double) B) - 1;
                long k = Math.min(kFromY, kFromX);
                long kLimitFromY = (long) Math.ceil((y0 - 1e9) / (double) A);
                if (kLimitFromY <= k) {
                    System.out.println(y0 - A * k);
                } else {
                    System.out.println("IMPOSSIBLE");
                }
            }

        }
    }

    static EGResult extendedGcd(long a, long b) {
        long s0 = 1, t0 = 0, r0 = a;
        long s1 = 0, t1 = 1, r1 = b;

        long temp;
        while (r1 != 0) {
            long q = r0 / r1;

            temp = r0 - q * r1;
            r0 = r1;
            r1 = temp;

            temp = s0 - q * s1;
            s0 = s1;
            s1 = temp;

            temp = t0 - q * t1;
            t0 = t1;
            t1 = temp;
        }
        return new EGResult(s0, t0, r0);
    }
}

class EGResult {
    long s;
    long t;
    long r;

    public EGResult(long s, long t, long r) {
        super();
        this.s = s;
        this.t = t;
        this.r = r;
    }

    @Override
    public String toString() {
        return "ExtendedGcdResult [s=" + s + ", t=" + t + ", gcd=" + r + "]";
    }

}

 

에라토스테네스의 체 - 소수

1837- 암호제작

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static int MAX = 1000000;
    static int K;
    static char[] P;
    static boolean[] isNotPrime;
    static List<Integer> primes = new ArrayList<>();

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        //나머지 연산을 위해 입력값을 문자 형태로 변환하여 배열에 저장.
        P = st.nextToken().toCharArray();
        K = Integer.parseInt(st.nextToken());

        isNotPrime = new boolean[MAX + 1];

        //소수연산
        for(int i=2; i< MAX + 1; i++){
            if(isNotPrime[i] == false){
                primes.add(i);
                for(int j=i*2; j<MAX+1; j+=i){
                    isNotPrime[j] = true;
                }
            }
        }

        for(int prime: primes){
            if(prime >= K){
                break;
            }
            if(checkIsBad(prime)){
                System.out.println("BAD "+ prime);
                return;
            }
        }
        System.out.println("GOOD");
    }

    static boolean checkIsBad(int x){
        int ret = 0;
        for(int i=0; i< P.length; i++){
            ret = (ret*10 + (P[i] - '0')) % x;
        }
        if(ret ==0){
            return true;
        } else {
            return false;
        }
    }
}