[알고리즘] 4일차

지금까지 봤던 문제들 중에 Boggle 문제가 진짜 어려웠음

 

애초에 이거 이해하기도 어렵고, 여러 가지 알고리즘 다 섞여 있는데

 

이 문제는 내가 나중에 다시 풀라고 해도 못풀듯 엄청 어려웠다

 

 

Boggle 문제 8방...

package day03.P9202;

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

public class Main {
	static final int[] MX = {-1, -1,-1,0,0,0,1,1,1};
	static final int[] MY = {1,0,-1,1,0,-1,1,0,-1};
	static char[][] map; 
	static int[] score = {0,0,0,1,1,2,3,5,11}; 
	static TriNode root = new TriNode();
	
	static int W,N;
	static int sum;
	static String answer;
	static int count;
	static boolean[][] visited;
	static StringBuilder sb = new StringBuilder(); //정답이 긴 경우에 이거 사용
	
	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++) {
			insert(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);
				}
			}
			for (int y = 0; y < 4; y++) {
				for (int x = 0; x < 4; x++) {
					if(root.hasChild(map[y][x])) {
						search(y,x,1,root.getChild(map[y][x]));
					}
				}
			}
		}
	System.out.println(resultSb.toString());
}
	
	
	static void search(int y, int x, int length, TriNode node) {
		//1. 체크인
		visited[y][x] = true;
		sb.append(map[y][x]);
		// 알고리즘 풀 때 자바는 더하기 하면 안돼 
		//2. 목적지인가
		if(node.isWord == true && node.isHit == false) { // 목적지인경우
			node.isHit = true;
			//점수계산
			sum += score[length];
			count++;
			String foundWord = sb.toString();
			if(compare(answer, foundWord) > 0) { // 지금 것이 더 좋다
				answer = foundWord;
			}
			
		}
		//3. 연결된 곳을 순회
		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,length + 1, node.getChild(map[ty][tx]));
				}
			}
			
		}
		
		
		//6. 체크아웃
		visited[y][x] = false;
		sb.deleteCharAt(length - 1);
		
	}
	
	
	static int compare(String a, String b) {
		int result = Integer.compare(a.length(), b.length()); // a와 b의 길이를 비교해서 같다면
		if (result == 0) {
			return a.compareTo(b); // 알파벳 순으로 누가 빠른지 알려줌
		}
		return result;
	}
	
	
	
	static void insert(String word) {
		TriNode current = root;
		for(int i = 0; i < word.length(); i++) {
			if(current.hasChild(word.charAt(i)) == false) {
				current.child[word.charAt(i) - 'A'] = new TriNode();
			}
			current = current.getChild(word.charAt(i));
		} // for문이 끝난거면 word의 끝까지 간것임 (마지막 노드라는 뜻이지)
		current.isWord = true;
	}
}

class TriNode{
	TriNode[] child = new TriNode[26];
	boolean isWord = false;
	boolean isHit = false;
	
	//사전은 하나인데 맵은 여러개라 맵 하나 돌면 그 다음에 isheat 초기화해줘야해
	void clearHit() { // 재귀호출을 이용해서 맵 끝났을 때 clear 구현
		isHit = false;
		for (int i = 0; i < child.length; i++) {
			if(child[i] != null) {
				child[i].clearHit();
			}
		}
	}
	
	//자식을 가지고 있는지?
	boolean hasChild(char c) {
		return child[c-'A'] != null;
	}
	
	TriNode getChild(char c) {
		return child[c-'A'];
	}
}

 

 

유클리드 호제법 ( 최대공약수 하나 빼기)

package day04.P14476;
// 유클리드 호제법 ( 최대공약수 하나 빼기)
public class Main {
	static int N;
	static int[] nums;
	static int[] gcdLtoR;
	static int[] gcdRtoL;
	public static void main(String[] args) {
		gcdLtoR[0] = nums[0];
		for (int i = 0; i < N; i++) {
			gcdLtoR[i] = gcd(gcdLtoR[i-1], nums[i]);
		}
		gcdRtoL[N-1] = nums[N-1];
		for(int i = N-2; i >= 0; i--) {
			gcdRtoL[i] = gcd(gcdRtoL[i+1], nums[i]);
		}

		for (int i = 0; i < N; i++) {
			int gcd = 0;
			if(i == 0) {
				gcd = gcdRtoL[1];
			}else if(i == N-1) {
				gcd = gcdLtoR[N-2];
			}else {
				gcd = gcd(gcdLtoR[i-1], gcdRtoL[i+1]);
			}
		}
		
	}
	
	
	
	// gcd(a,b) = gcd(b, a%b)
	// gcd(a,b) = gcd(b,r) r = a%b
	static int gcd(int a, int b) {
		while(b != 0) {
			int r = a % b;
			a = b;
			b = r;
		}
		return a;
	}
}

 

 

확장 유클리드 호제법

package day04.P3955;

public class Main {
	// X : 인당 나눠줄 사탕의 수
	// Y : 사탕 봉지의 수
	// A * X + 1 = B * Y
	
	// Ax + By + C의 형태로 변환
	//-Ax + By = 1
	
	// A(-x) + By = 1

	static int A,B;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		EGResult result = egcd(A,B);
		
		// D = gcd(A,B)
		// Ax + By = C일 때, C % D == 0 이어야 해를 가질 수 있음 : 배주 항등식
		if(result.r != 1) { //1 % result.r != 0
			//해가 없음
			
		}else {
			//(초기해 설정)
			//x0 = s * C/D
			//y0 = t * C/D
			long x0 = result.s; // C도 1, D도 1이니까 이 문제에서는,,
			long y0 = result.t;
			
			//(일반해 공식으로 일반해 설정)
			// x = x0 + B/D * k
			// y = y0 - A/D * k
			
			
			// x < 0
			// 여기서 D는 1이니까 식의 간소화를 위해 조금 생략했음
			// x0 + B * k < 0
			// k <-x0 / B
			
			// 0 < y <= 1e9
			// 0 < y0 - A * k <= 1e9
			// -y0 < -A * k <= le9 - y0
			// (y0 - le9) / A <= k < y0 / A
			
			// 따라서 합치면 조건
			// (y0 - le9) / A <= k < y0 / A
			//                   k <-x0 / B
			long kFromY = (long)Math.ceil((double)  y0 / (double) A) - 1;
			long kFromX = (long)Math.ceil((double) -x0 / (double) B) - 1;
			long k = Math.min(kFromX, kFromY);
			
			long kLimitFromY = (long) Math.ceil((y0 - 1e9) / (double) A);
			
			if(kLimitFromY <= k) {
				System.out.println(y0 - A * k);
			}else {
				// 범위를 만족하는 해가 없음..
			}
			
		}
		
	}
	
	//As + Bt = r을 만족하는 s,t,r을 찾는 과정
	static EGResult egcd(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; // temp = r0 % r1
			r0 = r1;
			r1 = temp;
			
			//유클리드호재법을 s랑 t로 바꾼 게 확장 유클리드호재법
			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,t,r;

	public EGResult(long s, long t, long r) {
		super();
		this.s = s;
		this.t = t;
		this.r = r;
	}
	
	@Override
	public String toString() {
		return "EGResult [s=" + s + ", t=" + t + ", r=" + r + "]";
	}

	
	
}

 

 

 

 

 

소수 에라토스테스의 체?

이중 for문 돌리면 돼