공부(2018~2019) - 스킨변경전/Algorithm

1. 땅따먹기(Programmers) 사용 알고리즘 : DP 문제를 제대로 읽지 않아서 열이 최대 100,000 인줄알고 아무리 생각해도 3중 for문이 나오는데 ... 라는 착각을 했다..... 그래서 궁금증을 가지고 해설을 봤는데 3중for문이여서 말이되나 싶었는데 다시 읽어보니 열의 개수는 고정 4개 였다.. 문제에 대한 접근&생각 임의의 점을 설정 -> 역으로 탐색해서 해당위치의 최댓값을 구함 -> 자기열을 제외한 아래열의 최댓값을 더한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 class Solution { int solution(int[][] land) { int n = land.length; int[][] dp= new in..

1. 가장 큰 정사각형 찾기(Programmers) 사용 알고리즘 : DP 예전에 기업 코딩 테스트볼때 이것보다 어렵지만 비슷한 유형의 문제를 본적있다. (그때는 못풀었다...) 코드를 보면 간단하지만 DP에 대한 접근방식을 모르면 상당히 어려울 수 있는 문제라 생각이 든다. 문제에 대한 접근&생각최대 넒이를 가지는 정사각형의 크기 -> n과 m은 최대 1000 -> 너무 많은 경우의 수 발생 -> DP!임의의 한점을 선택 -> 그 점을 오른쪽 아래로 가진다면? -> 인접한 왼쪽, 위쪽, 대각선 지점에서의 최대치의 최소값으로 알 수 있음아래 그림에서 셋중에서 가장 작은 (회색영역 + 1) * (회색영역 + 1)로 크기가 정해지는 것을 알수 있음 코드 123456789101112131415161718192..

1. 2688번 줄어들지않아(BOJ) 사용 알고리즘 : DP DP 기본적인 문제, 규칙을 찾아서 그걸 코드로 구현할 수 있는지 묻는 문제라는 생각이 들었다.예전에 비슷한 문제를 풀어본 기억이 있어서 금방 풀 수 있었던 것 같다. 문제에 대한 접근&생각최대 64자리의 줄어들지 않는 수 -> 완전탐색 불가! -> DP!규칙 : 11~ 99까지 45가지 ( 1+2~+8+9), 100~999는 165가지 (1+3+~+36+45)결과적으로 이전의 합의 누적이 된다. (1~9까지 합, 1~8까지합 ~) 코드 123456789101112131415161718192021222324252627282930313233343536373839import java.util.Arrays;import java.util.Scanner..

1. 2229번 조짜기(BOJ) 사용 알고리즘 : DP 처음에 209. 파일합치기(BOJ) 이문제와 유사하다는 느낌을 받아 비슷한 방법으로 풀어보았다.차이는 이문제는 기준점으로 부터 처음까지 탐색하여 결과를 내기 떄문에 1차원 DP만으로 풀 수 있었다. 문제에 대한 접근&생각조를 만드는데 가장 작은값과 큰값의 차이가 큰 경우 -> 결과조건!너무 많은 경우의 수 -> 완전탐색X, DP! 나이순으로 정렬되어 최대한 나이차이가 적게 나게 조를 구성 -> 순차적으로 조를 구성 -> 기준을 잡고 역탐색! 코드 1234567891011121314151617181920212223242526272829303132import java.util.Scanner; public class Main { public static ..

1. 1699번 제곱수의 합(BOJ) 사용 알고리즘 : DP 2019/05/31 - [공부/Algorithm] - 211. 동전(BOJ) 이문제와 유형이 비슷하다고 해서 한번 풀어보았다,동전 문제보다는 일반적인 DP 방식으로 접근해서 풀었다. 문제에 대한 접근&생각최대 100000의 숫자 중 가장 최소 항 조합 -> 약 1~300까지 조합 -> 너무 많은 경우의수 -> DP!처음 1^2 부터 시작하는 경우를 배열에 저장 -> ex) 11 = 1^2 + 1^2 ~ 자기 개수만큼제곱수와 대상숫자가 같은 경우는 하나의 항이 최소가 됨누적되있는 결과와 현재 조합할 수 있는 결과 중 작은 것이 최소항 코드 1234567891011121314151617181920212223242526272829import java..

9084번 동전(BOJ) 사용 알고리즘 : DP 몇번 풀어봤던 문제인데 한번에 떠오르질 않았다. 이번에 풀면서 확실하게 정리해둬야 겠다. 이전에 풀었던 문제들이 가로로 직선적인 흐름이라면 이 문제는 세로로 직선적인 흐름을 가지는 것 같다. 차곡차곡 쌓는게 아니라 한번 쭉 쌓고 다시와서 덧붙여 쌓는 방식의 문제이다. 문제에 대한 접근&생각 동전 최대 20개, 최대 금액 10000 -> 너무 많은 경우의 수 -> 완전탐색 X , DP! 이전에 만든 금액을 통해 만들려는 금액의 동전 개수를 알 수 있음 -> 메모제이션! 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 import java.util.Scanner; ..

1. 2631번 줄세우기(BOJ) 사용 알고리즘 : LIS 이 문제는 처음에 문제를 잘못 이해해서 더 어렵게 느껴졌다. 아이가 서로 swap 되는 정렬이 아닌 단순히 이동시키는 것이었다.LIS라는 힌트를 보고 이미 순서대로 서있는 아이들을 제외한 아이들 모두 움직이는 것이 최소라는 것을 통해 풀 수 있었다. 문제에 대한 접근&생각아이들의 순서를 오름차순, 이동 시킬 아이의 최소 -> 정렬? -> 최대 500명 -> DP!아이를 이동시킴 -> 이 뒤에 아이들은 밀림 -> 포함되지 않는 조건!이미 순서대로 있는 아이들 제외 한 나머지 아이들 이동 -> LIS! 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344i..

1. 11066번 파일합치기(BOJ) 사용 알고리즘 : 구간합, DP 1차원을 2차원 DP로 생각해야하는 문제 , 정답률이 50퍼센트여서 쉬울 줄 알았는데 되게 어렵게 느껴졌다, 다른 블로그를 보면서도 이해가 잘 되지 않았는데 3중 for문 구간합이 섞여있어서 더 그랬던 것 같다. 문제에 대한 접근&생각파일의 개수는 500개, 2개씩 처리 ( 순서상관없이) -> 경우의 수가 너무 많음 -> DP!DP[j][i] = min(DP[j][i], DP[j][k] + DP[k+1][i])-> j와 i 구간의 최솟값!지정한 곳 사이의 값들의 합이 필요 -> 구간합! 코드 123456789101112131415161718192021222324252627282930313233343536import java.util.S..

1. 6359번 만취한 상범(BOJ) 사용 알고리즘 : DP 배수 규칙을 이용하는 기초 DP 문제, 다른사람 코드들도 방식만 다르고 같은 원리를 이용했다.i*j 는 i의 배수가 여러 부분에서 활용이 가능한 것 같다. 문제에 대한 접근&생각매라운드 마다 K번째 배수로 방문의 상태가 변함 -> DP! (i*j는 i배수) -> 마지막에 결과값이 누적! 코드 1234567891011121314151617181920212223242526272829import java.util.Arrays;import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int..

1. 11048번 이동하기(BOJ) 사용 알고리즘 : DP 2019/05/27 - [공부/Algorithm] - 206. 보행자천국(Programmers) 단순히 DP문제를 풀려고 했는데 신기하게 어제푼 문제랑 비슷했다. 어제 푼 문제의 기초 버전 느낌이 든다... 무엇보다 경로느낌이 들면 DFS, BFS로 접근하려고 하는데 이제는 DP 먼저 생각을 해야겠다. 문제에 대한 접근&생각(1,1) 부터 (n,m) 까지 최댓값 -> DFS, BFS? -> n과 m이 최대 1000 -> DP!대각선으로 내려오는 경우, 왼쪽에서 오는 경우, 위에서 내려오는 경우 중 최댓값-> DP(i,j) = Max[DP(i-1,j-1),DP(i-1,j),DP(i,j-1)! 코드 1234567891011121314151617181..

1. 보행자천국(Programmers) 사용 알고리즘 : DP 예전에 많이 풀어봤던 경우의 수 누적 문제인 것 같아서 같은 방식으로 접근했지만 시간초과가 발생한 문제 단순히 2차원 배열 두개로 흐름을 나눠서 누적 방식도 이중포문만으로 구성해서 O(N^2)로 할 수 있는 것을 보고 놀라웠다. 문제에 대한 접근&생각m, n의 최대 크기 500 -> 한번 방문했던 곳은 재방문 없이 경우의 수만 처리 -> DP!DFS 형태로 구현 -> 시간초과! -> 2차원 배열 누적형태 ! 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697..

1. 캠핑(Programmers) 사용 알고리즘 : 좌표압축, 구간합 다른 블로그를 보면서 힘겹게 이해한 문제, 일반적인 알고리즘보다 확실히 어렵다는 느낌이 들었다.이문제를 풀면서 좌표압축하는 방법을 확실하게 알 수 있었다.(배열의 인덱스가 아닌 상대적 위치만 필요로 할때 사용) 문제에 대한 접근&생각좌표의 범위가 2^31-1 이고 대각선으로 떨어져 있으면 텐트를 만들 수 있음 -> 좌표압축!내부에 쐐기가 있는 경우 제외, 경계에 있는 쐐기는 허용 -> 결과조건!내부에 쐐기가 있는 경우에 대한 예외처리 -> 구간합! 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556..