Develop by May Develop by May

알고리즘

• 섬 개수 세기 - dfs

  알고리즘 2024. 10. 19. 14:23

  이건 dfs, bfs 모두를 이용해서 계산 할 수 있다.제일 기본적인 알고리즘이니 형태를 암기해서 모든 것의 기본으로 활용하자. 메커니즘을 살펴보자.1. map을 돌면서 아직 방문하지 않았고 조건에 맞는 섬을 찾았다.2. 섬 개수에 +1을 해준다.3. 그 좌표(i, j)와 방문 기록(visited)을 dfs나 bfs에 넣어서 연결된 섬은 방문 체크를 한다. 이걸 코드로 구현한 java 코드이다.//dfsimport java.util.*;import java.io.*;public class SafyZone { public static int[] x_move = {1,0,-1,0}; public static int[] y_move = {0,1,0,-1}; public static void dfs(int[..

  Read More
• 프로그래머스 풀이 : 호텔 대실

  알고리즘 2024. 10. 7. 16:10

  import java.util.*;//시간은 시각에 60 곱해서 다 분으로 관리하기! //우선순위 큐//큐에 비는 시간을 넣기//큐에 몇개가 있느냐가 의도class Solution { public int solution(String[][] book_time) { int answer = 1; int[][] newList = new int[book_time.length][2]; Queue queue = new PriorityQueue(); //시간을 분으로 변환 for(int i=0; i(){ @Override public int compare(int[] a, int[] b){ ..

  Read More
• 백준 풀이 : 동전 1 - 2293번

  알고리즘 2024. 10. 6. 18:47

  이 문제는 방법의 수를 구하는 문제로 DP 문제이다.n개의 동전으로 k원을 만드는 방법의 수를 구해야 한다.예제인 n = 3, k = 10, coin = {1, 2, 5}로 설명해보겠다. 처음에 나는 dp[i] = dp[i-1] + dp[i - 2] + dp[i - 5] 이런 식으로 생각했는데 그럼 dp[3] = 2가 말이 되지 않았다. 이 문제는 해당 수를 각 동전으로 만들 수 있는 경우의 수의 합으로 생각하면 된다.해당 수의 모든 경우의 수를 구하고 그걸 다음 계산에 사용하는 것이 아닌,한 동전을 사용해 해당 수를 만드는 경우를 계산한 다음, 그걸 다른 수 계산에 이용해야한다. 즉 dp[3] = dp[2] + dp[1] 이긴 한데, 계산 당시 dp[2] = 1, dp[1] = 1이다.왜냐하면, 이때 ..

  Read More
• [99클럽 코테 스터디 2일차 TIL] JAVA 배열의 최대공약수(gcd), 최소공배수(lcm) 구하기

  알고리즘 2024. 7. 23. 16:14

  //최대공약수public int gcd(int a, int b){ if(a % b == 0){ return b; } return gcd(b, a % b);}//최소공배수public static int lcm(int a, int b) { return a * (b / gcd(a, b));}// 배열의 최대공약수 구하기public static int findArrayGCD(int[] arr) { int result = arr[0]; for (int i = 1; i

  Read More
• dfs java

  알고리즘 2024. 6. 28. 15:30

  여기서 dfs함수는 방법의 수를 리턴public class TargetNumber { public int solution(int[] numbers, int target) { return dfs(numbers, target, 0, 0); } private int dfs(int[] numbers, int target, int index, int currentSum) { // base case: 모든 숫자를 다 사용한 경우 if (index == numbers.length) { // 현재 합이 타겟 넘버와 같으면 1을 반환 (방법의 수 1개 추가) return currentSum == target ? 1 : 0; ..

  Read More
• 정렬

  알고리즘 2024. 4. 4. 20:04

  - String ArrayList 정렬ArrayList list = new ArrayList();list.add("5");list.add("3");Collections.sort(list); Collections.sort(list, new Comparator(){ @Override public int compare(String a, String b){ if(a.compareTo(b) == 0){ return "동일함"; } return a.compareTo(b); }}); - String[ ] 정렬String[] arr = {"a", "b", "c"};Arrays.sort(arr); - int[]를 String[]으로 바꿔서 정렬// int 배열..

  Read More
• 합병 정렬

  알고리즘 2024. 2. 27. 18:25

  합병 정렬(merge sort) 알고리즘 - 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. - 합병 정렬은 다음의 단계들로 이루어진다. - 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. - 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출 을 이용하여 다시 분할 정복 방법을 적용한다. - 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다. - 합병 정렬의 과정 - 추가적인 리스트가 필요하다. - 각 부분 배열을 정렬할 때도 합병 정렬을 순환적으로 호출하여 적용한다. - 합병 정렬에서 실제로 정..

  Read More
• bfs - 너비 우선 탐색

  알고리즘 2024. 2. 20. 17:26

  그래프 탐색이란 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 Ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 너비 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다. 즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다. 사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다. Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우 특징 - 어떤 노..

  Read More