infobox503 님의 블로그

문제 유형누적합 알고리즘문제 접근답살아남은 건물 개수주어지는 정보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; ..

문제 유형시뮬레이션문제 접근답정육면체 주사위를 만들 수 있는 지 검사주어지는 정보주사위 3개 정보후보완전탐색가능할 것이라 생각됨주사위의 정보는 3개이므로, 그에 따른 모든 경우의 수 탐색으로도 시간복잡도가 크게 늘어나지는 않음하지만 방법을 찾지 못함시뮬레이션가능주사위를 굴린다고 생각하고 시뮬레이션을 구현가능풀이목적주어진 주사위를 정육면체 주사위로 만들어보자방법입력 주사위가 위 사진 모양 틀에 들어갈 수 있는지를 확인한다.해당 틀을 왼, 오, 위, 아래 방향으로 굴려가면서 입력값이 1일때 해당 틀 위치를 true로 채운다.주사위의 빈 곳이 없다면 입력 주사위는 정육면체 모양을 만들 수 있다.  import java.util.*;import java.io.*;class XY{ public int y,x..

문제 유형시뮬레이션 + BFS문제 접근답물을 뿌릴 때 만들어지는 웅덩이의 용량주어지는 정보맵 크기 최대 2500 (N * M)땅의 높낮이 1~9후보완전탐색가능맵의 크기와 땅의 높낮이가 충분히 작음따라서, 문제 설명 그대로 시뮬레이션을 만드는 게 좋을 듯함풀이(BFS)맵의 제일 낮은 땅, 높은 땅을 구한다.제일 낮은 땅들에 +1만큼의 물을 뿌린다.물을 뿌리고 난 후에 웅덩이가 형성될 시, 정답에 더한다.제일 높은 땅만큼 될 때까지 2번 과정에서부터 물을 +1 뿌린다.주의BFS()에서 웅덩이가 형성되지 않더라도, 물을 뿌려야한다(물을 뿌릴 수 있는 땅 한정).물을 뿌리지 않을 시, 물로 인해 높아진 땅이 벽처럼 형성돼서 새로운 웅덩이가 생길 수 있다.이는 가짜 웅덩이므로 count되면 안된다.//맞는 접근b..

문제 유형유니온 파인드 or 완전 탐색문제 접근답친구끼리 묶었을 때 팀의 개수주어지는 정보학생 수 최대 1000 (n)학생 간의 인간관계 정보 최대 5000 (m)후보완전탐색가능학생의 수가 충분히 작음완전탐색을 통한 n*n 연산을 시도했을 때, 시간 복잡도를 넘지 않음유니온 파인드적합1번의 친구가 2번이고, 2번의 친구가 3번이라고 하자.이 경우, 완전 탐색으로 1,2,3번의 친구 리스트를 전부 탐색하는 것도 된다.하지만 유니온 파인드를 통해, 1, 2, 3번의 최종 친구를 정해놓으면 더 빨리 팀 개수를 구할 수 있다.풀이(유니온 파인드)목적팀 개수를 구한다.단계자료구조List[] FList;친구 명단을 기록한다.a, b가 친구라면FList[a].add(b)FList[b].add(a)List[] ELis..

문제 유형시뮬레이션문제 접근답치즈가 전부 녹기까지 걸리는 시간주어지는 정보맵 크기 최대 10000 (N*M)맨 바깥 테두리는 치즈가 들어올 수 없다.치즈 = 1, 여백 = 0후보시뮬레이션가능이유맵이 충분히 작음각 시간마다 치즈에 대한 시행 횟수는 최대 (N*M)*2번 정도 밖에 되지 않음(문제에서 주어지는 대로 연산을 진행할 시)풀이목적치즈가 녹기까지 걸리는 시간을 구하자단계자료구조int[][] map문제에서 주어지는 치즈 맵을 기록한다.int[][] copyMap치즈 녹이기 연산마다 map을 복사한다boolean[][] visited바깥 공기에서부터 치즈의 접촉 시, true로 체크한다함수bfs()녹을 치즈가 없으면 true를 반환한다.단계map을 copyMap에 복사한다copyMap에 0,0 좌표부터..

문제 유형트리문제 접근답후위 순회 출력주어지는 정보트리 노드 개수 최대 1000이진 트리알고리즘 후보없음전위, 중위 순회로 트리의 모양을 유추 할 수 있는지를 묻는 문제 같음풀이목적후위 순회 출력필요 지식전위, 중위로 트리 모양 유추전위 순회와 후위 순회가 주어졌다전위 순회의 첫번째 인덱스 값은 a이다.중위 순회의 A번째 인덱스 값은 a이다.이때, 중위 순회의 1~A-1 인덱스의 값은 a의 왼쪽 자식이다.중의 순회의 A+1~N(마지막 인덱스) 인덱스의 값은 a의 오른쪽 자식이다.함수printTree(int preIdx, int s, int e)후위 순회 출력 함수단계재귀적으로 루트 노드부터 왼쪽 자식→오른쪽 자식 순으로 탐색한다.맨 마지막으로 탐색된 노드부터 출력한다.출력 결과는 후위 순회와 같다. im..

문제 유형완전 탐색 + BFS문제 접근답길을 건너야만 만날 수 있는 소의 쌍 수주어지는 정보맵 크기 최대 10000 (N*N)소 개수 최대 100 (K)후보완전탐색가능N, K가 충분히 작으므로 시간 초과는 없을 것으로 예상⇒ BFS를 통해 완전탐색 시행풀이목적BFS 탐색으로 다리를 건너야만 만날 수 있는 소를 카운팅한다.단계자료구조Cow[i] cowList;i번째로 입력된 소의 좌표를 등록한다.int[y][x] map;(y,x) 좌표의 소의 i 번호를 적는다.boolean[][][][] bridge;(y,x) → (y’,x’) 좌표로 이어지는 다리를 true로 등록Q) 배열이 커서 시간 초과가 일어나지 않나?일어나지 않는다100^4 byte = 100MB함수bfs()소를 순서대로 뽑아서 Map 전체를 탐..