infobox503 님의 블로그

문제 유형구현문제 접근답각 인원이 가지는 돈주어지는 정보인원 100,000자식, 부모 관계소득이 발생하는 대상후보완전탐색부적합분기점에 따른 경우의 수가 나눠지지 않기 때문에 부적합구현적합n*n = 1억 연산(전체 인원) * (각 인원으로 인해 발생하는 최대 연산량)⇒ 문제에서 주어지는 설명을 그대로 따라해서 코드를 구성해도 연산량 초과X전체 코드import java.util.*;class Node{ public String parent; public String name; public int value; public Node(String parent, String name){ this.parent = parent; this.name = name; ..

문법SELECT출력할 열 선택FROM테이블 선택GROUP BY같은 값의 행끼리 그룹화그룹화된 행 중에서 출력되는 값은 순서상 제일 먼저 위치해있는 행 값임SELECT *FROM PLACESGROUP BY HOST_IDHOST_ID100200100-------HOST_ID100200  WHERE, HAVING조건문WHEREGROUP BY 이전 테이블에 대한 조건문 지정# HOST_ID = 5507453인 데이터 개수 출력SELECT count(*)FROM PLACESWHERE HOST_ID = 5507453 HAVINGGROUP BY 이후 테이블에 대한 조건문 지정# HOST_ID = 760849인 데이터 개수 출력SELECT count(*)FROM PLACESGROUP BY HOST_IDHAVING HO..

문제 유형완전탐색문제 접근답열쇠가 자물쇠의 빈곳을 모두 채우면 true, 아니면 false 반환주어지는 정보열쇠 크기 m(m ≤ 20)자물쇠 크기 n (n ≤ 20)홈 0, 돌기 1후보완전탐색적합추정 연산 횟수 : (20204)(2020 + 20*20) = 1,280,000열쇠 4회전 * (자물쇠의 모든 좌표와 매칭 + 자물쇠의 빈 곳이 모두 없어지는 지 확인)⇒ 안정적인 연산 횟수로, 완전탐색 적합설명열쇠 회전key의 좌표를 읽는 시작 위치를 다르게 하면 90*n도 회전이 가능함예시(90도 회전)y=0, x=0부터 읽는게 아닌, x=0, y=n-1부터 읽는 것//90도 회전for(int x = 0; x= 0; y--){ rotateBoard[i][j] = (board[y][x] == 1) ..

문제 유형시뮬레이션문제 접근답기둥, 보 건설/철거에대한 결과물주어지는 정보Map 최대 크기 10,000건설, 철거 명령 최대 1000후보완전탐색적합X경우의 수 탐색을 의도한 문제가 아님문제에서 요구하는 조건만 채워도 답을 구할 수 있기 때문시뮬레이션적합문제에서 요구하는 조건을 지키기만해도 답을 유추 가능설명문제에서 요구하는 조건기둥은 바닥 위에 있거나 보의 한쪽 끝 부분 위에 있거나, 또는 다른 기둥 위에 있어야 합니다.public boolean checkColumn(int y, int x){ //바닥 if(y == 0){ return true; } //아래에 기둥 존재 else if(y-1 >= 0 && columns[y-1][x] == true){ ..

문제 유형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..