🤷‍♂️Algorithm

트라이는 문자열 검색을 빠르게 실행할 수 있도록 설계한 트리 형태의 자료구조이다. 트라이의 핵심이론트라이는 일반적으로 단어들을 사전의 형태로 생성한 후 트리의 부모 자식 노드 관계를 이용해 검색을 수행한다.N진 트리 : 문자 종류의 개수에 따라 N이 결정된다. 예를 들어 알파벳은 26개의 문자이므로 26진 트리로 구성된다.루트 노드는 항상 빈 문자열을 뜻하는 공백 상태를 유지한다. https://www.acmicpc.net/problem/14425  코드1import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Main { public st..

트리(Tree)노드와 에지로 연결된 그래프의 특수한 형태 순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.트리의 부분 트리 역시 트리의 모든 특징을 따른다. 예제1https://www.acmicpc.net/problem/11725import java.util.*;import java.io.*;public class Main { static int N; static boolean[] visited; static ArrayList tree[]; static int answer[]; public static void main(String[] args) { Scanner sc = new Scanner(S..

유클리드 호제법 유클리드 호제법은 두 수의 최대 공약수를 구하는 알고리즘이다. 일반적으로 최대 공약수를 구하는 방법은 소인수분해를 이용한 공통된 소수들의 곱으로 표현할 수 있지만 유클리드 호제법은 좀 더 간단한 방법을 제시한다. 유클리드 호제법의 핵심이론 유클리드 호제법을 수행하려면 먼저 MOD 연산을 이해하고 있어야한다. MOD연산이 최대 공약수를 구하는 데 핵심 연산이기 때문이다. MOD 연산으로 구현하는 유클리드 호제법 1. 큰 수를 작은 수로 나누는 MOD 연산을 수행한다. 2. 앞 단계에서의 작은 수와 MOD 연산 결괏값(나머지)으로 MOD 연산을 수행한다. 3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택한다. 예제 1 https://www.acmicpc.net/problem/19..

소수 구하기의 핵심이론 대표적인 판별법으로는 에라토스테네스의 체를 들 수 있다. 에라토스테네스의 체란? 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. 배열의 끝까지 2를 반복한 후 배열에서 남아 있는 모든 수를 출력한다. 에라토스테네스의 체를 사용할 때 시간 복잡도는? 일반적으로 에라토스테네스의 체를 구현하려면 이중 for문을 이용하므로 시간 복잡도가 O(N²) 라고 판단 할 수 있다. 하지만 실제 시간 복잡도는 최적화의 정도에 따라 다르지만, 일반적으로 O(Nlog(logN))이다. 그 이유는 배수를 삭제하는 연산으로 실제 구..

그리디 알고리즘이란 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다. 그리디 알고리즘의 핵심 이론 해 선택: 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 적절성 검사: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지 검사한다. 해 검사: 현재까지 선택한 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못한다면 1. 로돌아가 같은 과정을 반복한다. 문제 풀이 먼저 선택된 카드 묶음이 비교 횟수에 더 많은 영향을 미친다. 따라서 카드 묶음의 카드의 개수가 작은 순서대로 먼저 합치는 것이 전체 비교 횟수를 줄일 수 있는 방법이다. 즉, 현재 데이터 중 가장 작은 카드의 개수를 가진 묶음 2개를 ㅃㅂ고 다시 데이터..

문제의 핵심은 이진탐색이다. 이진탐색은 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 핵심이론은 다음과 같다. 현재 데이터셋의 중앙값을 선택한다. 중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터셋을 선택한다. 과정 1~3을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. 문제에서는 블루레이의 크기가 모두 같고 녹화순서가 바뀌지 않아야 함 이라는 문제 조건이 이진 탐색 알고리즘을 선택하게 하는 실마리이다. 이진탐색의 시작 인덱스는 최대 레슨 시간인 9, 종료 인덱스는 레슨 시간을 모두 합한 45이다...

문제의 핵심은 버블정렬의 이중for문에서 안쪽 for문 전체를 돌 때 swap이 일어나지 않았을때의 횟수를 출력하는 것이다. 하지만 버블정렬을 이용하여 풀면 시간을 초과할 수 있어서 다른 아이디어를 사용해야합니다. 풀이 안쪽 루프는 1에서 n - j까지, 즉 왼쪽에서 오른쪽으로 이동하면서 swap을 수행한다. 이는 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리가 1이라는 뜻이다. 즉, 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾으면 이 문제를 해결할 수 있다. 마지막에 정렬이 다 완료되어 swap이 일어나지 않는 반복문이 실행되는 것을 감안해 최댓값에 1을 더합니다. import java.io.*; import java.uti..

풀이 슬라이딩 윈도우를 덱으로 구현하여 정렬할 수 있다. 처음 인덱스부터 덱에 넣어가면서 만약 들어온 새로운 값이 덱의 마지막 인덱스와 비교했을때 덱의 마지막인덱스의 값 > 덱에 새로 들어온 값일 경우 마지막 인덱스의 값을 삭제한다. 또한 예시처럼 L을 3처럼 잡고할 경우 인덱스가 3을 넘어가버리면 처음 인덱스는 제거해줘야한다. 똑같은 방식으로 계속 해가면 된다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); B..

문제는 다음과 같다. 풀이 숫자 3은 1과2로 이루어지고 4는 3과1 ... 10은 1과9 로 합쳐지듯이 다른 수 두개의 합으로 나타낼 수 있다면 그 수를 좋은 수 라고하는 것이다. 이 문제를 풀기 위해선 정렬과 투 포인터를 이용하여 해결하면 된다. for(k를 0부터 N까지 반복) { 변수 초기화하기(찾고자 하는 값 find, 포인터 i, 포인터 j) while(i < j) { if(A[i] + A[j] == 찾고자 하는 값) 두포인터 i,j가 k가 아닐때 결괏값에 반영 및 while 문 종료 두 포인터 i,j가 k가 맞을때 포인터 변경 및 계속 수행하기 else if(A[i] + A[j] < 찾고자 하는 값) 포인터 i 증가 else 포인터 j 감소 } } 좋은수의 개수 출력하기 import java..

문제는 다음과 같다. 문제의 핵심은 특정 구간 수들의 나머지 연산을 더해 나머지 연산을 한 값과 이 구간 합의 나머지 연산을 한 값을 동일하다. 구간 합 배열을 이용한 S[j] - S[i]는 원본 배열의 i+1 부터 j까지의 구간 합이다. S[j] % M의 값이 같다면 (S[j] - S[i]) % M 은 0이다. 즉, 구간 합 배열의 원소를 M으로 나눈 나머지로 업데이트하고 S[j]와 S[i]가 같은 (i,j)쌍을 찾으면 원본 배열에서 i+1부터 j까지의 구간 합이 M으로 나누어 떨어진다. import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int..