Algorithm (12) 썸네일형 리스트형 [백준] 플래 V 달성 골드를 목표로 시작했지만, 막상 골드가 되고나니 골드 문제를 못 푼다.다시 또 다음 목표인 플래티넘을 달성했지만, 또 플래티넘 문제를 못푼다.플래티넘 문제를 풀 수 있으면 좋겠지만, 지금은 오버 스터디인게 아닌가? 싶다이제는 습관화 된 공부를 통해 더 많은 골드 문제를 푸는 것이 목표이다. [백준] 11054. 가장 긴 바이토닉 부분 수열 문제 풀이 해당 문제를 풀기 위해서는저번 시간에 배웠던 LIS 개념을 써야한다.이전에 배웠던 개념을 활용하니 금방 해결할 수 있었다.LIS에 대해 잘 모르겠다면 아래 글을 먼저 보고 오면 좋을 이해하는데 도움이 될 것 같다. https://inscowoo.tistory.com/37 [백준] 11053. 가장 긴 증가하는 부분 수열(LIS) - JAVA문제풀이 처음에는 DFS의 재귀를 이용해서 약 2시간동안 풀어보았다. import java.io.*;import java.util.*; public class Main{ static StringBuilder sb = new StringBuilder(); static int N,Max,cur; static int[] arr; static void dfs(int.. [백준] 12865. 평범한 배낭 (DP) - JAVA 문제 풀이 해당 문제는 가장 유명한 배낭 문제이다. 동적 프로그래밍(DP)를 활용해서 풀어야 한다.우선, 시간 복잡도는 (N*M) 이다. 문제에서 받은 데이터인물품 개수 N = 4가방의 무게 K = 7 로 풀이를 해보겠다. 2중 for문을 통해서 DP[ ][ ] 값을 채워넣을 건데먼저 비교식부터 알려주자면,i = 가방의 넣을 수 있는 물품 위치w = 현재 무게 DP[ i ][ w ] = Math.max(DP[ i-1 ][ w ] , DP[ i-1 ][ w-(i의무게) ] + i의 가치)이다.쉽게 말하자면, 현재 물품을 추가하지 않고 그대로 가기vs현재 물품만큼 가방을 비우고, 현재 물품 추가하기 아래에서 표를 통해 확인해보자. [0][1] (6,13)[2] (4,8)[3] (3,6)[4] (5,12.. [백준] 11053. 가장 긴 증가하는 부분 수열(LIS) - JAVA 문제풀이 처음에는 DFS의 재귀를 이용해서 약 2시간동안 풀어보았다. import java.io.*;import java.util.*; public class Main{ static StringBuilder sb = new StringBuilder(); static int N,Max,cur; static int[] arr; static void dfs(int cur,int depth,int count){ if(depth == N){ Max = Math.max(count, Max); return; } for(int i=depth; iN; i++){ if(arr[i]>cur){ .. [백준] 골드 V 달성 처음 시작할 때 골드를 목표로 시작했지만, 어느새 골드이다.이제 다음은 플래티넘이다.느낀점은 코딩테스트는 꾸준한게 답이다. 화이팅 [백준] 30804. 과일 탕후루(슬라이딩 윈도우) - JAVA 문제 풀이 해당 문제를 풀기 위해서는 우선, 슬라이딩 윈도우를 알아야 한다.슬라이딩 윈도우란? 배열이나 문자열처럼 연속된 데이터를 다룰 때, 일정 크기의 구간(윈도우)를설정하고 그 구간을 한 칸씩 밀면서 문제를 푸는 방식이다.보통 구간 합, 최대/최소값, 특정 패턴 탐색 같은 문제에서 많이 사용하며,매번 새로 합이나 조건을 계산하지 않고, 앞에서 빠지는 값은 빼고 새로 들어오는 값만 더해서 효율적으로 계산한다. 예시를 들어보자면 배열 arr[N] 이 있다고 가정해보자, 이때 구간 3개중 최대 값을 구하려고 한다. 가장 좌측 부터 3개를 더한다. 즉, arr[0]+arr[1]+arr[2]를 사용할 것이다. 다음은 한칸씩 밀리는데 이때중복되는 구간이 arr[1]+arr[2] 부분이다.이 계산을 중복방지하.. [백준] 1260. DFS와 BFS - JAVA 문제 풀이 해당 문제는 DFS와 BFS 문제로 그래프를 이용하여 푸는 문제이다. DFS는 깊이를 우선으로 노드를 방문하여 탐색하기 위해서재귀함수 즉, 자식의 노드로 다시 함수를 호출하여 깊게 파고 들어가는 방법을 사용한다. BFS는 넓이를 우선으로 노드를 방문하여 탐색하기 위해서큐를 이용하여 인접한 노드를 방문하는 방법을 사용한다. 코드 import java.io.*;import java.util.*;public class Main{ static boolean[] dvisited; static boolean[] bvisited; static ArrayListInteger>[] graph; static ArrayListInteger>[] bgraph; public st.. [백준] 1966. 프린터 큐 - JAVA 문제 풀이 선입선출 구조인 큐를 이용한다.이때 큐에다가는 배열을 삽입해서 사용해야한다.Queue q = new LinkedList();가 있을때 q안에는 배열의 형태로 넣어줘야한다.큐에는 {인덱스, 우선순위} 가 두 개 모두 들어가야 하기 때문이다.그래서 큐에 배열을 넣기 위해서는q.offer(new Integer[]{인덱스, 우선순위}); 처럼 사용해야 배열의 형태로 넣을수가 있다.이 점을 활용하여, 앞에서부터 선택정렬을 통해 더 큰 값이 있다면,맨 뒤로 보내고, 더 큰 값이 없다면,count값 증가와 함께 큐에서 삭제시켜주었다. 코드 import java.io.*;import java.util.*; public class Main{ public static void main(String[] .. 이전 1 2 다음
