백준50 [백준] 수 찾기 / 자바 문제 레벨: S4알고리즘: 이분 탐색풀이시간: 10:29힌트 참조 유무:https://www.acmicpc.net/problem/19201 번째 시도 import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.Arrays;import java.util.StringTokenizer; public class Main { public static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inp.. 2024. 6. 2. [백준] 숫자 찾기 / 자바 문제 레벨: 알고리즘: 이분탐색풀이시간: 40분힌트 참조 유무: 유https://www.acmicpc.net/problem/10816 1 번째 시도 [upper-bound, lower-bound 차이]lower bound, 즉 하한은 찾고자 하는 값 이상의 값이 처음으로 나타나는 위치를 의미한다. upper bound, 즉 상한은 찾고자 하는 값을 초과한 값을 처음 만나는 위치다. 중복 원소에 대한 길이 = (상한 - 하한) mport java.util.Arrays;import java.util.StringTokenizer;import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException.. 2024. 6. 1. [백준] 공유기 설치 / 자바 문제 레벨: G4알고리즘: 이분탐색 풀이시간: 1시간힌트 참조 유무: 무https://www.acmicpc.net/problem/21101 번째 시도 만약, 이 문제를 풀이하기 전에 이분탐색에 대해 조금이나마 헷갈리는 부분이 있다면 필자가 풀이한 숫자카드 2 문제를 한 번 보고 오시는 것을 추천드린다.자카드 2 문제에서 다루었던 Upper Bound, Lower Bound 형식을 그대로 적용시키면서 최대한 코드 재사용성을 높이고자 같은 구조를 띄도록 노력하고 있다. import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;import java.util.StringTokenizer; i.. 2024. 5. 31. [백준] 감시 / 자바 문제 레벨: G3알고리즘: 완전탐색 풀이시간: 1:30힌트 참조 유무: 무https://www.acmicpc.net/problem/156831 번째 시도: 실패 [알고리즘 선택 과정]각 cctv마다 방향 설정이 중요합니다그렇다면 각 cctv의 방향을 무슨 기준으로 놓아야 할까요주장: 각 CCTV마다 칸을 많이 차지하는 방향으로 반론: A가 칸이 많이 차지하는 방향, B가 칸이 많이 차지하는 방향으로 설정했는데 A,B가 겹치는 것이 많은 상황을 가장해보자.(주장 답안)0 0 #0 0 2(A)0 0 #0 0 2(B)0 0 #(정답 답안)0 0 0# # 2(A)0 0 0# # 2(B)0 0 0 그래서 이 주장은 옳지 않습니다. 패스그렇다면 완전탐색으로 각 CCTV의 모든 방향마다 확인해.. 2024. 5. 30. [백준] 가장 긴 증가하는 부분 수열 2 / 자바 ** 문제 레벨: G2알고리즘: 이분탐색풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/120151 번째 시도 [ LIS (Longest Increasing Subsequence) 란]어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열이다.LIS를 구할 때는 DP를 사용한다.LIS의 길이를 구할 때는 이분 탐색(O(nlogn))을 사용한다. DP(O(n^2))로 길이를 구할 시 시간초과가 난다[알고리즘 설명]*이 알고리즘은 고정된 사고를 달리해서 이해해야 합니다*핵심 아이디어: 길이가 동일한 증가 부분 수열 중에서 마지막 값이 작은 것을 유지합니다.지금부터 배열을 순회하면 LIS를 찾아보도록 하겠습니다.수열 A가.. 2024. 5. 29. [백준] 최단경로 / 자바 문제 레벨: G4알고리즘: 다익스트라 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/17531 번째 시도 [다익스트라 알고리즘에서 우선순위 큐를 쓰는 이유]최소거리 값 갱신 횟수의 감소때문이다. 먼저 우선순위 큐를 쓰지 않고 일반 큐를 써도 결과에는 차이가 없다. 하지만 우선순위 큐를 쓰는 이유는 속도에 이점이 있기 때문이다.import java.io.*;import java.util.*;class Node implements Comparable{ int end, weight; public Node(int end, int weight){ this.end = end; this.weight = weight;.. 2024. 5. 28. [백준] 파티 / 자바 문제 레벨: G3알고리즘: BFS풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1238 1 번째 시도: 실패 가중치가 있기 때문에 인접리스트 대신 인접행렬 선택갈 때 최단 거리를 구하는 dfs와 돌아올 때 최단 거리를 구하는 dfs2왜 굳이 dfs를 두개로 나누었나? 현 코드 dfs 리턴 값은 void로 답을 전역변수에 할당했다.효율적인건 리턴 값을 int로 하여 전역변수를 사용하지 않는 거다그러나 구현에 어려움이 있어 답을 전역변수에 할당하고 dfs를 2개로 나뉘었다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import .. 2024. 5. 27. [백준] 아기상어 / 자바 문제 레벨: G3알고리즘: 풀이시간: 12:34힌트 참조 유무:https://www.acmicpc.net/problem/162361 번째 시도: 실패 [알고리즘 선택 사고 과정]먹을 수 있는 것들을 다 먹어야 함(배열 탐색)먹을 수 있는 것에서 갈 때에는 최소한의 거리로 가야 함 -> BFS 선택되게 간단히 알고리즘 선택했다 [풀이 과정]반복문상어가 먹을 수 있는 것을 찾을 때까지 탐색(BFS)한다.만약 먹을 것이 없다면 반복문을 종료하고 답을 반환한다.자세한 건 주석 참조 import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;i.. 2024. 5. 25. [백준] 줄 세우기 / 자바 문제 레벨: G3알고리즘: 위상정렬 + 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/22521 번째 시도 가장 단순하게 구현을 하면 학생수만큼의 길이를 가진 배열을 만들고 문제에서 조건이 주어질 때마다 배열의 원소들의 위치를 바꿔주면 됩니다. 그러나 이렇게 하면 시간 복잡도에서 당연히 초과 판정을 받게 될 겁니다. 그렇기 때문에 알고리즘을 써야 하고 이때 사용할 수 있는 알고리즘은 위상 정렬(Topological Sort)이 있습니다. 위상 정렬(Topological Sort)은 그래프에서 선후관계 조건이 있을 때 이를 고려해서 노드의 순서를 정렬할 수 있습니다. (위상정렬은 순환그래프가 포함될 시 사용하지 못한다.) import ja.. 2024. 5. 24. 이전 1 2 3 4 5 6 다음
