전체 글
무지했던 지난 날에 대한 속죄의 기록
-
https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 이 문제는 dp (동적계획법) 을 사용하고 함수는 기존의 함수를 그대로 사용하면 된다. 규칙이 있나 찾아보다가 재밌는 규칙을 찾아내서 그것도 사용해 보았다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; publi..
(JAVA) 백준 9148번 : 신나는 함수 실행https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 이 문제는 dp (동적계획법) 을 사용하고 함수는 기존의 함수를 그대로 사용하면 된다. 규칙이 있나 찾아보다가 재밌는 규칙을 찾아내서 그것도 사용해 보았다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; publi..
2022.11.25 -
https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 이번 문제는 해당 함수의 재귀가 얼마나 이루어지는 지에 대한 수를 구하는 문제이다. 풀이는 아래와 같다. 소스코드 1 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { static int N1 = 0; static int N2 = 0..
(JAVA) 백준 24416번 : 알고리즘 수업 - 피보나치 수 1https://www.acmicpc.net/problem/24416 24416번: 알고리즘 수업 - 피보나치 수 1 오늘도 서준이는 동적 프로그래밍 수업 조교를 하고 있다. 아빠가 수업한 내용을 학생들이 잘 이해했는지 문제를 통해서 확인해보자. 오늘은 n의 피보나치 수를 재귀호출과 동적 프로그래밍 www.acmicpc.net 이번 문제는 해당 함수의 재귀가 얼마나 이루어지는 지에 대한 수를 구하는 문제이다. 풀이는 아래와 같다. 소스코드 1 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { static int N1 = 0; static int N2 = 0..
2022.11.24 -
https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 이번 문제는 nCr 을 DP를 이용하여 구한 후, 누적합을 구하는 방식으로 풀이했다가 메모리 에러가 발생하여 밑의 글을 참고하여 풀이를 진행하였습니다. 항상 잘 보고 있습니다 : ) https://st-lab.tistory.com/166 [백준] 2004번 : 조합 0의 개수 - JAVA [자바] www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠..
(JAVA) 백준 2004번 : 조합 0의 개수https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 이번 문제는 nCr 을 DP를 이용하여 구한 후, 누적합을 구하는 방식으로 풀이했다가 메모리 에러가 발생하여 밑의 글을 참고하여 풀이를 진행하였습니다. 항상 잘 보고 있습니다 : ) https://st-lab.tistory.com/166 [백준] 2004번 : 조합 0의 개수 - JAVA [자바] www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠..
2022.11.18 -
https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 기본적으로 수의 범위가 1 - 500 의 팩토리얼을 구해야 하다 보니 팩토리얼을 구해 계산하기 보다는 어떠한 규칙이 있는 지 확인을 먼저 해보았다. 직접 팩토리얼을 계산하면서 진행하다가 보니 0이 늘어나는 경우의 수는 팩토리얼을 진행해야 하는 수의 소인수 분해를 했을 때 2 X 5 의 경우가 N개 있을 때마다 0의 자릿수가 N개임을 확인할 수 있었다. 모든 수의 경우에 2의 제곱 수가 5의 제곱 수보다 많음을 확인하여 해당 수의 5의 제곱에 대한 누적 수를 구하는 방식으로..
(JAVA) 백준 1676번 : 팩토리얼 0의 개수https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 기본적으로 수의 범위가 1 - 500 의 팩토리얼을 구해야 하다 보니 팩토리얼을 구해 계산하기 보다는 어떠한 규칙이 있는 지 확인을 먼저 해보았다. 직접 팩토리얼을 계산하면서 진행하다가 보니 0이 늘어나는 경우의 수는 팩토리얼을 진행해야 하는 수의 소인수 분해를 했을 때 2 X 5 의 경우가 N개 있을 때마다 0의 자릿수가 N개임을 확인할 수 있었다. 모든 수의 경우에 2의 제곱 수가 5의 제곱 수보다 많음을 확인하여 해당 수의 5의 제곱에 대한 누적 수를 구하는 방식으로..
2022.11.15 -
https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 이번 문제는 의상의 종류에 대한 조합 문제이다. hat headgear sunglasses eyewear turban headgear 위와 같은 경우엔 headgear : hat, turban & eyewear : sunglasses 로 2개 ,1개에 대한 조합이다. 하지만 하나만 착용하는 경우가 있기 때..
(JAVA) 백준 9375번 : 패션왕 신해빈https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 이번 문제는 의상의 종류에 대한 조합 문제이다. hat headgear sunglasses eyewear turban headgear 위와 같은 경우엔 headgear : hat, turban & eyewear : sunglasses 로 2개 ,1개에 대한 조합이다. 하지만 하나만 착용하는 경우가 있기 때..
2022.11.15 -
https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 이 문제도 전에 풀었던 이항 계수 1, nCr 을 구하는 풀이와 같다. 이번에도 동적계획법 DP 를 이용하여 풀이를 구했다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { s..
(JAVA) 백준 1010번 : 다리 놓기https://www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 이 문제도 전에 풀었던 이항 계수 1, nCr 을 구하는 풀이와 같다. 이번에도 동적계획법 DP 를 이용하여 풀이를 구했다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main { s..
2022.11.14 -
https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net nCr 을 구하는 문제인데 첫 풀이로 노가다 방식으로 진행해봤다. 이번 문제와 같이 수의 범위가 크지 않다면 문제가 없지만 비효율적이고 코드도 예쁘지 않다고 생각하여 총 3가지 풀이로 진행해봤다. 가장 기본적인 풀이 (row) import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; import java.util.Stri..
(JAVA) 백준 11050번 : 이항 계수 1https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net nCr 을 구하는 문제인데 첫 풀이로 노가다 방식으로 진행해봤다. 이번 문제와 같이 수의 범위가 크지 않다면 문제가 없지만 비효율적이고 코드도 예쁘지 않다고 생각하여 총 3가지 풀이로 진행해봤다. 가장 기본적인 풀이 (row) import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; import java.util.Stri..
2022.11.14 -
https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 서로 다른 부분 문자열의 갯수를 구하는 문제이다 보니 중복 제거가 필요하다 생각하여 HashSet 을 사용해야 한다고 생각했다. 또한 부분 문자열이 필요하니 String.subString() 을 사용했다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashSet; public class Main { pub..
(JAVA) 백준 11478번 : 서로 다른 부분 문자열의 개수https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 서로 다른 부분 문자열의 갯수를 구하는 문제이다 보니 중복 제거가 필요하다 생각하여 HashSet 을 사용해야 한다고 생각했다. 또한 부분 문자열이 필요하니 String.subString() 을 사용했다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashSet; public class Main { pub..
2022.11.11