[알고리즘] 정렬 : 정렬(Sorting)이란 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 것. 알고리즘 학습의 필수이고 대표적으로 버블, 선택, 삽입이 있다. # 버블정렬 : 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘 배열의 전체를 순회하면서 앞, 뒤의 데이터를 비교후 Collections.swap으로 자리를 바꿔준다. swap 여부를 체크하며 없을 경우 더 이상 비교할 필요가 없다고 간주하여 해당 루프를 종료한다. [버블정렬] - 구현 예시코드 import java.util.ArrayList; import java.util.Collections; public class BubbleSort { public ArrayList ..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 이번 문제를 읽는데 무슨 내용인지 이해가 되지 않아 애를 먹었었다. 정리하자면 첫번째에서 RED 에서 골랐으면 두번째에선 RED를 제외한 BLUE OR GREEN 을 선택하고 세번째에선 나머지를 고르고, 이러한 경우 중 최소값을 고르면 되는 문제이다. 풀이는 아래와 같다. # Process import java.io.BufferedReader; import java.io.In..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 이번 문제는 동적 계획법과 피보나치 수열의 응용 버전이라고 생각하면 편하다. 이번 문제는 4번째 값부터 한칸 뒤의 두 수의 합과 같다. 즉, dp[i] = dp[i-2] + dp[i-3] 으로 표현할 수 있다. 풀이는 아래와 같다. 소스코드 import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException..

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..

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..

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 ≠..

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의 제곱에 대한 누적 수를 구하는 방식으로..

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개에 대한 조합이다. 하지만 하나만 착용하는 경우가 있기 때..