코딩테스트46 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. BufferReader,Writter. 기타 자료구조 활용법 현재 파이썬으로 한 문제를 풀고, 그 문제를 JAVA로 바꾸는 것을 진행중이다.그러다 실버1정도의 난이도임에도 JAVA에서'만' 출력오류가 나는 것을 발견했다. 1. 입력받기BufferReader br = new BufferReader(new InputStreamReader(System.in));int N = Integer.parseInt(br.readLine()); // nextInt없음 2. 출력하기BufferWriter bw = new BufferWritter(new OutPutStreamWriter(System.out)); //tt아니다.. Stringbuilder sb = new StringBuilder();sb.append("할일"), sb.append('\n') // 각 문자별 띄어쓰기bw... 2024. 8. 10. 다익스트라 다익스트라는, 최단 경로 (비용이 일정하지 않을 때) 사용하는 알고리즘이다.(비용이 일정할땐, bfs로 푸는 것이 쉬움을 이전에 배웠다.) 세팅 : 정답 행렬 (어디서 어디로 갈때 얼마나 비용이 드나) 를 무한대로 초기화 (n,n은 0으로 초기화)0.출발 노드를 우선순위 큐에 넣는다.1. 처음 입력받은 거리 행렬 중, 현재 인덱스 -> 갈 수 있는(아직 안 간) 가장 값이 작은 노드 선택2. 해당 노드까지 가는 비용 ex ) 1->4 >>> 정답행렬의 해당 노드 [ex )정답행렬[1] ] + 기존 행렬의 1->4 3. 업데이트가 실행 되면, 그 값을 정답행렬에서 바꾼다. 4. 업데이트가 실행 되면, 그 INDEX를 우선순위 큐에 넣는다. (주로 HEAPQ로 구현한다. 정렬을 안해도 되므로)5. 그 .. 2024. 8. 9. 문자열 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. CCW 알고리즘이란? 점선 세개가 놓여졌을때, 그 점선 세개의 방향이 어디로 가는지를 확인하는 알고리즘 이와 같은 형태로 구현한다. 이 TEMP가 >0시 반시계, =0시 직선 **부록 - 점 4개로 넓이 구하기x1*y2+~~x4*y1 - (y1*x2+~~~) 같은 방식이지만,점 4개로 구하면 넓이가. 3개로 구해서 도형이 되지 않으면 방향이 구해진다. *주의! 4각형은 불가한 부분이 있다. (시계방향 정렬이 되어있어야. )그떄는 가장 큰 x간 차이, y간 차이를 곱하자 . 2024. 7. 8. deque를 쉽고 고급지게 쓰기 + 다각형 넓이 구하기 팁 이전까지는 deque를 , 단순히 양쪽 pop & push가 가능한 형태로만 썼다.이를 고급지게 활용해보자 1. deque에서의 pop 일단, from collections import deque로 선언deq = deque()로 선언 deq.popleft() , deq.popright()로 pop(0), pop()을 변경하자.#pop은 기본적으론 가장 오른쪽 pop임을 기억하자 2. rotatedeq.rotate(-1) # 왼쪽 회전deq. rotate(1) # 오른쪽 회전 이러한 rotate는, 특히나 직접 컨테이너벨트나 숫자등을 구현할 때 쓰인다. #활용 예시 백준. 20055 import sys from collections import deque inputlist = list(map(int,sys.. 2024. 7. 4. 이전 1 2 3 4 5 다음
