알고리즘90 [백준] 2048(Easy) / 자바(feat 브루트 포스, 백트래킹, DFS 차이점) 문제 레벨: G2알고리즘: 브루트 포스풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/121001 번째 시도 [사고 과정]이 게임의 규칙을 못 찾겠다.최대 N= 20 최대 탐색횟수 5번, 20*20*5 =2,000이므로 완전탐색이 가능할 것 같다.5번의 완전탐색으로 구현 자! 그렇다면 어느 것을 기준으로 탐색해야 할까?각각의 숫자들을 타겟 or 방향각각의 숫자들을 초점에 맞추어 방향을 바꾸어 본다면 다른 숫자들도 영향을 받기 때문에 머리가 너무 아프다당연히 4가지로만 나누어진 방향에 초점을 맞추는 게 맞다!(이번 기회를 통해 어는 것의 초점을 맞추어 탐색할지 중요할 것을 알았다) [구현 할 때 힘든 점]스크롤한 후 배열의 결과를 구현하기가.. 2024. 5. 23. [백준] 별 찍기 -10 / 자바 문제 레벨: G5알고리즘: 풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/24471 번째 시도 [풀이 사고 과정]처음 주어진 패턴으로 부분요소들을 크게 업데이트 해가는 문제구나 라는 생각즉, 재귀함수 문제라 생각풀이는 코드 주석 참조import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); .. 2024. 5. 23. [백준] 치킨배달/ 자바** 문제 레벨: G5알고리즘: DFS+조합 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/15686 1 번째 시도 여느 BFS 문제랑 같다 생각하고 작성하였다import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.LinkedList;import java.util.Queue;import java.util.Set;//String[] s = br.readLine().split(" ");//Integer.parseInt(br.readLine());//int N = Inte.. 2024. 5. 21. 정렬 생각 흐름 Arrays.sort() 시도안되면 Collections.sort() 시도퀵 정렬 시도 정렬 방식시간 복잡도Arrays.sort()DualPivotQuicksort평균 : O(nlog(n)) / 최악 : O(n^2)Collections.sort()TimeSort (삽입정렬과 합병정렬을 결합한 정렬)평균, 최악 : O(nlog(n)) 2024. 5. 20. 퀵 정렬(Quick Sort) 퀵 정렬의 메커니즘은 크게 다음과 같다.하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.이 부분에서 만약 알고리즘에 대해 잘 알고있다면 '분할 정복(Divide and Conquer)'을 떠올릴 것이다. 병합정렬과의 차이점병합정렬: 하나의 리스트 절반으로 나누어 분할 정복퀵 정렬: 피벗의 따라 나누기 때문에 부분리스트 크기가 다를 수도 있음 퀵 정렬 특징비교 정렬 : 구체적으로 알아보기에 앞서 미리 언급하자면 퀵 정렬은 데이터를 '비교한다.제자리 정렬(in-place sort) : 추가적인 공간을 필요로 하.. 2024. 5. 20. [백준] LCS/자바 문제 레벨: G4알고리즘: DP풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/92511 번째 시도 import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str1 = br.readLine().toCharArray(); char[] str2 .. 2024. 5. 20. [백준] ACM Craft/자바 문제 레벨: G3알고리즘: 위상정렬 + DP 풀이시간: 2시간힌트 참조 유무: 유https://www.acmicpc.net/problem/10051 번째 시도 입력을 받을 때마다 해당번호의 짓는 시간을 업데이트를 해줬다.결과는 실패이유는 입력 순서가 차례대로일거라고 가정했기 때문이다.import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.. 2024. 5. 16. [백준] 내리막길/자바 문제 레벨: G4알고리즘: DFS + DP 풀이시간: 40분 힌트 참조 유무: 유https://www.acmicpc.net/problem/15201 번째 시도 1. 먼저 (0,0) 위치에서 시작하므로 dp[0][0]값을 0으로 초기화한다.2. (0,0) 위치에서 상하좌우로 이동하면서 map[x][y] > map[nx][ny]인 위치에 대해서만 DFS 메소드를 재귀호출3. 재귀호출을 통해 (M-1, N-1)위치에 도달하는 경로의 개수를 찾는다.4. 이렇게 찾은 경로의 개수를 dp[0][0] 값에 더해준다.5. 모든 이동 가능한 위치에 대해 위 과정을 반복6. dp[0][0] 값이 결정되면 해당 값을 리턴한다.위와 같은 과정을 거쳐서 dp[0][0] 값을 찾게 된다. 만약 dp[0][0].. 2024. 5. 13. [백준] 토마토/자바 문제 레벨: G5알고리즘: BFS풀이시간: 2시간힌트 참조 유무: 유https://www.acmicpc.net/problem/7569 1 번째 시도 기존 bfs와 다른 점은 하나인 줄 알았다. 방향이 상,하가 추가 되서 총 6개를 탐색해야 된다는 점이다 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.PriorityQueue;import java.util.Queue;public class Main { static int[] xx; static int[] yy; public stat.. 2024. 5. 12. 이전 1 2 3 4 5 6 7 ··· 10 다음
