[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: 문법이 간단하다. ..
[JPA] Entity 클래스에서 Setter 메소드의 사용
2023. 4. 9. 15:35
Spring
Entity 클래스를 만들 떄 getter/setter를 무작정 생성하는 경우가 있다. 이렇게 되면 해당 클래스의 인스턴스 값들이 언제 어디서 변해야하는지 코드상으로 명확하게 구분할 수가 없어 차후 기능 변경시 복잡해짐 따라서 Entity클래스에는 Setter메소드의 사용을 지양하고, 많약 해당 필드의 값 변경이 필요하면 명확히 그 목적과 의도를 나타낼 수 있는 메소드를 추가하는 것이 좋다. 예를 들어 주문 취소 메소드를 만든다고 가정해보자 잘못된 예 public clsaa Order{ public void setStatus(boolean status){ //set 메소드 작성 -> 목적과 의도가 명확하지 않다. this.status = status; } } public void 주문서비스의_취소이벤트(..