infobox503 님의 블로그

문제 유형BFS + 시뮬레이션문제 접근답목적지 도달을 위한 최소 움직임 횟수주어지는 정보Map 최대 크기 10,000후보완전탐색적합X로봇이 움직이는 모든 경우의 수를 구하려면 O(N^2)이므로 시간 초과BFS적합최소 움직임 횟수이므로 BFS가 적합함설명로봇의 회전 구현//가로if(Math.abs(bot.x1 - bot.x2) == 1){ for(int i = 0; i 로봇의 이동 구현for(int i = 0; i   전체 코드import java.util.*;class Bot{ public int x1,y1; public int x2,y2; public int cnt; public Bot(int y1, int x1, int y2, int x2, int cnt){ ..

문제 유형완전탐색 + 순열문제 접근답모든 취약 지점을 검사하기 위한 최소 인력주어지는 정보모든 지점 최대 200(n)취약 지점 최대 15(weak)인력 최대 8(dist)후보완전탐색적합정보의 최대값이 충분히 작기 때문에 시도해볼만함설명순열 구하기취약 지점(weak)에 대한 순열 Weak인력(dist)에 대한 순열 distPer완전탐색Weak, distPer에 대한 모든 경우의 수 탐색⇒ 최소 인력을 추출 전체 코드import java.util.*;class Solution { int[] dist; int[][] Weak; int N; public int Brute(int[] weak, int[] dist){ int L = 0; int R = 0..

문제 유형최단 거리 알고리즘문제 접근답최소 택시 요금주어지는 정보목적지 개수 최대 200후보완전탐색불가능각 목적지에 따른 모든 경우의 수를 구한다고 하자대략 200!로 경우의 수가 구성되는데, 한참 초과됨dijkstra 알고리즘가능방법v[] : start 지점에 대한 최단 거리 구성curV[] : v 배열의 각 지점에 대해서 또 다시 최단 거리 구성v[i] + curV[a] + curV[b] 지점의 최소값을 return 전체 코드import java.util.*;class Node implements Comparator{ public int node,value; public Node(){ } public Node(int node, int value){ ..

문제 유형누적합문제 접근답제일 많은 시청자가 보기 위한 광고 시작 타임주어지는 정보영상 최대 길이 99:59:59시청자 수 최대 300,000후보완전탐색가능누적합을 써서 각 시간별 시청자 수를 배열로 기록해당 배열을 전부 훑으면서 시청자 수가 제일 많을 때를 찾아냄설명누적합int[] temp : 시청자의 시청 시작, 종료 시간을 표기int[] logsTime : 각 시간별 시청자의 총합을 표기public void setLogsTime(String[] logs){ logsTime = new int[MAX]; int[] temp = new int[MAX]; for(int i = 0; i  제일 시청자가 많이 보는 시작 시간 구하기public int getTimeLine(String a..

문제 유형완전탐색(순열 + BFS)문제 접근답카드 짝을 전부 맞추기 위해 필요한 최소 명령 횟수주어지는 정보맵 크기 최대 4*4(int[][] board]카드 개수 최대 7후보완전탐색가능맵 크기, 카드 개수가 충분히 작으므로 완전 탐색을 시도해 볼만함과정순열을 만든다(카드 짝을 맞추는 경우의 수 전부)⇒ dfs()각 순열에 맞는 최소 명령 횟수를 구한다⇒ bfs()import java.util.*;class Card{ public int num,y,x; public Card(int num,int y,int x){ this.num = num; this.y = y; this.x = x; } }class XY{ public int y,x;..

문제 유형완전탐색 + DFS문제 접근답양 최대 수주어지는 정보노드의 총 개수 17 (info)노드의 부모, 자식 연결 관계는 이차원 배열로 주어짐후보완전 탐색가능노드의 개수가 충분히 작으므로 시도해볼만함방법DFS를 통해 모든 노드를 탐색탐색한 노드에서 조건에 맞는 노드일 경우, 해당 노드를 재귀 방문 코드import java.util.*;class Solution { int N; int answer = 1; boolean[] visited; public void dfs(int[] info,int[][] edges, int sheep, int wolf){ answer = Math.max(sheep, answer); for(int[] edg..

문제 유형누적합 알고리즘문제 접근답살아남은 건물 개수주어지는 정보Map 최대 크기 1,000,000(N*M)건물에 대한 명령 개수 최대 250,000(K)후보완전 탐색불가능건물 1개마다 모든 명령을 적용하면 1,000,000*250,000으로 시간 초과누적합가능함모든 명령을 적용한 Command 배열을 만듦해당 배열을 최종 배열에 적용하면 시간 복잡도 N*M + K코드class Solution { int N,M; int[][] command; public void setCommand(int[][] board, int[][] skill){ command = new int[N+1][M+1]; for(int i = 0; i 0){ ..

문제 유형mini-max 알고리즘문제 접근답Winner, Looser 역할의 캐릭터가 최선의 선택을 했을 때 말의 이동횟수주어지는 정보제한시간 10초Map 최대 크기 25 (row * col)후보완전 탐색가능할 것으로 보임시간 자체가 너무 널널해서 최선의 선택에 대한 모든 경우를 찾으라는 뜻으로 해석됨해결 방법mini-max 알고리즘2 player를 기준으로 서로가 최선의 경우를 택했을 때 나오는 결과값 도출https://github.com/encrypted-def/kakao-blind-recruitment/blob/master/2022-blind/Q7.java코드 해석목적aloc이 이길 경우 : bloc이 최선을 다해서 버틴 이동 횟수에서 제일 작은 이동 횟수를 고름aloc이 질 경우 : bloc이 최..

문제 유형플로이드-위셜 알고리즘문제 접근답모든 행성 방문 최소 시간주어지는 정보맵 크기 최대 100 (N*N)행성 시작 지점(K)후보완전 탐색실패방문한 곳을 재방문 가능함. 따라서, 각 경우의 수마다 방문한 곳을 재방문 하면 무한 반복 발생해결 방법플로이드-와샬 알고리즘모든 정점에서 다른 정점으로의 최단 거리 갱신int[][] graph;static void floyd(int[][] graph){ for(int k = 0; k 시간 계산플로이드101010 = 1000플로이드로 구한 그래프에서 재귀 탐색(10-1)! = 362880총합363880 ⇒ 통과 코드import java.io.*;import java.util.*;class Main { static int N, K; static i..

문제 유형시뮬레이션문제 접근답N 기간이 지난 후, 애벌레 크기주어지는 정보맵 크기 최대 700*700(M * M)날짜 수 최대 1,000,000(N)후보시뮬레이션가능시간 복잡도3,490,001( = N3 + 2M + ((M-1)*(M-1))Growth 배열에서 1point, 2point 시작 지점++가장자리 왼쪽, 위쪽 배열 대상으로 Growth 배열을 이용해서 애벌레 최종 성장나머지 배열의 애벌레들 최종 성장값은 위쪽 좌표의 애벌레 성장 point로 지정(가장 많은 포인트를 지니는 애벌레들은 맨 위 오른쪽 상단의 애벌레이므로 가능함) import java.util.*;import java.io.*;class Main { static int N, M; static int[][] map; ..