Mintaka's log

...찾아보니 무차별 공격이라고도 나오는데, 그것 말고. 알고리즘에서 쓰이는 브루트 포스에 관함. 브루트 포스란? Brute force. 발생하는 모든 경우를 무식하게 탐색한다는 뜻. 즉, 가능한 모든 경우의 수를 탐색하기 때문에 정답만을 출력한다고 한다. 종류에는 1. 선형 구조를 전체적으로 탐색 : 순차탐색 2. 비선형 구조를 전체적으로 탐색 : 깊이 우선 탐색(DFS, Depth First Search), 너비 우선 탐색(BFS, Breadth First Search), 백트래킹 장단점 간단하다. 모든 경우를 전부 탐색하므로 장점 정확한 정답을 얻을 수 있음 알고리즘을 설계하고 구현하기 쉬움. 단점 메모리 비효율적 시간이 오래 걸림 예시 비선형 구조에 대한 예시는 각각 dfs, bfs, 백트래킹 글..

유클리드 호제법이란 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘. 이 때 호제법이란, 두 수가 서로 상대방를 나눠서 원하는 수를 얻는 알고리즘을 의미한다. 즉, 큰 수의 경우 일반적으로 알고있는 소인수분해를 하기 번거로운데 이 때 사용할 수 있는 방법이라고 볼 수 있겠다. 위키백과에 설명은 이렇게 되어 있다. 2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (단, a.>b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 대강 설명해보자면 a라는 자연수를 b..

피보나치라는 것만 알면 간단! 그런데 피보나치라는 걸 몰라서 헤맸다..... s(n) 을 2xn 크기의 직사각형을 채우는 방법의 수라고 정의하면, s(n-1)의 형태에다가 오른쪽에 1x2 타일을 붙이는 경우가 포함되는 걸 알 수 있다. 따라서 s(n) = s(n-1) + ? 이 때 ?의 형태들을 잘 보면, 2x1 타일이 두개 붙은 것이 가장 오른쪽에 들어가있다. 즉, s(n-1)에서 1x2 타일이 항상 가장 오른쪽을 차지하고 있었다면 나머지 경우의 수들은 2x1 타일이 항상 가장 오른쪽을 차지하고 있다. 즉, ? = s(n-2). 따라서 s(n) = s(n-1) + s(n-2) 어차피 n이 되기 전 모든 값들을 계산해야 할테니 memoization을 해도 생략할만한 계산이 없다. 따라서 tabulatio..

아무리해도 어떤 식으로 풀어야 할 지 모르겠다가, (dp 기초문제라는데ㅠㅜㅠㅜㅠㅜㅠㅜ) 일단 모든 경우를 다 따져보는 코드를 먼저 작성해보라는 것과, 상태를 정한 다음 풀이하라는 걸 보고 다음식으로 짜보았다. >>어떻게 풀지 참고한 블로그 https://zzonglove.tistory.com/13 동적계획법 (Dynamic Programming) 는 어떻게 풀까? 이 포스팅은 Nitish Kumar 의 기사를 참고하여 만들었습니다. [출처] 동적계획법 (Dynamic Programming), DP 는 다항(Polynomial)한 시간안에 특정 문제를 풀기위한 기술입니다. DP 를 이용한 솔루션은 지수형태 zzonglove.tistory.com import java.io.BufferedReader; imp..

https://www.acmicpc.net/problem/10991 10991번: 별 찍기 - 16 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int num = br.read()-'0'; StringBuilder sb = new Str..

https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 배열을 써서 한 번 풀어봤다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] arg..

https://www.acmicpc.net/problem/1924 1924번: 2007년 첫째 줄에 빈 칸을 사이에 두고 x(1 ≤ x ≤ 12)와 y(1 ≤ y ≤ 31)이 주어진다. 참고로 2007년에는 1, 3, 5, 7, 8, 10, 12월은 31일까지, 4, 6, 9, 11월은 30일까지, 2월은 28일까지 있다. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static void main(String[] args) throws IOExcept..

Scanner의 nextInt( ) 는 숫자 입력 후 구분하기 위해 입력하는 엔터를 제거하지 않는다. 즉, 엔터를 nextLine( )의 입력으로 받아들이게 된다. 에러코드 public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int val = sc.nextInt(); for(int i = 0; i 1. nextLine 써주기 전에 nextLine 한 번 더 써줘서 엔터 버리기. public class M..

https://www.acmicpc.net/problem/10951 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 종료시점을 명확히 해주지 않아 NoSuchElement 에러남. Scanner를 사용했는데 데이터가 하나가 들어왔을 때가 있어서 발생했다고 떴다. ==>hasNextInt( ) 를 사용해서 종료시점 알 수 있도록 해줬다. 다른 코드를 보다보니 더 짧은 시간이 걸리는게 있었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; pub..

https://www.acmicpc.net/problem/10950 10950번: A+B - 3 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 별거아닌데 Scanner에 space입력했을 때는 엔터와 달리 숫자 입력이 안되는줄 알았다. 그런데 되더라. 다음은 자바 API 문서 Scanner 관련 항목 A Scanner breaks its input into tokens using a delimiter pattern, which by default matches whitespace.