알고리즘/문제풀이

가. 문제파악 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..

가. 문제파악 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()..

가. 문제파악 1. 유형 : 배열 활용, 수학 - 처음 봤을때 수학 규칙을 찾으려고 하다보니 이해도 어렵고 구현하기도 쉽지 않았다. - 다른사람의 풀이들을 봤는데 규칙으로 찾거나 배열을 활용해서 푼게 있었다. - 내가봤을때 배열을 활용하는게 이문제가 원하는 부분이 아닐까? 라는 생각이 들었다. 나. 코드 1. 풀이 : 피라미드를 2차원배열로 붙이자 - 피라미드 자체로 보다보면 보기가 어렵고 1차원 배열로만 생각하게 되어버린다... - 그림처럼 2차원배열로 생각하면 쉽다. 아래 옆 대각선 순으로 하나의 스텝으로 가져가면 된다. import java.util.Arrays; public class Solution { public int[] solution(int n) { int[][] arr = new int..

가. 문제파악 1. 유형 : 정렬 - 이문제는 처음에 접근을 뒷자리가 큰순으로 정렬 했다가 망해버렸다 ... - 어떻게 접근해야하는지 감이 안와서 답안을 참고하여 풀었다. 나. 코드 1. 풀이 : 두개를 더해서 비교 후 정렬! - 생각보다 단순하다. 두문자를 더해서 미리 비교해서 정렬 하는 것 이다! => {10,2,1} 이면 10, 2 -> 210 > 102 / 2 ,1 -> 21 > 12 / 1,10 -> 110 > 102 정렬 {2,1,10} - 정렬된배열을 한줄로 만들면 된다. 그리고 0일경우 000 이렇게 될수있으니 예외 처리 필수! import java.util.Arrays; import java.util.stream.Collectors; public class Solution { public..

가. 문제파악 1. 유형 : 순열, 에라토스테네스 체 - 경우의수는 항상 느끼지만 많이 헷갈리게 하는 것 같다. - 모든 경우의수 구하는 것을 그려보면 최대한 깊이 들어갔다가 돌아왔다가 하는 원리이다. - 여기서는 모든 경우의 수가 아닌 중복없이 만들 수 있는 경우의 수를 판단해야한다. 나. 코드 1. 풀이 : Vistied, 재귀 - boolean 배열을 활용해서 해당 숫자를 사용했는지 안했는지 판단하는 것이 중요하다 - 에라토스테네스 체로 소수를 구하고 이를 이용해서 count를 올려준다. (false로 판단해서 조금이상하다..) - 숫자에 대한 중복은 허용되지 않으니 한번 만들어진 소수는 소수가 아닌걸로 해줬다. public static int n; public static char[] array;..

가. 문제파악 1. 유형 : 진법 - 뭔가 알듯 말듯 하면서 잘 풀리지 않았던 문제였다... 진법만 나오면 머리가 띵해지는 것 같다. 나. 코드 1. 풀이 : 3진법과 보정 - 문제를 보면서 처음엔 3개로 만들 수 있는 모든 경우의 수를 구하면 되지 않을까 생각했다 - 보다보니 3진법으로 풀릴것 같아서 3진법으로 하는데 문제가 발생했다. - 3진법으로 그려보면 숫자보다 먼저 자리수가 달라지는 문제가 발생한다. 3 | 6 --- 3 | 2 - - - 0 --- 0 - - - 2 3 | 6 --- 3 | 1 - - - 0 -> -1 --- 0 - - - 1 - 자리수가 달라지기 때문에 자리수 보정을 해준 뒤 0을 "4" 라고 생각하면 된다 public String solution(int n) { String..