728x90 알고리즘 풀이7 [백준] [자바] 17144번 : 미세먼지 안녕! 문제 출처 www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 1. 풀이 접근 ㆍ 미세먼지 확산 ※ 미세먼지 확산 할 때 옆에 있는 칸이 서로 미세먼지가 있어도 각각이 확산되면서 서로 영향을 끼침 - 그래서 각각에 대한 값을 구한다음에 새로운 배열에 저장해서 보관하고 있다가 모든 프로세스가 끝나면 원래 배열에 덮어 씌우는 방식으로 해결 ㆍ 미세먼지 청정 - 입구에서부터 한칸씩 밀려서 회전 후 되돌아와 없어짐, 각각의 위치에 맞춰서 배열 회전 시킴 ※ 회전할 때.. 2021. 3. 29. [백준] [자바] 16236번 : 아기 상어 문제 출처 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1. 풀이 접근 ㆍ 현재 먹이를 먹을 수 있는지 확인 ( 먹이 못 먹을 경우 종료 후 시간 출력 ) ㆍ 현재 위치로 부터 가장 가까운 먹이 찾기 (BFS 탐색) - 나보다 큰 먹이는 지나가지 못함 ( 벽 같은 역할 ) - 나의 크기와 같거나 작으면 지나 갈 수 있음 ※ 물고기를 현재 크기 만큼 먹어야 크기 성장함. Ex. 상어 크기 3 -> 3번먹어야 4로 진화 ㆍ 가장 가까운 곳에 먹을 수 .. 2021. 3. 26. [백준] [자바] 16234번 : 인구 이동 문제 출처 www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 1. 풀이 접근 ㆍ 유니온으로 나눌 구역을 찾음. 이 때 기준은 서로의 차이가 L보다 크고 R보다 작아야 함. ※ 이 때 처음 찾는곳을 기준으로 DFS로 같은 구역을 지정해야 함. ㆍ 구역이 찾아지면 구역의 평균값을 구해서 같은 구역일 경우 값 덮어쓰기. ㆍ 더이상 반복 할 수 없을 때 까지 수행 2. 소스코드 github.com/Choi-JinYeong/Solve_Alg/tree/ma.. 2021. 3. 25. [백준] [자바] 15686번 : 치킨 배달 문제 출처 www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 1. 풀이 접근 ㆍ 치킨집 위치와 고객집들의 위치를 각각 저장 ㆍ 치킨집 개수 N 중 M개 만 남겼을 때의 경우의 수 추출 ( NCM의 조합 개수 만큼 나옴 ) ㆍ 각 고객집 위치에 따라 M개의 치킨집 중 가장 최소 거리 추출해서 배열에 쭉 저장 (이 배열은 각 고객집 인덱스와 매칭됌) ㆍ 각 고객집 최소거리값을 더해서 전체 최소값이랑 비교 후 출력 2. 소스코드 github.c.. 2021. 3. 23. [백준] [Java] 12865번 : 배낭 채우기 문제 1. 풀이 접근 gsmesie692.tistory.com/113 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 gsmesie692.tistory.com 혼자 풀다가 그리디도 써보고 DFS도 써봤는데 반례생기거나 시간초과 나길래 참고해서 문제 풀었음. 위에 분이 매우 상세하게 적어주셔서 출처로 밝힘 2. 소스코드 github.com/Choi-JinYeong/Solve_Alg/blob/master/Solve_Algs/src/BJ_12865/Main2.java Choi-JinYeo.. 2021. 3. 6. [백준] [Java] 14502번 : 연구소 출처 : www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 1. 풀이 접근 조합으로 벽 설치 할 수 있는 경우의 수 산출 벽 설치 후 바이러스 위치 기준으로 BFS 검색 이동 가능할 때마다 바이러스 숫자 2로 변경 더 이상 탐색 불가능 시 0 개수 산출 후 최대값 비교 2. 소스코드 github.com/Choi-JinYeong/Solve_Alg/tree/master/Solve_Algs/src/Sol_BJ_14502 Choi-JinYeong/Solve_Alg 알고리즘 풀이... 2021. 2. 18. [백준] [Java] 14500번 : 테트로미노 출처 : www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 1. 풀이 접근 테트로미노 5가지 모양에 따라 기준점으로 부터 검색할 곳으로 배열로 선언 (회전시 모양도 기준점으로부터 다 미리 작성해서 반영해둠) 기준점(모든 맵 좌표)에 따라서 넘어 가면서 검색하면서 맵 안에 있을 시 더함 ㅗ 모양은 기준점으로 가운데 기준점으로 부터 BFS로 확인, 나머지모양은 기준점으로부터 DFS로 확인 (맞는지 잘 모르겠음, 그냥 이동방향에 따라서 계속 탐색) 끝까지 다 탐색해.. 2021. 2. 17. 이전 1 다음 728x90
