for IF

📌 문제백준 | 파도반 수열 | SILVER 3 | DPhttps://www.acmicpc.net/problem/9461 📌 문제 탐색하기정삼각형이 나선(오른쪽 시계방향)으로 계속 돌면서 모양을 만듬  📌 알고리즘P(N)이 구현되는 모습이, 그 전의 값들로부터 영향을 받아 구현되기 때문에 이 문제는 ‘DP’ 알고리즘으로 풀 수 있다.이를 구현하기 위해, Memoization 을 활용한다.example) P(N) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9N012345678P(N)011122345       P[1] + P[5]P[2] + P[6]P[3] + P[7]즉, P(N) = P(N-5) + P(N-1) (단, N>=5)  📌 코드 설계하기TEST 입력MEMOIZATION 기법을 ..

📌 문제백준 | 가장 큰 증가하는 부분 수열 | SILVER 2 | DPhttps://www.acmicpc.net/problem/11055 📌 문제 탐색하기증가하는 부분 수열 중, 합이 가장 큰 것 구하기ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}⇒ 1,2,50,60 = 113⇒ 3, 5, 6, 7, 8 = 29그러므로 가장 큰 증가하는 부분 수열은 113  📌 알고리즘부분수열을 구해야하는데, A의 크기가 1,000까지 가능만약 for문을 통해 돌 경우, 1000 * (1000 - i) (i = 자신의 위치)시간이 1초제한이므로, 1000000 - 1000i라 가능할 것 같긴한데.. => 너무 비효율적인 것 같아서 PASS어쨌든, 최대 합인 부분수열을 골라야하므로, ..

📌 문제백준 | 행복 유치원 | level5 | 그리디https://www.acmicpc.net/problem/13164  📌 문제 탐색하기N명의 원생들을 키 순서대로 줄을 세우기총 K개의 조로 나누려고 함각 조에는 원생이 적어도 1명 있어야함같은 조에 속한 원생들은 서로 인접해 있어야함조별로 인원수가 같을 필요는 없음조마다 티셔츠를 맞추는 비용 = 가장 키가 큰 원생 - 키가 작은 원생출력 : 최대한 비용을 절약하기 위한 최소 비용 📌 알고리즘원생의 수 N은 최대 300,000까지 가능K는 N이하문제에서 이미 키 순서대로 작성됏으므로 Arrays.sort = O(NlogN)은 필요 x출력값을 최소로 만들기 위해선, 처음부터 각 조의 가장 키가 큰 원생과 작은 원생의 차이가 작도록 구성해야함 ⇒ 그..

9251번: LCSLCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.https://www.acmicpc.net/problem/9251 코드 설명fir : 첫번째 문자열firLen : fir의 길이sec : 두번째 문자열 secLen : sec의 길이lcs : LCS를 구현한 함수LCS란?Longest Common subsequence : 최장 공통 부분 서열두 서열이 주어졌을 때 두 서열 중 공통인 부분 서열 중 가장 길이가 긴것exampleACAYKPCAPCAK⇒ ACAK (최장공통부분서열)public static int lcs(char[] fir, char[] sec,int fi..

18352번: 특정 거리의 도시 찾기어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다. 모든 도로의 거리는 1이다.https://www.acmicpc.net/problem/18352 코드 설명graph : 그래프 생성용graph = new ArrayList(); for(int i =0; i