Hayden's Archive

알고리즘 문제 출처 : 백준 - 15988번 : 1, 2, 3 더하기 3 https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 내가 작성한 코드 import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); long[] check = new long[1000001]; check[1] = 1; check[2..

알고리즘 문제 출처 : 백준 - 11053번 : 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 내가 작성한 코드 다이나믹 프로그래밍 말고 다른 방법으로 풀어볼 수 있을 것 같아서 도전했다가 실패하고 결국 다이나믹 프로그래밍으로 풀었다. 먼저 check에 1씩 할당해야 한다.(어느 수이든 1가지 방법 이상이기 때문) 앞에 있는 numArr..

알고리즘 문제 출처) 백준 1463번 : 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 내가 작성한 코드 Bottom-Up 방식(반복문으로 구현) import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] record = new int[n+1]; for(int i=2; irecord[i/2]+1) { record[i] = record[..

백준 11005번 : 진법 변환 2 알고리즘 문제 출처 : https://www.acmicpc.net/problem/11005 11005번: 진법 변환 2 10진법 수 N이 주어진다. 이 수를 B진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 �� www.acmicpc.net 내가 작성한 코드 10진법 수 N을 B진법으로 바꾸려면 N이 0이 될 때까지 나머지를 계속해서 구하면 된다. import java.util.Scanner; public class Main { public static StringBuilder change(int n, int b) { StringBuilder sb = new Str..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/17087 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이� www.acmicpc.net 내가 작성한 코드 수빈이와 동생들과의 거리의 절대값들을 각각 구한 뒤 그 값들의 최대공약수를 구해주면 된다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static lon..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 내가 작성한 코드 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long factorial = 1; int n = sc.nextInt(); for(int i=2; i

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 내가 작성한 코드 import java.util.Scanner; public class Main { public static boolean prime(int a) { if(a==1) {//1인 경우 return false; } for(int i=2; i*i

알고리즘 문제 출처 : https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 내가 작성한 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static int gcd(int a, int b) { //최대공약수 if(b==0) { re..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이�� www.acmicpc.net 관련 문제 포스팅 : https://hayden-archive.tistory.com/276 내가 작성한 코드 후위 표기식 문제를 풀고 풀었더니 쉽게 풀 수 있었던 문제. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식�� www.acmicpc.net 관련 알고리즘 : 차량기지 알고리즘 https://ko.wikipedia.org/wiki/%EC%B0%A8%EB%9F%89%EA%B8%B0%EC%A7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 정답 비율 30.790%를 자랑하는 문제. 생각지도 못한 반례에서 계속 부딪혀서 9번만에 정답을 맞혔다... 후위표기식 문제에서 나올 수 있는..