[Java] 이항계수 /백준 1010, 11051
2023. 5. 1. 02:26
Algorithm
문제 풀 때마다 까먹어서 이항계수를 정리해보려 한다. 이항계수 nCr 은 n개중 r개를 선택하는 경우의 수를 의미하며 n!/r!(n-r!)로 나타낼 수 있다 알고리즘에서 이항계수를 구할 때 팩토리얼로 일일히 이항계수를 구하면 int범위를 벗어나 오버플로우가 발생하는 경우가 많다. 따라서 BigInteger를 이용해줄 수 있지만 보통은 재귀를 이용한다. 재귀를 이용할 때에도 시간초과가 날 수 있기 때문에 dp로 풀어주는 것이 일반적이다. 이항계수에는 중요한 규칙 두 가지가 있다. 1.nCr = n-1Cr + n-1Cr-1 2.nC0 = nCn = 1 이를 증명해보자 {a1,a2,a3....an}의 부분집합 중 원소의 개수가 r인 것의 개수는 nCr이다 여기서 원소의 개수가 r인 경우는 두가지로 나뉠 수 있..
[JAVA] DFS,재귀 이해하기/ 백준 2644 촌수계산
2023. 5. 1. 00:38
Algorithm
나는 DFS로 풀었다 처음에 작성한 코드 public class Baek_2644 { static int[][] family; static boolean[] check; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int A = Integer.parseInt(br.readLine()); StringTokenizer st = new StringTokenizer(br.readLine()," "); int S = Integer.parseInt(st.nextToken()); int E = Integer.parseInt(..
[모듈러 연산] 백준 11726 /프로그래머스 - 피보나치 수
2023. 4. 21. 16:57
Algorithm
문제 자체는 점화식만 구한다면 어렵지 않다. dp[1] = 1 / dp[2] = 2 / dp[3] = dp[2] + 2*dp[1] - dp[1] dp[n] = d[n-1] + dp[n-2] 를 이용하여 재귀로 풀어주었다. 그러나 이렇게만 푸니 틀렸다. 찾아보니 계산하려는 수가 너무 커져 오버플로우가 발생했기 때문이었다. 정수형 데이터의 타입을 사용할 때에는 반드시 자신이 사용하고자 하는 데이터의 최소/최대 크기를 고려해야 한다. 오버플로우 : 해당 타입이 표현할 수 있는 '최대 표현 범위'보다 큰 수를 저장할 때 발생하는 현상 언더플로우 : 해당 타입이 표현할 수 있는 '최소 표현 범위'보다 작은 수를 저장할 때 발생하는 현상 위 문제에서는 '방법의 수를 10,007로 나눈 나머지를 출력' 이라는 문구가..
[Java]Quick Sort
2023. 4. 21. 12:41
Algorithm
merge sort와 마찬가지로 분할 정복 알고리즘(divide and conquer)을 이용한 정렬 방식 divide and conquer 문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결한다. 만약 더이상 나눌 수 없다면 직접 해결한다. 💡퀵정렬 원리 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.(피봇을 선정하는 기준에 따라 다양한 퀵소트 구현 방법이 나올 수 있다.) 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗의 위치는 확정되므로 더 이상 움직이지 않는다. 분할..
[Java]Merge sort
2023. 4. 20. 16:58
Algorithm
divide and conquer 방식으로 정렬! divide and conquer 문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결한다. 만약 더이상 나눌 수 없다면 직접 해결한다 😎병합정렬 원리 예를 들어서 다음과 같은 배열이 있다고 가정하면 이 배열을 계속해서 반으로 나눌 수 있다. 그리곤 각각의 sub 부분들을 비교해서 정렬한다 원소가 하나인 경우는 그 자체로 정렬되어 있으므로 원소 2개의 비교부터 시작한다. [50,100] 배열과 [32,67] 배열을 비교해서 정렬해보자 먼저 각 배열의 첫번째 원소끼리 비교한다. 더 작은 수를 원 배열의 첫번째 인덱스에 넣고 다음 수로 넘어가 비교한다. 1. 50과 32 비교 -> 32가 더 작음 -> 배열에 첫번째 인덱스에 ..
분할 정복 정복하기~
2023. 4. 20. 15:58
Algorithm
1.divide -> 문제를 작은 크기의 서브 문제들로 나눈다. 2.conquer -> 서브 문제(Recursive Case)들을 동일하게 재귀적인 방식으로 해결한다. 만약 문제가 충분히 작아 더이상 나눌 수 없다면(Base Case) 직접 해결한다 3.combine -> sub 문제의 솔루션을 합쳐서 원문제의 솔루션을 만든다 이라는 문제 해결 전략 사용 분할 정복을 이용하는 예시 merge sort, quick sort, binary sort https://develoyummer.tistory.com/75 [Java]Merge sort divide and conquer 방식으로 정렬! divide and conquer 문제를 나눌 수 있을 때까지 나누고 , 서브 문제들을 동일하게 재귀적인 방식으로 해결..
[DP]백준 9095 예제 뿌시기
2023. 4. 14. 16:37
Algorithm
알고리즘을 공부하면서 똑같은 문제도 여러 가지로 풀 수 있다는 것을 느꼈다. 그리고 각 문제마다 효율적인 방법이 있다. 그래서 알고리즘 문제를 풀때 다른 풀이와 내 풀이를 비교하며 어떤게 효율적인지 생각해보는 습관이 좋은 것 같다. 다음 문제는 백준의 9095번 분제 1,2,3더하기라는 문제이다. n이 11보다 작다는 제한이 주어져서 뭔가 메모이제이션을 이용해서 풀면 굉장히 효율적일 것 같았다. 근데 어떻게 풀지 감이 안와서 처음에는 DFS를 이용해서 풀었다. 1. DFS 풀이법 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { static int cou..
DFS / BFS
2023. 4. 14. 14:57
Algorithm
DFS/BFS를 한번에 정리해 보려고 한다. DFS/BFS로 풀기 좋은 대표적 문제 유형 1.경로 탐색(최단거리/시간) 2.네트워크 유형(연결) 3.조합 유형(모든 조합 만들기) DFS (깊이 우선 탐색) 한길로 쭉 가는 유형, 재귀로 구현하는 것이 일반적! 재귀를 타고타고 가서 탈출조건에 도달하고 파라미터를 하나씩 바꿔가면서 정점을 찾는 방식 DFS문제 예 프로그래머스-타겟 넘버 class Solution { static int answer; public int solution(int[] numbers, int target) { answer =0; dfs(0,0,numbers,target); return answer; } static void dfs(int index, int sum, int[]numb..
[mustache]spring boot 프로젝트에 mustache 템플릿 엔진 적용해보기
2023. 4. 10. 14:25
etc
화면을 구성하기 위해 템플릿 엔진 중 mustache를 사용하였다. 템플릿 엔진이란 지정된 템플릿 양식과 데이터가 합쳐져 HTML 문서를 출력하는 소프트웨어를 말한다. 자바 진영에서는 JSP,Velocity,Freemarker,Thymleaf등의 템플릿 엔지니 존재하고 각 템플릿 엔진에는 장단점이 있다. JSP,Velocity : 스프링부트에서는 권장하지 않음 Freemarker: 기능이 많다. 자유도가 높다. 따라서 숙련도가 낮을 수록 Freemarker 안에 비즈니스 로직이 추가될 확률이 높다. Thymleaf: 스프링 진영에서 적극적으로 밀고 있음. 문법이 다소 어려움 . HTML 태그에 속성으로 템플릿 기증을 사용하는 방식이 높은 허들로 느껴지는 경우가 많다. Mustache: 문법이 간단하다. ..