완전탐색5

• 

  백준 - A와B2 문제 설명 A⇒ B로 바꿀수 있는지 가능여부를 물어보는 문제이다. 주의사항 완전탐색 시간복잡도를 측정해봐야한다. 50의 길이 시도 완전탐색 FAIL 백트래킹만들어질 수 없는 경우는 탐색하지 않도록 한다. 일반 완전탐색은 2^50까지 나온다. 풀이 - [덱을 이용한 풀이] 문자를 추가하는 것은 괜찮다 하지만 뒤집고 뒤집고 .. 이런행위가 시간초과에 영향을 줄 수 있다고 생각했기 때문에 사용하지 않았다. static boolean isPossible = false; public static boolean isChange(String A, String B) { LinkedList results = new LinkedList(); for (char c : A.toCharArray()) { results.offe.. Algorithm/백준 2023. 4. 5.

• 

  백준 - 부분 삼각 수열 문제 설명 길이가 N인 배열이 주어진다. 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오. 삼각 수열이란 a[0], a[1] …. a[n-1]의 배열에서 b[i], b[j], b[k]가 삼각 관계에 있으면 삼각 수열이다. 삼각 관계는 세개의 수가 x+y>z, x+z>y, y+z>x 관게를 만족하는 관계이다. 문제이해가 중요하다. 원본 배열에서 일부를 뽑아 부분수열을 만들고 삼각 부분 수열의 최대길이를 구하는 문제이다. 삼각 관계를 보면 세 수를 정하고 세수가 위 조건의 상하 관계를 만족하는 것을 볼때, b[k]는 가장 큰 숫자이고 b[i]는 가장 작은 숫자로 본다. 이를 보면 정렬이 생각나야 된다. n=7, arr[]=[2,3,4,1,3,4,5] 일때, 답은 5가 나온다. 만약 중간에 다른 수들이 .. Algorithm/백준 2023. 4. 4.

• 

  백준 - 제곱수 찾기 문제 설명 N행 M열의 배열이 주어지고 서로 다른 2개 이상의 칸은 선택하여 만들 수 있는 수중 가장 큰 완전 제곱수를 구하는 문제이다. 서로 다른 2개 이상의 칸을 선택하기 위해서는 행의 번호가 순서대로 등차 수열을 이루고 있어햐 하고 열의 번호도 선택한 순서대로 등차 수열을 이루고 있어야 한다. 주의사항 서로 다른 2개 이상의 칸을 탐색하기 위한 문제 이해가 중요하다. 행의 번호가 순서대로 등차 수열을 이루고 있어야 한다. 열의 번호도 동일하다. 나는 처음에 값이 등차수열을 이루어야 한다고 착각했다. 그것이 아니라 인덱스 간격이 등차수열을 이루어야 한다는 이야기이다. 즉 행에 대해 +2칸 이면 (0,0) → (2,0) → (4,0) → (n-2,0) 까지 등차수열의 간격을 이루고 탐색한 칸의 값을 모.. Algorithm/백준 2023. 4. 2.

• 

  백준 - 호석이 두 마리 치킨 문제 설명 치킨집 두곳을 차리는데, 모든 건물에서 가장 가까운 거리에 있는 곳에 치킨집을 차린다. 주의사항 간선의 개수 M의 범위 생각한 아이디어 플로이드 워셜을 이용하여 거리 측정하고 각 최소 거리를 구한다. 풀이 static final int INF = (int)1e9; static int n, m; static int[] picks = new int[2]; private static int[][] edges; static int roundTripAnswer = INF; static int[] chickensAnswer; /** * 모든 건물에서 접근성이 가장 좋은 치킨집 2곳을 선정하고 거리를 측정하라 */ public static void main(String[] args) throws IOExc.. Algorithm/백준 2023. 3. 27.

• 

  백준 - 종이조각 문제 설명 2차원 배열이 주어진다. 2차원 배열을 적절히 조각내어 자르고 만들 수 있는 최댓값을 출력한다. 같은 경계에 있으면 숫자를 이어붙이고 다른 경계에 있는 숫자는 더한다. 시도 가로로 붙일지, 세로로 붙일지 2가지의 선택한다. 풀이 static int n, m, answer; static int[][] paper; static boolean[][] v; public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(reader.readLine(.. Algorithm/백준 2023. 3. 24.