jayyhkwon의 개발공부로그
Algorithm 브루트포스
20 Jan 2020 |브루트 포스
브루트 포스
-
단순 무식하게 모든 경우의 수를 다 구해보는 방법
-
방법의 갯수가 많지 않을 때 사용하는 방법
문제풀이
- 문제의 가능한 경우의 수를 계산해본다
- 가능한 모든 방법을 다 만들어 본다
- 각각의 방법을 이용해 답을 구해본다
시간복잡도
- O(경우의 수 * 걸리는 시간/개)
브루트 포스
단순 무식하게 모든 경우의 수를 다 구해보는 방법
방법의 갯수가 많지 않을 때 사용하는 방법
문제풀이
시간복잡도
package BOJ._0119;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BOJ_1309 {
static int[][] answer;
static int mod = 9901;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
answer = new int[n + 1][3];
solve(n);
}
private static void solve(int n) {
answer[1][0] = 1;
answer[1][1] = 1;
answer[1][2] = 1;
for(int i=2; i<=n; i++){
answer[i][0] = answer[i-1][0]%mod + answer[i-1][1]%mod + answer[i-1][2]%mod;
answer[i][1] = answer[i-1][0]%mod + answer[i-1][2]%mod;
answer[i][2] = answer[i-1][0]%mod + answer[i-1][1]%mod;
}
System.out.println((Arrays.stream(answer[n]).sum())%mod);
}
}
package BOJ._0119;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class BOJ_11057 {
static int[][] number;
static int mod = 10_007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
number = new int[n+1][10];
solve(n);
}
private static void solve(int n) {
number[1][0]=1;
number[1][1]=1;
number[1][2]=1;
number[1][3]=1;
number[1][4]=1;
number[1][5]=1;
number[1][6]=1;
number[1][7]=1;
number[1][8]=1;
number[1][9]=1;
for(int i=2; i<=n; i++){
for(int j=0; j<10; j++){
for(int k=j; k<10; k++){
number[i][j] += (number[i-1][k])%mod;
}
}
}
System.out.println((Arrays.stream(number[n]).sum())%mod);
}
}
package BOJ.DP;
import java.util.Arrays;
import java.util.Scanner;
public class BOJ_11055 {
static int[] number;
static int[] answer;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = Integer.parseInt(sc.nextLine());
number = new int[n + 1];
answer = new int[n + 1];
for (int i = 1; i <= n; i++) {
number[i] = Integer.parseInt(sc.next());
}
solve(n);
System.out.println(Arrays.stream(answer).max().getAsInt());
}
private static void solve(int n) {
for(int i=1; i<=n; i++){
answer[i] = number[i];
for(int j=1; j<i; j++){
if(number[j] < number[i] && answer[i] < answer[j] + number[i])
answer[i] = answer[j] + number[i];
}
}
}
}
volatile은 변수의 가시성을 보장한다
Java volatile 키워드는 멀티스레딩 환경에서 사용되는 변수의 변화(값의 변화) 에 대한 가시성을 보장한다. 이 말이 좀 추상 적으로 느껴질 수 있는데 자세하게 설명하자면 non-volatile 변수들로 운영되는 멀티 쓰레드 어플리케이션에서 각 쓰레드들은 성능적인 이유로 메인 메모리로 부터 변수를 읽어 CPU 캐시에 복사하고 작업하게 된다. 만약 컴퓨터에 하나 이상의 CPU로 구성되어 있다면 각 쓰레드들이 서로 다른 CPU에서 실행 될수 있다. 이 말은 각 쓰레드들이 서로 다른 CPU들의 CPU 캐시에 값을 복사할 수 있다는 것으로 아래의 다이어그램이 이를 설명해주고 있다.
non-volatile 변수들은 어느 시점에 Java Virtual Machine(JVM)이 메인 메모리로 부터 데이터를 읽어 CPU 캐시로 읽어 들이거나 혹은 CPU 캐시들에서 메인 메모리로 데이터를 쓰는지(write) 보장해 줄 수 없다.
volatile 키워드는 언제 사용하는 가?
가장 최신의 값을 보장한다2개의 스레드가 하나의 객체를 공유하는 경우를 생각해보자.
public static class StoppableTask {
private boolean pleaseStop;
public void run() {
while (!pleaseStop) {
// do some stuff...
System.out.println("running");
}
}
public void tellMeToStop() {
pleaseStop = true;
}
}
public static void main(String[] args){
StoppableTask task = new StoppableTask();
new Thread(() -> task.run()).start(); // 별도의 스레드에서 run() 호출
task.tellMeToStop(); // main thread에서 호출
}
예제를 하나 더 보자. 싱글턴 패턴 중 DCL을 이용하여 구현한 코드이다
// DCL
public class MyBrokenFactory {
private static MyFactory instance;
private int field1, field2 ...
public static MyBrokenFactory getFactory() {
1 if (instance == null) {
2 synchronized (MyBrokenFactory.class) {
3 if (instance == null)
4 instance = new MyBrokenFactory();
}
}
return instance;
}
private MyBrokenFactory() {
field1 = ...
field2 = ...
}
}
instance = new MyBrokenFactory();
// jvm이 리오더링(컴파일시 위치최적화)하여 다음과 같이 코드가 변경될 수 있다
// 1) space = MyBrokenFactory를 할당하기 위한 공간
// 2) instance = space
// 3) space = new MyBrokenFactory();
ref. 블로그
ref. https://www.javamex.com/tutorials/double_checked_locking.shtml