알고있니

문제https://www.acmicpc.net/problem/12015  입출력610 20 10 30 20 504 아이디어 - 증가하는 부분 수열을 유지하는 배열 LIS + 이분탐색 1) A[i] 가 LIS 배열의 마지막 원소보다 크면 추가2) 아니라면 이분 탐색을 통해 교체할 위치를 찾아 값 교체  - 이분 탐색으로 O(NlogN) 내에 해결하기// 개선이 필요한 로직for (int i = 0; i  - Collections.binarySearch() 리스트에 값이 존재하면 → 해당 값의 인덱스(index)를 반환리스트에 값이 존재하지 않으면 → 값이 들어갈 "삽입 위치(insertion point)" 를 -(insertion point) - 1로 반환  코드 값이 없다면, - (들어갈 위치 - 1) ..

문제https://www.acmicpc.net/problem/14002   입출력 610 20 10 30 20 50410 20 30 50아이디어 - 가장 긴 증가하는 부분 수열 길이 구하기 - 가장 긴 증가하는 부분 수열 구하기 (parent 배열로 어떤 곳에서 왔는지 저장해 둔다) 코드  import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int N; static int[] arr; public static void main(String[] args) throws Exception { Buff..

문제https://www.acmicpc.net/problem/11054 입출력101 5 2 1 4 3 4 5 2 17아이디어 - 증가하다가 감소하는 부분 수열 1) 증가하는 부분 수열 최대 길이 LIS // 왼쪽 부터 2) 감소하는 부분 수열 최대 길이 LDS // 오른쪽부터   코드 import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class Main { static int N; // 수열A의 크기 static int[] arr; // 수열 public static void main(String[] args) throws Exc..

문제https://www.acmicpc.net/problem/11057  입출력- 입출력110아이디어DP // i번째자리까지 고려하여 j(0-9중)를 택했을 때 갯수 코드  import java.io.BufferedReader;import java.io.InputStreamReader;public class Main { static int N; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); N = Integer.parseInt(br.readLine()); // 자리가 오름차순을 이루는 수, 인접한 수가 같아도 오..

문제https://www.codetree.ai/ko/trails/complete/curated-cards/challenge-the-sum-of-the-subsequences/  입출력   아이디어  N개의 원소 A 내 부분 수열의 합이 M이 되는 경우가 있는지 판단 DP[i][j] : i번째 원소까지 고려할 때 부분 수열의 합이 j가 될 수 있음1) 부분 수열에 포함시키는 경우2) 포함시키지 않는 경우 코드  import java.io.*;import java.util.*;public class Main { static int N, M; static int[] arr; public static void main(String[] args) throws Exception { Bu..

문제https://www.acmicpc.net/problem/17837   입출력4 40 0 2 00 0 1 00 0 1 20 2 0 02 1 13 2 32 2 14 1 2 -1아이디어subList 사용할 때 new ArrayList()로 생성하자    코드  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Collections;import java.util.HashMap;import java.util.List;import java.util.Map;import java.util.StringTokenizer;publi..

문제https://www.acmicpc.net/problem/19238   입출력   아이디어 - 시뮬레이션1. bfs로 택시 현재 위치에서 가장 가까운 거리에 있는 손님 찾기 2. 그 위치로 택시를 옮기고 사람을 옮기는 로직 수행 (이때 연료 확인) 코드    import java.io.*;import java.util.*;public class Main { static int N, M, fuel; static int[][] box; static int[][] personToId; static int[] car; static int[][] routes; static final int INF = Integer.MAX_VALUE; static int[][] way = ..

문제https://www.acmicpc.net/problem/17135   입출력   아이디어M개의 열 중 3개 궁수 위치 선택 시뮬레이션 진행 1) N번의 턴을 진행하여 적들이 아래로 내려옴 (적이 성에 오면 게임이 끝난다 이런 말이 없으므로 무조건 N번 진행)2) 궁수가 공격할 적 찾기 (여러 궁수가 동일한 적을 공격할 수 있음)3) 적 제거  + 개수 세기 4) 적 이동   코드  import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util...

문제https://www.acmicpc.net/problem/1043   입출력 4 302 1 21 33 2 3 43아이디어파티 참여한 사람들을 그룹지어 하나의 그룹으로 취급하고진실을 알고있는 사람들도 하나의 그룹으로 취급한 뒤 파티 참석 가능 여부를 확인하기 위해 파티 i에 참석한 사람의 그룹장 == 진실을 알고 있는 사람의 그룹장 확인    코드  import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Main { static int N, M; // 사람의 수, 파티의 수 ht..

문제https://www.acmicpc.net/problem/1261  입출력3 30111111103 아이디어 - 가중치가 0 또는 1인 미로에서 최소한의 벽(1)을 부수고 목표 지점까지 가는 최단 경로를 찾는 문제1) 벽 부수는 행위 = 가중치 12) 최소 비용 갱신  코드  import java.io.BufferedReader;import java.io.InputStreamReader;import java.util.Arrays;import java.util.PriorityQueue;import java.util.StringTokenizer;public class Main { static int M, N; // 열, 행 static int[][] box; static int EMPTY = 0, WALL..