알고있니

문제 https://www.acmicpc.net/problem/14503   입출력   아이디어시뮬레이션 조건 잘 읽고 그대로 구현하기   코드  import java.io.BufferedReader;import java.io.FileInputStream;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N, M; static int r, c, d; // 북(0) 동(1) 남(2) 서(3) static int[][] way = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } }; static int[][] box; static int WALL = 1, E..

문제https://www.acmicpc.net/problem/14889  입출력 40 1 2 34 0 5 67 1 0 23 4 5 00아이디어재귀 종료 조건, 가지치기 조건 잘 설정하기(?)   코드  import java.io.BufferedReader;import java.io.FileInputStream;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N; // 내림차순 순서, 어떤 순서로 서 있는지 static int[][] box; static boolean[] visited; static int minDiff = Integer.MAX_VALUE; public static..

문제https://www.acmicpc.net/problem/14501  입출력73 105 201 101 202 154 402 20045 아이디어 1) 백트래킹n이 최대 15이므로  선택 O, 선택 X 2) DPdp[i] // i번째 상담 결정시 최대 수익 (뒤부터)상담 O dp[i + T[i]] + P[i]상담 X dp[i + 1]  코드  import java.io.BufferedReader;import java.io.FileInputStream;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N; // 내림차순 순서, 어떤 순서로 서 있는지 static int[] times;..

문제https://www.acmicpc.net/problem/1766  N개의 문제(1번~N번)가 있고, 일부 문제는 다른 문제를 먼저 풀어야 한다.가능한 한 쉬운 문제부터 풀어야 한다.즉, 진입 차수가 0인 노드 중에서 번호가 작은 문제부터 풀어야 한다.  입출력입력 4 24 23 1 출력3 1 4 2아이디어 위상정렬 + 우선순위 큐 위상 정렬(Topological Sorting)을 사용하여 순서를 정하면서, 가능한 한 숫자가 작은 문제 부터 풀기 위해 우선순위 큐를 활용한다  1. 그래프, 진입 차수 배열 생성2. 진입 차수가 0인 문제를 우선순위 큐에 저장 (문제 번호가 작은 것부터 풀어야하므로 오름차순 정렬이 필요)  코드  import java.io.BufferedReader;import jav..

문제 https://www.acmicpc.net/problem/1005 특정 건물이 먼저 완성되어야 함승리하기 위해 건물 W를 건설하는데 걸리는 최소 시간 구하기   입출력테스트 케이스 개수 T건물 개수 N 건설 순서 규칙 개수 K각 건물i의 건설 시간건설 순서 규칙 X Y -> X를 지어야 Y를 지을 수 있음목표 건물 W  아이디어위상 정렬을 활용한 건설 순서 및 최소 시간 계산 문제  위상 정렬 + DP 1. 진입 차수 배열 indegree 생성 - i번 건물을 짓기 전에 지어야 할 건물 개수2. 그래프 생성i번 건물 이후에 지어야 할 건물 목록3. resulti번 건물이 완성되는 최소 시간4. 위상 정렬 수행indegree[i] == 0 인 건물부터 큐에 넣고 시작 선행 건물이 모두 지어진 후 최대..

문제https://www.acmicpc.net/problem/2178   입출력  아이디어 예전에는 Queue에 최단 거리를 넣었었는데 최단 거리를 저장하는 배열을 밖으로 빼보았다   코드  import java.io.BufferedReader;import java.io.FileInputStream;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.Queue;import java.util.StringTokenizer;public class Main { static int N, M; static int[][] box; static int[][] way = { { -1, 0 }..

보호되어 있는 글입니다.

보호되어 있는 글입니다.

그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때 이분 그래프라고 한다 DFS나 BFS를 활용하여 인접한 노드들은 다른 색으로 칠해가다가 이미 같은 색인 경우 이분 그래프로 만들 수 없음을 알 수 있다  [관련 문제]1707 이분그래프https://www.acmicpc.net/problem/1707 13265 색칠하기 https://www.acmicpc.net/problem/13265 1953 팀배분각각 싫어하는 사람들의 정보가 주어짐 (서로 같은 팀을 하기 싫어하는 사람들)-> 연결된 정점을 다른 색으로 칠한다 https://www.acmicpc.net/problem/1953

보호되어 있는 글입니다.