알고리즘

가. 세그먼트 트리 a. 무엇인가 - 어떤 배열의 구간합을 트리형태로 저장 b. 특징 - 배열로 구간합을 저장하고 (S[i]= S[i-1]+A[i]) 원하는 구간을 (S[R] - S[L-1])의 형태로 구현이 가능[O(1)] - 하지만 배열의 값이 바뀌는 경우 바뀔때마다 구간합을 더해서 저장해야한다 O(N*변경) - 세그먼트 트리는 이를 O(logN)으로 만들어 줄 수 있다. 나. 구현 a. DFS 및 이분탐색의 활용 - node는 1번부터 시작하며 node*2가 왼쪽 자식노드 node*2+1이 오른쪽자식 노드가 된다. - 트리의 구성은 이분탐색으로 쭉쭉 내려가면서 start랑 end가 같아질때 해당 노드번호에 요소를 저장한다. - 리프에 저장이 끝나면 위로 돌아와서 해당구간을 더한 값을 저장해준다. p..

가. 무엇인가? a. 캐시 알고리즘 - 데이터를 빠르게 가져오기도 하고 DB 부하를 줄이기 위해 캐시를 많이 사용한다. - 하지만 캐시에도 용량이 있기 때문에 지워주면서 사용해야한다. - 이런 캐시를 관리하는 여러 알고리즘이 존재한다. b. LRU - Least Recently Used, 최근까지 적게 hit된 캐시데이터를 지우는 방법이다 나. 구현 a. LinkedHashMap을 활용 - LinkedHashMap에는 두가지 정렬 모드가 있다. ( ordering mode, insertion-order mode) => 들어온 순서를 그대로 가져가는 모드, access로 가져가는 모드 - access 모드를 이용해 쉽게 LRU를 구현할 수 있다. public static void main(String[] ..

가. 문제파악 1. 유형 : 그리디 - 되게 자주보이는 유형인데 생각보다 접근하기가 쉽지 않는 것 같다. - 핵심은 이전 스케줄에 대한 추가,삭제를 어떻게 처리할 것 인가! 이다. 나. 코드 1. 풀이 : 정렬과 타입 - 스케쥴을 시점별로 따로따로 분리해서 풀었다. 즉 start 와 end를 따로 하나의 요소로서 정렬하여 푼다. - 주의할점은 수업은 동시에 진행되는 조건이 있기 때문에 시간이 같으면 end 먼저 처리해야한다. import java.util.ArrayList; import java.util.Collections; import java.util.List; import java.util.PriorityQueue; import java.util.Scanner; public class Main {..

가. 문제파악 1. 유형 : 그래프 - 접근을 어떻게 해야할지 감이 잘안왔던 문제, 단순배열의 경우로만 하려다가 그래프로 풀이했다. 나. 코드 1. 풀이 : 양방향으로 탐색하자! - 순위를 확정 지을 수 있는 것은 결국 자신 이외에 사람들과 승패가 갈려야한다. - a-b 에서 b가 승자고 b-c에서 c가 승자면 a-c 에서 승자는 a가 된다. - 모든 선수들을 연결하여 그래프 탐색을 하면 위의 경우를 파악할 수 있다. import java.util.LinkedList; import java.util.List; public class Solution { public int solution(int n, int[][] results) { int answer = 0; order = new LinkedList[n..

가. 무엇인가 a. 정렬 - 싸이클이 없는 방향그래프에서 정점들을 일렬로 나열하는 알고리즘이다. => 각 정점에 대해서 순위를 부여함 ex. 강의 수강 순서도 b. 시간복잡도 - O(N+M) DFS 탐색시간 + O(N) 뒤집는시간 = O(N+M) 나. 구현 a. DFS를 활용 public class 위상정렬 { public static void main(String[] args) { int N = 7; List[] graph = new ArrayList[N]; for(int i = 0; i < N; i++) { graph[i] = new ArrayList(); } graph[0].add(4); graph[0].add(5); graph[1].add(3); graph[1].add(4); graph[2].ad..

가. 무엇인가 a. 최단경로 - 시작정점부터 모든 정점으로 가는 최단경로를 구하는 알고리즘 => 가중치가 양수일 경우에만 사용가능 - 진행 0. 모든 정점이 가지고 있는 가중치합(시작정점부터 도착정점까지의 최단경로)을 INF(엄청큰값) 초기화한다. 1. 현재 정점(동그리미)이 가진 간선들중 가장 최소값을 가지는 간선의 정점을 방문한다. => 이때 방문 정점이 가지고 있는 가중치합은 여러 정점을 거쳐왔을수도 있다. 2. 현재 경로의 가중치합과 방문정점이 가지고 있는 가중치의 합을 비교해서 최소값으로 업데이트한다. 3. 현재 시점에서 가중치합이 더 작았다면 방문정점에서 다시 1번을 수행한다. 나. 구현하기 a. 배열 public class 다익스트라 { public static void main(String..

가. 문제파악 1. 유형 : 완전탐색 - 이문제는 카테고리로 문제 유형이 있어서 풀수 있지 않았나 싶은 생각이 든다... - 그림을 그려보다보면 쉽게 이해할 수 있다. 나. 코드 1. 풀이 : 완전탐색, 약수 - 그림을 그려보다 알았는데 사각형을 만들수 있는 경우는 대응 대는 약수의 곱인 것을 알수 있었다. => 18인 경우 1x18 2x9 3x6 {1,2,3,6,9,18} - 규칙을 알면 간단하게 풀리는 문제였다 public int[] solution(int brown, int red) { int a = 0; int b = 0; for (int i = 1; i

가. 문제파악 1. 유형 : 큐 - 생각보다 어렵게 느껴졌던 문제.. 구현하면서 생각하다보니 조금 지저분해졌다.. - 때로는 단순한 방법으로도 해결할 수 있다는 것을 생각하자! 나. 코드 1. 풀이 : 다리에 있는 시간을 큐로 만들자! - 조건 1. 다리는 큐이고 다리의 길이가 끝나는 지점이 큐에서 Poll을 해주는 것이다. 2. 다리에서 빠져나갔으니 중량에서 그만큼을 빼준다. 3. 중량이 가능하면 큐에 트럭을 추가하고 안되면 -1를 추가하자(1초에 의미) - 트럭이 한대면 대응을 못해서 하나의 경우에 대해 예외처리를 해줬다 ... import java.util.LinkedList; import java.util.Queue; public class Solution { public static void m..

가. 문제파악 1. 유형 : 브루트포스 - 이 문제는 제한이 크지 않기때문에 모든 경우의 수를 확인해주면 된다. 나. 코드 1. 풀이 : 모든 경우의 수를 구하자 - 이문제의 채점의 경우 하나로 여러번 실행하기 때문에 반드시 모든변수의 초기화를 메서드내에서 해야한다. => 테케는 맞는데 틀리는 경우 '왜틀렸지?' 하는 늪에 빠질수있다.. - 여기서 거리는 사이에 낀 캐릭터의 수이다 그러므로 -1 보정이 필요하다 ( 문제를 꼼꼼히 읽자....) import java.util.ArrayList; import java.util.List; public class Solution { public int solution(int n, String[] data) { String[] in = {"A", "C", "F",..

가. 문제파악 1. 유형 : 분할정복, DFS - 예전에 한번 본적이 있는 문제라 쉽게 풀줄 알았는데 생각보다 어려웠다 .. - 어렴풋한 기억으로 풀려다보니 모든걸 쪼갠뒤에 답을 구하려하니 답이 나오지 않았다. 나. 코드 1. 풀이 : 4방면으로 쪼개자! - 스타트 지점이 중요한데 (0,0) 을 기준으로 큰 -> 작은 사각형 순으로 4방면으로 분할하자! - 4방면으로 분할하기 전에 압축할 수 있는지를 판단 해야한다! => 전부 1 또는 0이라면 하나로 압축이 가능하므로 큰거 부터 판단해야한다. import java.util.Arrays; public class Solution { public int[] solution(int[][] arr){ ans = new int[2]; div(0,0,arr.leng..

가. 문제파악 1. 유형 : DP - 많이보는 DP유형의 기본 문제, 점화식을 세우면 간단하게 해결된다. 나. 코드 1. 풀이 : DP - 해당라인을 밟는 최대값은 밟은 라인을 제외한 3개의 라인의 최대값이다. - 이를 누적해서 구하면 끝~ public class Solution { public int solution(int[][] land){ int[][] dp = new int[land.length][land[0].length]; dp[0][0] = land[0][0]; dp[0][1] = land[0][1]; dp[0][2] = land[0][2]; dp[0][3] = land[0][3]; for (int i = 1; i < land.length; i++) { dp[i][0]=Math.max(Mat..

가. 문제파악 1. 유형 : 구현 - 이문제는 처음보고 규칙을 찾아야 하는건가 싶어서 너무 어렵게 느껴졌다. - 이게 어떻게 level2인가 싶었는데 최대치해도 크게 복잡도가 없어보여서 그대로 구현했더니 맞았다.. 나. 코드 1. 풀이 : 진법, 구현 - 미리 구해야하는 수 까지만 구하면된다. - n진법으로 변환해서 때려넣기만 하면 된다! public class Solution { String de[] = {"A","B","C","D","E","F"}; public String solution(int n, int t, int m, int p){ // p 튜브순서, m 참가인원, t 미리구할수개, n진법 int total = m * t; StringBuilder to = new StringBuilder()..