자바127 [백준] 하노이 탑 이동 순서 / 자바 문제 레벨: G5알고리즘: 재귀풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/117291 번째 시도 1. 하노이 탑에 기본 원리가장 큰 원판을 C로 옮기기 위해서는 n-1개의 원판이 A에서 B로 가야한다.Hanoi(n) = 2 × Hanoi(n-1) + 11은 가장 큰 원판이 C로 간 것2 x Hanoi(n-1)은 B로 잠깐 옮겨졌다가 최종 목적지인 C로 옮겨진 걸 뜻함import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException; public class Main { public static StringBuilder sb = new Str.. 2024. 5. 20. 퀵 정렬(Quick Sort) 퀵 정렬의 메커니즘은 크게 다음과 같다.하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법이다.이 부분에서 만약 알고리즘에 대해 잘 알고있다면 '분할 정복(Divide and Conquer)'을 떠올릴 것이다. 병합정렬과의 차이점병합정렬: 하나의 리스트 절반으로 나누어 분할 정복퀵 정렬: 피벗의 따라 나누기 때문에 부분리스트 크기가 다를 수도 있음 퀵 정렬 특징비교 정렬 : 구체적으로 알아보기에 앞서 미리 언급하자면 퀵 정렬은 데이터를 '비교한다.제자리 정렬(in-place sort) : 추가적인 공간을 필요로 하.. 2024. 5. 20. [백준] ACM Craft/자바 문제 레벨: G3알고리즘: 위상정렬 + 최대값 갱신 풀이시간: 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 .. 2024. 5. 16. [백준] 토마토/자바 문제 레벨: 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로 만들기/자바 문제 레벨: S4알고리즘: DP풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/14631 번째 시도 귀여운 수준의 구현이어서 바로 작성해보았다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.parseInt(br.readLine()); int cnt = 0; .. 2024. 5. 9. [백준] 연구소 / 자바 / 브루트포스(그래프 순회) 문제 레벨: G4알고리즘: 브루트포스(그래프 순회)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/145021 번째 시도 벽을 세우는 규칙이 안 보이는 것 같다결국 완전탐색 선택또 하나, 힌트인 것은 입력 값 N,M이 8이하이다. 결국 완전탐색을 해도 된다는 소리이다.깊은 복사 필수!!1. 얕은 복사 : '주소 값'을 복사한다는 의미입니다. 2. 깊은 복사 : '실제 값'을 새로운 메모리 공간에 복사하는 것을 의미하며, dfs로 벽을 세울 경우의 수를 탐색하고 3개의 벽을 세우면 bfs함수 호출하여 바이러스를 퍼트리기바이러스를 퍼트릴 때 원본배열에서 퍼트리는 것이 아니라 얕은 복사를 한 배열에 퍼트린 것이다. import java.io.Bu.. 2024. 5. 8. [백준] 벽 부수고 이동하기/자바 문제 레벨: G3알고리즘: BFS 풀이시간: 1시간 20분힌트 참조 유무: 유https://www.acmicpc.net/problem/22061 번째 시도 벽을 언제 뽀갤 건지 한 번에 알 수 있나?NO근데 왜 dfs가 아니고 bfs 인가?dfs는 최단 경로를 찾는 것이 아니라 끝까지 탐색해서 경로를 찾는 것이기 때문에 첫 번째 도착한 것이 최단경로임을 보장하지 않는다. 최단 경로 찾기에 bfs가 적합하다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.LinkedList;import java.util.Queue;public class Main.. 2024. 5. 7. [백준 1167] 트리의 지름 / 자바 / 트리순회(dfs) 문제 레벨: G2알고리즘: DFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11671 번째 시도 dfs를 통해 임의의 정점 하나에서 가장 먼 정점을 구한다. (임의의 정점은 아무거나 상관없다.)dfs를 통해 구한 정점으로 부터 가장 먼 정점까지의 거리를 구한다. 이게 가장 긴 지름임을 보장하는 이유는 예를 들어 설명하겠다.1 - 2 - 3 - 4 - 5 - 6 이런 일직선의 트리를 생각해보자가장 긴 지름을 구하려면 끝점 두 개를 구해야 한다. 1. 임의점에서 dfs를 하면 끝점 하나가 찾아진다.2. 그 끝점을 기준으로 dfs 하면 다른 끝점이 찾아진다.import java.util.*; public class Main { .. 2024. 5. 6. [백준 10026] 적록색약 / 자바 / 그래프 순회(dfs) 문제 레벨: G2알고리즘: DFS 풀이시간: 30분힌트 참조 유무: 무https://www.acmicpc.net/problem/100261 번째 시도 할 일 배열 초기화적록색맹x 일때 dfs적록색맹o 일때 dfs인접해있는 요소를 비교하는 문제일 때는 방향 설정 배열을 쓰는 것이 Point! static int[] x = {1,0,0,-1}; static int[] y = {0,1,-1,0};dfs함수의 for문과 main함수에서 for문을 짤 때 헷갈릴 수도 있다.dfs함수는 동,서,남,북 방향으로 주어진 글자랑 같은 게 무엇인지 찾는 것이고 main함수의 for문은 전체배열을 순서대로 순회하는 것이다 문제가 카드의 경우의 수를 구하는 경우라면 main함수의 for문은 없을 것이다. .. 2024. 5. 5. 이전 1 ··· 10 11 12 13 14 15 다음
