Preparing Coding Test/Algorithm14 [Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum) (출처 - 동빈나 유튜브) 배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간합 알고리즘에 대해 알아보려 한다. 수열에서 합이 N인 연속부분수열 → Two Pointer N개의 정수로 구성된 수열에서 M개의 쿼리에 해당하는 구간합 → Interval Sum 코테에서도 많이 나오는 것 같다. 특정한 합을 가지는 부분 연속 수열 찾기 [투 포인터를 활용한 알고리즘 설명] 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 현재 부분 합이 M과 같다면, 카운트한다. 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 양의 .. 2021. 6. 24. [Java/백준/DFS] 16964번: DFS 스페셜 저지 문제 www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 계속 99%에서 틀렸습니다가 떠서 환장했던 문제ㅠㅠ import java.io.*; import java.util.*; public class Main { static int N; static ArrayList[] adjacent; static boolean[] visited; static int[] compArr2; static StringBuilder sb = new.. 2021. 3. 9. [Java/백준/완전 탐색] 1018번: 체스판 다시 칠하기 문제 www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M*N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8*8 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 .. 2020. 12. 15. 우선순위 큐(Priority Queue) www.youtube.com/watch?v=AjFlp951nz0&list=WL&index=26 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 구현 방법 1) 리스트를 이용하여 구현 그냥 차례대로 쭉 넣은 다음에 꺼낼 때 하나하나 확인해서 값이 큰 거 출력 2) 힙을 이용하여 구현 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일 (힙 정렬) 삽입 시간 삭제 시간 리스트 O(1) O(N) 힙(Heap) O(logN) O(logN) 힙은 완전 이진 트리 자료구조의 일종 루트 노드로부터 시작해서 왼쪽 자식 노드, 오른쪽 자식 노드 순서대로 데이터가 차례대로 삽입되는 트리 힙에서는 항상 루트 노드를 제거한다. 최소 힙(Min Heap) 루트 노드가 가장 작은 값을 .. 2020. 11. 24. 다이나믹 프로그래밍 (Dynamic Programming) 동빈나 유튜브 참고 www.youtube.com/watch?v=FmXZG7D8nS4 다이나믹 프로그래밍 = 하나의 문제는 단 한 번만 풀도록 하는 알고리즘 다이나믹 프로그래밍을 사용할 수 있는 조건! 큰 문제를 작은 문제로 나눌 수 있다. (분할-정복의 개념) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (핵심!!) 예시 : 피보나치 수열 f(n) = f(n-1) + f(n+1) 이미 계산한 결과를 배열에 저장하는 메모이제이션(Memoization)이 분할-정복 기법과 다른 점이다. 어떤 조건일 때 종료되는지도 알아둬야 함! #include int dp(int x){ //언제 끝나는지 명시해주는 역할 if(x==1) return 1; if(x==2) return 1; return .. 2020. 9. 25. [자료구조/Java] Queue 구현하기 in Java www.youtube.com/watch?v=W3jNbNGyjMs 선입선출 방식(First-In First-Out, FIFO) 1) add() 2) remove() 3) peek() 4) isEmpty() import java.util.NoSuchElementException; class Queue{ class Node{ private T data; private Node next; public Node(T data){ this.data = data; } } private Node first; private Node last; public void add(T item){ Node t = new Node(item); if(last != null){ last.next = t; } last = t; //큐가 비.. 2020. 9. 9. [Java/자료구조] Stack 구현하기 https://www.youtube.com/watch?v=whVUYv0Leg0&t=9s LIFO (Last In First Out) 1) pop() : 마지막에 넣은 데이터를 가져오면서 지우는 함수 2) push() : 한 개 더 쌓아올리는 함수 3) peek() : 맨 위에 있는 걸 확인하는 함수 4) isEmpty() : Stack이 비어있는지 확인하기 코드 import java.util.EmptyStackException; class Stack{ class Node{ private T data; private Node next; public Node(T data) { this.data = data; } } private Node top; public T pop() { if(top==null) thr.. 2020. 9. 3. [자료구조/Java] 해시 테이블 (Hash Table) https://www.youtube.com/watch?v=Vi0hauJemxA&t=4s 검색하고자 하는 key 값을 입력받아 해시 함수를 돌려 반환받은 HashCode를 인덱스로 해서 데이터에 접근하는 방법! (key : 문자열, 숫자, 파일데이터) 암호화폐의 핵심 기술인 블록체인에서도 각 사용자들의 공공장부를 비교할 때도 해시코드를 이용한다. 해시테이블의 장점 검색 속도가 매우 빠르다! O(1) (해시 함수를 통해 만들어낸 해시 코드는 정수이다 → 배열 공간을 고정된 크기만큼 미리 만들어놓고 나눠담는다 해시코드 자체가 배열방의 인덱스로 쓰이기 때문에, 검색을 할 필요가 없고 바로 데이터의 위치에 접근할 수 있다!) 해시테이블의 단점 규칙에 따라 공간 활용이 비효율적으로 될 수 있다(Collision이 .. 2020. 8. 26. [자료구조/C, Java] 계수 정렬(Counting Sort) https://www.youtube.com/watch?v=n4kbFRn2z9M 목소리가 특이하신 분...ㅎ 범위 조건이 있는 경우에 한해서 굉장히 빠른 알고리즘이 있다. 계수 정렬(Counting Sort)는 단순하게 '크기를 기준으로 개수를 세는' 알고리즘이다. 지금까지는 모든 데이터를 그 자체로 위치를 바꾸어가며 정렬하는 알고리즘이었다. 계수 정렬은 '크기를 기준'으로 갯수만 세주면 되기 때문에 위치를 바꿀 필요가 없다. 모든 데이터에 한 번씩만 접근하면 된다는 점에서 무척이나 효율적이다. 1. 결과 배열의 크기를 숫자의 크기 범위만큼 잡아준다. 2. 하나를 확인할 때마다 배열에 데이터를 한개씩 증가시켜준다. 3. 출력할 때는 단순하게 배열 원소의 숫자만큼 반복하면 된다. - 시간 복잡도 : O(N).. 2020. 8. 20. 이전 1 2 다음
