본문 바로가기

Algorithm94

[알고리즘 문제풀이] 프로그래머스 - 등굣길 / JAVA(자바) https://programmers.co.kr/learn/courses/30/lessons/42898 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr /** 1. dp 풀이 2. 현재 좌표로 올수 있는건 위에서 오는거랑 왼쪽에서 오는 것 뿐. 3. 물웅덩이는 계산하지말고 패스할 것. **/ class Solution { public int solution(int m, int n, int[][] puddles) { int answer = 0; int[][] dp = new int[n+1][m+1]; .. 2022. 3. 22.
[알고리즘 문제풀이] 프로그래머스 - 디스크 컨트롤러 / JAVA(자바) https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr /** 1. 작업의 요청부터 종료까지 걸린 시간의 평균을 가장 줄이는 방법으로 평균 반환 1-1) 같은 시간에 요청중인 작업이 있다면 적은 작업시간부터 할 것!(sjf) 2. 현재 작업시작시간과 끝나는 시간을 표기해두고, 그안에 요청 들어온 작업들을 하나씩 처리하는 형태로 구현. 3. 우선순위큐에 요청시간 순 정렬해서 넣어두고, 그시간에 맞는 요청들을 하나.. 2022. 3. 21.
[알고리즘 문제풀이] 프로그래머스 - 전력망을 둘로 나누기 / JAVA(자바) https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 전력망을 둘로 나누기 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr /** 1. 정점 100 간선 99 2. 간선마다 끊어서 확인 3. 끊은 두 정점 체크함수 bfs 실행 4. 둘의 차이가 적은것으로 교체하며 정답 반환 **/ import java.util.*; class Solution { public ArrayList[] graph; public int solution(int n, int[][] wires) { int answ.. 2022. 3. 20.
[알고리즘 문제풀이] 백준 20188 등산 마니아 (JAVA코드) https://www.acmicpc.net/problem/20188 20188번: 등산 마니아 동네 뒷 산에는 등산로가 있다. 등산로는 N개의 작은 오두막들이 N −1개의 오솔길로 이어진 형태이다. 한 오솔길은 두 개의 오두막을 양 방향으로 연결한다. 한 오솔길의 길이는 1이다. 어떤 오 www.acmicpc.net /** * 1. 트리 dp문제 * * 2. 두개의 오두막을 골라 가는 길의 다양성의 총 합을 출력 * 2-1) 예시 1-2-3 이렇게 연결되어 있을때, * 1-2 1-3 2-3 오두막을 선택할 수 있고, * 각각의 길의 개수는 1 - 2 - 2 개로 총 5이다. * 2-2) 내림차순 선택 불가. 2-1 * * 3. 즉 두개의 오두막을 골라 쓰이는 총 간선의 수를 출력해야한다. * * 4. 이.. 2022. 3. 18.
[알고리즘 문제풀이] 백준 15681 트리와 쿼리(JAVA코드) https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net /* 1. U를 루트로 하는 서브트리에 속한 정점의 수를 출력 2. tree DP 3. DFS를 통해 서브트리의 노드 개수를 DP에 저장 */ import java.util.*; import java.io.*; public class BJ15681_트리와쿼리 { public static ArrayList[] tree; public st.. 2022. 3. 18.
[알고리즘 문제풀이] 백준 14499 주사위 굴리기(JAVA코드) https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net /** * 1. 처음 주사위는 모든 면이 0 * * 2. 지도를 이동하며 지도 위의 숫자가 0이 아니면 주사위 바닥면 복사. * * 3. 숫자가 0이면 주사위 바닥면이 지도로 복사. * * 4. 이동을 진행했을때마다 윗면에 쓰인 값을 출력 */ import java.io.*; import java.util.*; public clas.. 2022. 3. 18.
[알고리즘 개념] TreeDP / JAVA TreeDP Tree : cycle이 없는 그래프(서로 다른 두 노드를 잇는 간선이 1개) TreeDP는 Tree구조에서 서브트리(부분 문제)의 해를 가지고 전체 해를 구하는 방식입니다. DP에 서브트리의 어떠한 것(서브트리의 노드 개수, 서브트리의 간선 개수 등등)을 저장해둘 것이고, 보통 DFS를 통해 탐색하면서 서브트리의 해를 구해나갑니다. 정점을 기준으로 탐색해나간다면, 보통 O(N)만에 풀립니다. 백준 15681 트리와 쿼리 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ .. 2022. 3. 17.
[알고리즘 문제풀이] 백준 14502 연구소 (JAVA코드) https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net /* 1. 벽 3개 건설 (dfs) 2. 바이러스 퍼트리기 3. 안전 영역 개수 파악 4. 모든 경우의 수에서 제일 큰 안전영역의 개수 반환 시간복잡도: 3개벽짓기(8^2^3) * 탐색(8^2) == 8^8 */ import java.io.*; import java.util.*; public class 연구소 { public static int n,m, result; public static int[][] m.. 2022. 3. 17.

티스토리툴바