Algorithm/개념8 [알고리즘 개념] TreeDP / JAVA TreeDP Tree : cycle이 없는 그래프(서로 다른 두 노드를 잇는 간선이 1개) TreeDP는 Tree구조에서 서브트리(부분 문제)의 해를 가지고 전체 해를 구하는 방식입니다. DP에 서브트리의 어떠한 것(서브트리의 노드 개수, 서브트리의 간선 개수 등등)을 저장해둘 것이고, 보통 DFS를 통해 탐색하면서 서브트리의 해를 구해나갑니다. 정점을 기준으로 탐색해나간다면, 보통 O(N)만에 풀립니다. 백준 15681 트리와 쿼리 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ .. 2022. 3. 17. [알고리즘 개념] 브루트 포스(Brute Force) /Java 코드 브루트포스 알고리즘이란 완전탐색 알고리즘. 모든 경우의 수를 탐색해보는 알고리즘. Brute:짐승,동물 Force: 힘 . 즉 난폭한 힘 이런 뜻인데, 모든 경우의 수를 완전 탐색으로 구하는 알고리즘이다. 브루트포스 알고리즘의 방법으론, for문을 이용한 탐색, 백트래킹(재귀)을 이용한 탐색, DFS&BFS 탐색 등이 있다. (재귀와 DFS,BFS는 추후에 설명) 컴퓨터는 약 1초에 1억번(10^8)의 연산이 가능하다고 알려져있는데, 브루트포스는 전체 탐색하기때문에 좋은 알고리즘 방식이 아니다. (600억을 확인한다면... 600초 = 확인하는데만 10분...) 그래서 실제 알고리즘을 풀땐, 이 문제가 브루트포스로 가능한지 확인 후 불가능하다면 어떤 알고리즘을 적용해서 시간복잡도를 줄일지 확인해야한다.(.. 2022. 1. 30. [알고리즘 개념] 소수 구하기, 소수 판별 / JAVA 소수(Prime Number)란 1보다 큰 자연수 중 1과 그 수 자신만을 약수로 갖는 자연수 알고리즘 문제중에 소수판별 및 구하는 문제는 많이 나온다. 개발자들 사이에서 소수를 중요시 여기는 이유는 암호화방식에 소수를 많이 쓰기 때문입니다. 대표적으로 RSA암호방식이 있습니다. 2022.01.27 - [CS/NetWork] - [네트워크] 대칭키(Symmetric key), 공개키(Public Key), RSA 암호화 3가지방식으로 구해볼 예정 방법1(N미만 수로 나누기) 위에서 얘기했듯 1과 본인의 수(N)로만 나눠져야하므로, 1과 N를 제외한 약수가 있다면 소수가 아님. N미만의 수로 나누어서 확인 시간복잡도 해당숫자만 소수판별: O(N) 숫자이하 소수구하기: O(N^2) import java.ut.. 2022. 1. 28. [알고리즘 개념] 펜윅 트리(Fenwick Tree,Binary Indexed Tree) / JAVA 펜윅트리는 세그먼트 트리를 변형한 버전이므로, 세그먼트 트리를 먼저 알아야 이해가 잘 됩니다! 2022.01.17 - [Algorithm/개념] - [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java 그리고 비트 단위로 연산하기 때문에, 비트 연산자를 알아야합니다! 2022.01.14 - [Algorithm/개념] - [알고리즘 개념] 비트마스크(Bitmask) 펜윅트리란(Fenwick Tree, Binary Indexed Tree, BIT) 세그먼트 트리에서 메모리를 절약한 트리. 시간복잡도 O(MlogN) 데이터 변경: O(logN) 연산: O(logN) 공간복잡도 O(N) 펜윅트리는 세그먼트 트리에서 우측 노드를 지운 트리입니다. 만약 5~7까지의 합을 알고 싶다면, 1~7까지의 .. 2022. 1. 17. [알고리즘 개념] 세그먼트 트리(Segment Tree) / Java 세그먼트 트리란 특정 구간 내 데이터에 대한 연산(쿼리)을 빠르게 구할 수 있는 트리. ex) 특정 구간 합,최소값,최대값,평균값 등등 Segment : 부분.분할.나누다.분할하다. 시간복잡도 데이터 변경: O(logN) 연산: O(logN) 데이터 변경할때마다 M번 연산: O((logN +logN)*M) = O(MlogN) https://www.acmicpc.net/problem/2042 2042번: 구간 합 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 문제 어떤 N.. 2022. 1. 17. [알고리즘 개념] 비트마스크(Bitmask) 비트 마스크를 설명하기 앞서, 비트를 알아야한다. 잘 알면 아래부터 보면 됨! 더보기 비트(Bit) 컴퓨터는 이진수를 통해서 모든 자료를 표현한다. 여기서 사용하는 이진수가 데이터의 최소 단위 Bit(binary Disit)이다. 비트는 0 또는 1의 값을 가지며, n개의 비트는 2^0~2^n-1까지 표현 가능하다. 1 = 2^0 = 1 10 = 2^1 = 2 100 = 2^2 = 4 111 = 2^2+2^1+2^0 = 7 3자리의 비트는 1~2^n-1 까지 표현가능 비트 연산자 및 용어 정리 최상위 비트(MSB): 2^n-1 비트 최하위 비트(LSB): 2^0 비트 비트가 켜져있다: 1 비트가 꺼져있다: 0 int는 4byte 총 32비트로 되어있다. ( 최상위 비트는 부호비트 1: -, 0:+) in.. 2022. 1. 14. [알고리즘 개념] KMP - 문자열 검색 알고리즘(JAVA 코드) KMP란 문자열 검색 알고리즘. Knuth-Morris-Pratt 3명의 사람이 설계한 알고리즘으로, 전체 문자열에서 특정 문자열을 찾는 알고리즘. 시간복잡도: N+M N(전체 문자열 길이), M(패턴 문자열 길이) 브루트포스로 풀이 코드 가장 쉽게 생각할 수 있는 브루트포스로 전체 문자열에서 특정 문자열을 찾았다면, 시간복잡도는 전체 문자열의 길이(n) * 특정 문자열의 길이(m) public Main{ String all = "ABABABCD"; // 전체 문자열 String pattern = "ABABC"; // 패턴 int cnt = 0; //패턴이 맞은 개수 for(int i = 0; i < all.length(); i++){ boolean check = true; // 패턴이 맞는지 체크 변수.. 2022. 1. 12. 정렬 알고리즘(sort) 버블 정렬 알고리즘(Bubble Sort) 서로 인접한 두 원소를 검사하여 순서에 맞지 않는 경우 위치를 바꾼다. 시간복잡도 : O(n^2) | 5 | 4 | 6 | 1 | 3 | 2 | 위의 숫자로 이루어져 있을때 1회전 시 5 4 비교하여 작은숫자를 왼쪽 큰 숫자를 오른쪽으로 | 4 | 5 | 6 | 1 | 3 | 2 | 5 6 비교 시 아무일도 일어나지 않음. 6 1 비교 시 | 4 | 5 | 1 | 6 | 3 | 2 | 6 3 비교 시 | 4 | 5 | 1 | 3 | 6 | 2 | 6 2 비교 시 | 4 | 5 | 1 | 3 | 2 | [6] | 4 5 1 3 2 [6] 마지막 6은 이제 고정 큰수를 계속 뒤로 미뤄내기때문에 가장 마지막값은 최대값이 되고 2회전때는 마지막값은 비교할 필요 없으니 .. 2022. 1. 5. 이전 1 다음
