infobox503 님의 블로그

문제 유형그리디문제 접근답최대한 작은 건물 배열주어지는 정보건물 개수 : 최대 100,000 (N)양 옆에서 보이는 건물의 개수 : 최대 100,000 (a, b)정보 정리최대 연산은 N^2 미만이어야한다N^2 = 10,000,000,000⇒ 완전 탐색 X(시뮬레이션, BFS, DFS 등은 사용못할 가능성이 큼)남는 예상 후보DPNo문제와 DP간의 연관 관계를 찾을 수 없음이분 탐색가능은 할 것 같음배열을 각각 반으로 재귀적으로 나눠서 값을 채워넣는 방법을 예상함하지만 적합하지 않음값을 찾는 알고리즘이므로, 배열을 만드는 것과는 별 상관이 없음그리디적합최대한 적은 높이의 빌딩을 채워나가야한다.높이 1부터 시작하여 빌딩을 채워나갈 수 있을 것으로 예상된다.풀이List BuildList = new Linke..

백준 4179 JAVA문제 유형BFS문제 접근답Jihun의 최소 탈출 시간주어지는 정보map의 크기 1,000,000 (R*C)움직이는 대상Jihun 1명Fire 최대 999,999정보 정리Jihun과 Fire의 최대 연산 시간최대 8,000,000Jihun 1명, Fire 1개로 가정Jihun 1명(R*C) * 4(4방향 move)Fire 1곳(R*C) * 4(4방향 move)총합 ((R*C) * 4) * 2⇒ 시뮬레이션 가능⇒ “최소” 탈출 시간이니 BFS 사용이 적절풀이Jihun이 BFS로 1턴 움직임Fire가 BFS로 1턴 움직임이 과정을 반복import java.util.*;import java.io.*;class XY{ public int y,x; public XY(int y, in..

문제 유형완전 탐색문제 설명map의 크기 N*M트램펄린의 크기 L*LK개의 별똥별 x,y 좌표가 주어짐트램펄린의 범위 안에 별똥별이 포함될 시, 별똥별은 삭제됨문제 접근답트램펄린이 막아내지 못한 별똥별 개수주어지는 정보별똥별 최대 개수 100개정보 정리A 별똥별을 트램펄린 시작지점의 x 좌표로 지정B 별똥별을 트램펄린 시작지점의 y 좌표로 지정K*K = 최대 10,000트램펄린 안에 별똥별이 몇개 들어가는지 확인연산 최대 100총합10,000*100 = 1,000,000⇒1초 미만이므로 완전탐색 가능풀이 Why)왜 A, B 별똥별로 트램펄린의 시작지점을 정하는가?우리는 최대한 많이 모여있는 별똥별 위치에 트램펄린을 배치해야 한다.                         그렇다면, 우리는 최대한 바깥쪽..

문제 유형완전 탐색문제 접근답집-치킨집끼리의 최소 거리 총합주어지는 정보맵 최대 크기 2500(N*N)치킨집 배치 최대 개수 13(M)집 최대 개수100(2N)정보 정리치킨집 조합 최대 개수 1716 (13 C 7)치킨집과 집 사이 거리 비교 13100 (M2N)총합1716 * (13*100) = 2230800⇒1초 미만이므로 완전탐색 가능풀이ChickenList치킨집 XY 좌표 모음집HoustList집 XY 좌표 모음집Combination()M개수에 맞게 치킨집 조합 만드는 함수resolve()치킨집 조합 모음집 집 사이의 거리 총합 계산resolve()함수 호출 시마다 나오는 거리 총합 값이 제일 낮은 것을 답으로 출력import java.util.*;import java.io.*;class XY{ ..

문제 유형시뮬레이션문제 접근답1번 상어만 살아남는데 걸리는 시간주어지는 정보상어 개수 400시행 횟수에 따른 상어 움직임 1칸시행 횟수 1000번 제한⇒ 완전탐색 가능⇒시뮬레이션 가능 import java.util.*;import java.io.*;class Shark{ public int y,x; public int[][] command; public boolean live = true; public int way; public Shark(int y,int x) { this.y = y; this.x = x; } public void Command(int[][] command) { this.command ..

문제 유형시뮬레이션, BFS문제 접근답오토 플레이 종료 시, 포인트 총합주어지는 정보맵 크기 400가장 큰 블록 그룹 찾기약 400임의의 x, y좌표에 대한 bfs 탐색탐색했던 대상은 전부 방문 처리함으로써, 최대 연산 크기는 맵 크기와 비례됨가장 큰 블록 제거최대 400중력 작용약 400회전400총합 연산200 * (400 + 400 + 400 + 400 + 400) = 최대 400,000 미만으로 예상(블록 그룹의 최대 크기가 2일때 시행 횟수) * (가장 큰 그룹 찾기 + 대상 블록 제거 + 중력 + 회전 + 중력)⇒ 완전탐색 가능⇒시뮬레이션 가능import java.util.*;import java.io.*;class Block{ public int y,x,color,cnt,rainbowCn..

문제 유형시뮬레이션문제 접근답한 줄이 제거된 횟수블록 배치가 끝난 후에 녹색, 파랑 타일 개수주어지는 정보블록을 놓는 회수 10,000판의 크기64 + 46 = 48⇒ 완전탐색 가능⇒시뮬레이션 가능import java.util.*;import java.io.*;public class Main { public static boolean[][] BlueMap = new boolean[4][6]; public static boolean[][] GreenMap = new boolean[6][4]; public static void BlueInsert(int t, int y, int x) { if(t == 1) { for(int i = 1;..

문제 유형시뮬레이션문제 접근답말이 4개 이상 겹칠 때까지 걸리는 시간주어지는 정보말 개수 10개말을 움직이는 최대 회수 1000⇒ 시뮬레이션 가능주의점Listlistlist에서 꺼낸 객체 a⇒ 이 2개는 모두 같은 장소를 고유함(따라서, 값이 바뀌면 서로에게 다 적용됨)import java.util.*;class A{ public int a = 10;}public class HelloWorld { public static void main(String[] args) { Listlist = new ArrayList(); list.add(new A()); A a = list.get(0); a.a = 99; ..

문제 유형시뮬레이션문제 접근답T초 후에 먼지의 총량주어지는 정보맵 크기 R*C = 2500T초 = 1000예상 연산 횟수12,500,000(2500+(2500*4))*1000((T-1초 먼지 복사) + (먼지 퍼뜨리기)) * T초⇒ 시뮬레이션 가능예상 메모리 크기30MB1000250012byteT초 * T-1초 먼지 복사 * 먼지의 x,y,크기import java.util.*;import java.io.*;class Dust{ public int y,x,value; public Dust(int y, int x, int value) { this.y = y; this.x = x; this.value = value; }}class AirClea..

문제 유형BFS, 조합문제 접근답바이러스가 빈 공간을 채우는 최소 시간주어지는 정보바이러스는 10개 중 n개를 선택최대 경우의 수 252(= 10 C 5)맵 크기 2500 (N*N)예상 연산 횟수1,260,000(바이러스 선택 경우의 수) * (바이러스 퍼트림 + 연산 후, 맵에 빈 공간이 없는지 확인)252 * (2500 + 2500)⇒ 완전 탐색 가능BFS vs DFSBFS로 알고리즘을 짜야한다.답은 최소 시간을 구하는 문제이므로, DFS는 적합X주의사항메모리 초과BFS함수에 방문 기록을 저장하는 배열을 쓰면 안된다.시간 초과조합 함수를 만들 때, 최대한 효율적인 알고리즘을 사용해야 한다 import java.util.*;import java.io.*;//combination//bfsclass Vir..