infobox503 님의 블로그

문제 유형시뮬레이션문제 접근답말 4개 이상을 쌓기위한 시행 횟수주어지는 정보맵 크기 최대 144 (N*N)말 개수 최대 10 (K)시행 횟수 최대 1000후보시뮬레이션가능말 개수가 최대 10개이고, 시행 횟수는 최대 1000이다.시행 횟수에 따른 말 이동 횟수가 충분히 적으므로, 시뮬레이션 가능풀이목적만들 수 있는 괄호 조합을 모두 구하여, 최대값을 선정한다.단계자료구조int[][] colorMapmap의 color 색깔 지정int[][][] chessMapmap의 말의 개수를 표시하기 위한 배열map[y][x][h] = idx(y,x) 좌표의 h 높이에는 idx번째 체스가 존재한다.Chess[idx] chessList체스 좌표를 표시하는 리스트(idx번째 체스 표시)함수moveChess()체스의 방향을..

문제 유형완전탐색문제 접근답식이 주어졌을 때, 괄호 조합으로 만들 수 있는 최대값주어지는 정보수식의 길이 최대 19 (N)식에서 쓰이는 숫자의 길이는 1자리후보완전 탐색가능수식의 길이 N은 충분히 작기 때문에 완전 탐색 가능풀이목적만들 수 있는 괄호 조합을 모두 구하여, 최대값을 선정한다.단계식은 모두 char 배열에 담는다식에서 주어지는 숫자의 길이는 1자리 수 이기 때문에 char 배열은 적합하다DFS 탐색으로 모든 경우의 수를 탐색한다선택지해당 자리의 수를 total 값에 포함한다.해당 자리의 수와 그 다음 자리의 수를 괄호로 묶어서 total 값에 포함한다최대값을 선정한다. import java.util.*;import java.io.*;class Main { static int N; ..

문제 유형완전탐색 + BFS + 다익스트라문제 접근답모든 섬을 연결하기 위한 다리 길이 최소값주어지는 정보맵 크기 최대 100(N * M)섬 개수 최대 6후보완전 탐색가능맵 크기가 현저히 작으므로, 시간 초과를 걱정하지 않아도 됨.⇒ BFS, DFS 사용 가능⇒ DP, 이분 탐색 등등 시간을 아끼기 위한 알고리즘 사용X다익스트라다소 적합다리 길이의 최소 값을 구하므로, 최소 신장 트리를 구해야함따라서, 다익스트라 알고리즘으로 최소 신장 트리 구성 가능다만, 크루스칼(간선 기준 최소신장 트리 구성) 알고리즘 보다는 적합성이 떨어짐풀이목적주어진 맵을 최소 신장 트리로 구성하여, 최소 다리 길이를 구하자단계각각의 섬을 구분하자완전탐색 + BFS섬을 마주할 시, BFS 탐색으로 해당 섬을 전부 탐색한다.탐색된 ..

문제 유형다익스트라문제 접근답1번→N번 지역으로 이동하기 위해서 걸리는 시간(분 단위)주어지는 정보지역 최대 100,000 (N)횡단 보도 최대 700,000 (M)후보완전 탐색N*N 시간 초과 이므로 불가다익스트라1→N에 대한 최단 거리를 구하므로 적합풀이다익스트라 알고리즘으로 1번 지역과 가장 가까운 v[a] 지역을 방문했다고 하자.a 지역 → 2~N 지역에 대한 최단 거리 갱신 방법은?//target = a 지역//dis = 방문 지역이 초록불이 되는 시간//if : 초록불이 끝난 다음에 a번 지역에서 b 지역으로 가려는 경우if(v[target]%M >= dis){ comp = v[target] + (dis + (M-v[target]%M));}//else : 초록불이 지나기 전에 a번 지역에..

문제 유형다익스트라문제 접근답A 마을→ 도착 마을→A 마을에 대한 최단 거리 중, 최대 값A : 임의의 한 마을주어지는 정보마을 개수 최대 1,000 (N)길 개수 최대 10,000 (M)후보최단 거리를 구하므로, 최단 거리 알고리즘을 선택지로 두는게 맞는 듯함(다익스트라, Prim 등등)다익스트라도착 마을을 X라 하자.X 마을 → 시작 마을에 대한 다익스트라X 마을 ← 시작 마을에 대한 다익스트라총 (N*N)*2 = 2,000,000import java.util.*;import java.io.*;public class Main { static int N,M,X; static int MAX = 1000000; public static int[] resolve(int s, int[][] m..

문제 유형그리디 + 우선순위 큐문제 접근답각 가방에 넣을 수 있는 보석 가치 총합주어지는 정보보석, 가방의 최대 개수 300,000 (N, K)보석의 최대 무게, 가치 1,000,000(M, V)가방의 최대 무게 100,000,000(C)후보완전 탐색불가능보석과 가방을 전부 비교N*K = 90,000,000,000그리디가능방법최대한의 가치를 가지는 보석을 먼저 넣는다.가방에 들어가지 않으면 버린다.이분 탐색시도했지만 실패이분 탐색으로 보석 무게와 근접한 가방 무게를 찾을 수 있음하지만 보석이 들어가있는 가방이 여러개일 시, 선형 탐색이 되므로 시간 초과DP부적합보석, 가방으로 주어지는 값은 규칙성이 없으므로 DP로 안됨우선순위 큐가능https://steady-coding.tistory.com/56풀이정렬..

문제 유형DP문제 접근답A~B 사이의 값을 이진수로 만들어서 얻을 수 있는 1의 개수 총합주어지는 정보A, B 의 최대 크기 10^16정보 정리숫자 최대 크기 10^16순차 탐색 불가능logN의 알고리즘을 사용해야 함후보이진 탐색A, B 사이 숫자들의 1의 개수를 전부 알아야하므로 부적합DP적합이진수는 자릿수가 올라갈 때마다 2의 지수만큼 커지는 규칙성을 가짐해당 규칙성을 이용하여, n자리수의 이진수가 가지는 1의 개수 총합을 dp로 나타낼 수 있다참고https://tussle.tistory.com/1022풀이dp[n]1~n 자리수의 이진수가 가질 수 있는 이진수 값 종류에서 1의 개수를 전부 더함dp[n] = dp[n-1] * (2^(n-1))resolve(long N)return : 0~N의 값에 대..

문제 유형DP문제 접근답N,M 좌표로 도착했을 때, 최대 가치 얻기주어지는 정보Map 최대 크기 1,000,000 (N*M)각 좌표의 가치 -100 ~ 100Move는 오른쪽, 왼쪽, 아래 방향만 가능정보 정리완전 탐색시도했으나 실패남는 후보그리디 : 불가능인접한 좌표에 대한 최선의 값을 찾을 시, 최대값은 구할 수 없음DP : 가능https://velog.io/@mong7399/java-2169번-로봇-조종하기DPMove의 방향이 오른쪽, 아래, 왼쪽만 가능하다는 것을 응용한다이동 지점에 대해서, 1, 2번 방향 중 더 높은 값을 저장한다 temp[0][0] = dp[i-1][0] + map[i][0];for(int j = 1; j     2. 이동 지점에 대해서, 1, 2번 방향 중 더 높은 값을 저..

문제 유형DP문제 접근답주어진 돈으로 반반씩 나눠가질 수 있는 지의 여부주어지는 정보시행 횟수 3번동전 종류 100(N)금액의 총합 최대 100,000정보 정리완전 탐색 : 불가능돈의 모든 조합 구하기 = 100!남는 예상 후보그리디 : 불가능가능한 동전의 모든 조합을 만들어야 답을 구할 수 있음DP : 가능만들 수 있는 조합을 배열에 저장하면 가능성 있을 듯함DP주어진 각 동전을 방문 표시한다boolean[] visited = new boolean[100001];for(int i = 0; i - 돈의 총합이 홀수이면 반 쪼개기 불가능(돈은 모두 자연수라는 조건이 있음)if(total % 2 == 1){ System.out.println(0); return;}- 자기 자신의 동전을 제외한 모든..

문제 유형자료 구조(스택)문제 접근답현재 빌딩에서 보이는 빌딩 개수와 가장 가까운 빌딩 위치주어지는 정보건물 개수 : 최대 100,000 (N)건물 높이 : 최대 100,000 (L)정보 정리최대 연산은 N^2 미만이어야한다N^2 = 10,000,000,000⇒ 완전 탐색 X(시뮬레이션, BFS, DFS 등은 사용못할 가능성이 큼)남는 예상 후보DP가능할 거라 여겼으나, 실패내가 실패한 이유코드로 짜기 복잡함DP[current]의 값을 구하기 위해, DP[current-1]의 값 등을 이용해야 함하지만 DP[current-1]이 가지는 자신과 제일 가까운 빌딩 위치 a가 존재할 때,DP[currnet] → DP[current-1] → a 순의 단계를 거쳐서 DP[current]와 가장 가까운 빌딩을 유추..