코딩테스트/JAVA8 DP 팁 일단은, 나는 DFS나 BFS를 먼저 떠올린다.너무 클 거 같다면 1. 문제를 막 풀고 그 결론이 DP 2. 앞에서 부터 DP (2번의 경우에는 DP[I] = DP[I-1]+_ORIGINAL[I-2]~~ 식으로 할 때, 어디까지 DP의 영향이 닿고, 어디부터 닿지 않는지를 고려하자)3. 뒤에서 부터 DP (굉장히 어렵다) 이걸 사실 암기처럼 할게 아니고,1번의 경우는 수학적인 식이 DP라는 말이고 EX) Y = X+1 , Z = 2Y , Z = 2X+2 이런 느낌2번의 경우, 3번의 경우는 지금 현재의 값이 어디에서 왔는가. 를 고민하고어디까지 이전 값이 영향을 끼쳐도 되는가, 어디부터 안되는가 고민하면 된다. 또, 단순한 1차원 행렬이 아닐 수도. 기본적으로 dp가 2차원 행렬에서 이전 값이 다음 .. 2024. 10. 10. 투 포인터, 슬라이싱 윈도우 사용 전략? 일단은, For문으로 생각해본다. for문으로 생각하면 이중, 삼중이 되어 시간 복잡도가 1억이 넘는 경우가 생기는데, 이럴때 생각해볼 방안이다. 투포인터의 핵심은기존 정보를 저장해놓고, start, end index를 조정하여 특정 원소만 빼고 더한다는 것이다.투포인터의 시간복잡도는 O(N)이다.하지만 아무렇게나 짠다고 O(N)이 되어 주는 것은 아니고,기존 정보를 저장해놓고 END는 목표 (보통 WHILE문 안에 ENDSTART는 그 이후에 해당 INDEX를 쫓아가게 구현해야 한다. 그리고, 한 작업 중에 START나 END 모두 같은 방향으로 움직여야 한다.그래야 O(2*N = N)이 나온다.핵심 마지막은, 그러한 포인터들이 초기화되어선 안된다는 것. END가 3일때 START가 다 돌.. 2024. 9. 28. 인접 행렬, 리스트를 활용한 BFS 즉, 선이 많을때는 인접행렬을, 그렇지 않을때는 둘다 매우 많을때는 인접 리스트로 구현하자. 이게, List로 배열을 만들어 쓰는 예시이다. public static int BFS(int [][]graph, int n) { Queue q = new LinkedList(); boolean [] visited = new boolean[n+1]; int cnt = 1; q.add(1); visited[1] = true; while (!q.isEmpty()) { int now = q.poll(); for (int i = .. 2024. 9. 19. 특정 조건의 값(배열에 없는, 선택할 떄?) - 이진탐색 import java.util.*;import java.lang.*;import java.io.*;class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)) ; BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int N = Integer.parseInt(br.readLine()); String [] Strarr = br.readLine().split(" ").. 2024. 9. 13. 문자열 STRING.CONTAINS("문자열 중 일부") , 문자열.REPLACE("문자","바꿀 거") ; 2024. 8. 7. 자바 문법 - 배열, 정렬, set 1. python 처럼, 배열을 받아와서 split 시키기 String[] myarr = s.split("") 2. 특정 값의 index 불러오기 myarr.indexOf(값) -> 젤 가까운 값 3. valueOf주의 사항. => String.valueOf(바꿀 값)사실상 . parseInt같은 String 버전이다. 4. 배열 정렬import java.util.Arrays; -> 까먹지 말기Arrays.sort(배열)Arrays.sort(배열,Collections.reverseOrder()) 5.list 정렬?List list = new LinkedList();list.add(“김철수”);list.add(“김영희”);list.sort(); 6.char 대문자 A-Z: 유니코드 값 65-90소문자 a-.. 2024. 7. 24. 파이썬에서 넘어오며 헷갈리는 문법들 1. 배열 자바엔 [:]와 같은 슬라이싱 기능이나, A[3]과 같은 기능이 없다.대신 STRING의 원소중 하나를 쓸 때는 . charAt(index)를 활용하자.<p style.. 2024. 4. 20. JAVA로 코딩테스트 언어 변경 제목과 같다. 파이썬으로 현재 프로그래머스 기준 2초반~ 정도의 난이도를 풀 수 있음에도 불구하고 변경하려는 이유는 다음과 같다. 다른것보다, 나는 지금 자바의 문법이 가장 약점이다. 프로젝트를 진행하며SQLD 취.. 2024. 4. 20. 이전 1 다음
