https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net 최장 증가 수열 (LIS, Longest Increasing Subsequence) 출처 : https://4legs-study.tistory.com/106 😢 수열의 한 원소에 대해, 그 원소에서 끝나는 최장 증가 수열을 생각해보자. 그 최장 증가 수열의 k를 제외한 모든 원소들은 반드시 k보다 작아야 할 것이다. , 따라서 k의 앞 순서에 있는 모든 원소들 중 값이 k보다 작은 원소에 대해, 그 각각..
import java.util.*; public class Lis { public static void main(String[] args) { // Scanner sc = new Scanner(System.in); // int size = Integer.parseInt(sc.nextLine()); // String arrays = sc.nextLine(); // String[] ttee = arrays.split(" "); // int[] target = Arrays.stream(ttee).mapToInt(Integer::parseInt).toArray(); int size = 6; int[] target = {10,20,10,30,20,50}; int sol = 0; int[] dp = new int[..
🍕깊이 우선 탐색 : 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. 즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다. https://gmlwjd9405.github.io/2018/08/14/algorithm-dfs.html [알고리즘] 깊이 우선 탐색(DFS)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 깊이 우선 탐색(DFS)이 너비 우선 탐색(BFS)보다 좀 더 간단하다. 단순 검색 속도 자체는 너비 우선 탐색(BFS)에 비해서 느리다. 최단경..
😒 BFS / Breadth-First Search / 너비 우선 탐색 너비 우선 탐색 : 하나의 정점에서 시작해서 차례로 모든 정점을 방문하게 된다. 따라서 특정 도시에서 다른 도시로 가거나, 미로의 최단 거리를 찾거나, 보통은 두 좌표 사이의 ( 노드 사이의 ) 최단 경로 혹은 임의 경로를 찾기 위해 쓴다. 🥕 구현 시, 특정 좌표 ( 노드 ) 를 방문한것에 대한 여부를 반드시 검사해야 한다. 검사하지 않는다면 무한 루프에 빠질 위험이 존재한다. 방문한 노드를 차례로 꺼낼 수 있는 자료 구조인 Queue 를 사용. 즉 선입선출이 원칙이다. 🥕 왜 최단 거리가 되는가 ? https://wikidocs.net/125662 참조 : 미로탐색과 같은 문제를 BFS를 구현하다보면, 누구나 한 번씩은 의구심을 ..
https://www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int length = Integer.valueOf(br.readLine()); int[] tt = new int[length]; fo..
현재 개발 중인 프로젝트는 bearer 방식의 jwt + hash 비밀번호를 쓰려고 한다. SHA-256에 대해 알아 보려고 한다. java code 사용 할 경우. import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; public class main { public static void main(String[] args) throws Exception { System.out.println(sha256("needjarvis")); } /** * SHA-256으로 해싱하는 메소드 * * @param bytes * @return * @throws NoSuchAlgorithmException */ public sta..
완전탐색 상대적으로 구현이 간단하고, 해가 존재한다면 항상 찾게 된다. 완전 탐색으로 푼다면 기본적으로 시간 복잡도가 O(2^N)이나, O(N!) 이므로 INPUT의 값이 작아야한다. DFS / BFS 와 조합해서 풀이가 되는 문제가 꽤 있음. 방식은 대개 EX) { a, b, c, d } 중 2개를 뽑아서 일렬로 세운다면, ab ac ad ba bc bd ca cb cd da db dc 이처럼 다 찾거나, 반복문을 필요한 개수 만큼 돌리게 된다. for (int i=0; i < size; i++ ) { for (int j=0; j < size; j++) { for (int k=0; k < size; j++) { ...... } } } https://programmers.co.kr/learn/course..
선형 검색의 시간 복잡도는 O[N] 이다 라고 설명하는게 좋다. 공통적으로 모든 사람이 이해 하고 내용이 명확하게 어느정도인지 공유되고 알 수 있음 O[N] 으로 쓰는 게 Big O 표기법이다. 상수 알고리즘 O(1) 라고 표기한다. 인풋의 크기가 얼마나 되는 지는 상관이 없다. 위와 같은 알고리즘이 상수 알고리즘 항상 이렇게 구현 할 수 있을리가 없다. 에 속한다. 보기도 쉽고 알기도 쉽다. 다음은 O(N) 로 표기한다. 맨처음에 나타난 그래프가 O(N)이다 대각선 그래프다. Quadratic Time ( 2차 시간 ) 2차 시간은 Nested Loops (중첩반복) 이 있을 때 발생한다. 배열의 각 아이템에 대해 루프를 반복해서 실행한다. 따라서 시간복잡도는 인풋의 N^2 에 해당한다. 로그 시간(L..
https://www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); int money = sc.nextInt(); money = 1000 - money; int answer = 0; int coins = 0; int[] mon..
시작은 테스트 케이스는 통과하는 데, 반례가 뭔지 모르겠다 하지만, 정답을 푼 사람들의 답은 아주 간결했다. Arrays.sort(vv1, new Comparator() { @Override public int compare(T o1, T o2) { return 0; } }); 이 부분이 포인트. Arrays.sort 는 기본적으로 오름차순이지만, 아니라면 오버라이드를 통해 정렬 기준을 정해준다. 시간초과가 뜬 실패한 코드와 달리, 장황하게 for문을 안돌려도 된다. 내부적으로 Arrays.sort 가 처리하고 있겠지라고 생각해서 들어가 봤다. 왜 이거 쓰는지 궁금한 사람이 또 있었다. OKKY | 자바의 Arrays.sort는 왜 Dual-Pivot Quicksort를 사용하나요? 정렬공부를 하다 자바..
