본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 1912 연속합 출처: https://www.acmicpc.net/problem/1912 Input 10 10 -4 3 1 5 6 -35 12 21 -1 Output 3 배열의 연속된 부분합을 구하는 문제입니다. ① 중첩 for문을 이용하면 시간초과. ② 모든 원소가 음수일 때, 결과는 『0』이 아닙니다. Input 1 -100 Output -100 구현 DP 적용해서 부분문제부터 해결 시뮬레이션] import java.util.Scanner; public class Main { static final int MIN = Integer.MIN_VALUE; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = Integer... 2021. 2. 24.
[BOJ] 백준 1931 회의실 배정 출처: https://www.acmicpc.net/problem/1931 Input 11 1 4 3 5 0 6 5 7 3 8 5 9 6 10 8 11 8 12 2 13 12 14 Output 4 최대한 많은 회의를 잡기 위해서는 각 회의시간이 적어야 합니다. (1, 4) → (5, 7) → (8, 11) → (12, 14)과 같이 회의가 끝나자마자 다음 회의가 이어져야 합니다. 끝나는 시간이 빠른 순서로 1차 정렬 끝나는 시간이 같다면 시작시간이 빠른 순으로 정렬 ※ 우선순위큐로도 구현 가능 Sample Case Input 2 1 2 2 2 Output 2 두 회의가 끝나는 시간이 동일하면서, 하나의 회의는 시작시간과 종료시간까지 동일한 경우. (즉, 문제에서 주어진 회의가 시작하자마자 끝나는 case... 2021. 2. 24.
[BOJ] 백준 10451 순열 사이클 출처: https://www.acmicpc.net/problem/10451 Input 2 8 3 2 7 8 1 4 5 6 10 2 1 3 4 5 6 7 9 10 8 Output 3 7 순열정보를 아래와 같이 배열로 표현했을 때, 그래프에서 i → πi로 향하는 간선을 이어줍니다. ex) 순열정보 (3, 2, 7, 8, 1, 4, 5, 6)가 주어졌을 때, 3개의 순열 사이클이 존재한다고 정의. 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는.. 2021. 2. 24.
[BOJ] 백준 9466 텀 프로젝트 출처: https://www.acmicpc.net/problem/9466 Input 2 7 3 1 3 7 3 4 6 8 1 2 3 4 5 6 7 8 Output 3 0 Test Case #1의 경우 아래와 같이 배열을 표현. 사이클을 형성하는 정점은 {4, 7, 6}, {3}으로 사이클을 속하지 못한 정점은 3개 입니다. * 정점 1개로 사이클을 형성할 수 있음 ※ 사이클을 형성하는 정점은 사이클끼리 간선을 가지는 형태 ※ 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는.. 2021. 2. 24.
[BOJ] 백준 1149 RGB거리 출처: https://www.acmicpc.net/problem/1149 Input 3 26 40 83 49 60 57 13 89 99 Output 96 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com 3개의 집에 R - B - R일 때, 최소 비용 26 40 83 49 60 57 13 89 99 → 26 + 57 + 13 = 96 Sample Case 1 2 2 1 2 2 2 1 3 → 2 + 1.. 2021. 2. 24.
[BOJ] 백준 11724 연결요소의 개수 출처: https://www.acmicpc.net/problem/11724 Input 6 5 1 2 2 5 5 1 3 4 4 6 Output 2 ※ 연결요소(Connected component)? 전체 그래프(G)에서 정점과 간선이 겹치지 않는 부분 그래프를 의미합니다. (또한, 부분 그래프의 합집한은 전체 그래프입니다.) ① 정점과 간선 정보를 인접행렬로 구현. ② BFS로 연결된 지점을 방문하여 부분 그래프의 개수를 파악합니다. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = n.. 2021. 2. 24.
[BOJ] 백준 10026 적록색약 출처: https://www.acmicpc.net/problem/10026 Input 5 RRRBB GGBBB BBBRR BBRRR RRRRR Output 4 3 DFS - stack 이용 - 중복 방문 방지를 위한 방문표시 visited[][] - 적록색약 여부에 따른 방문여부 (R, G 색깔 구분 여부) import java.util.Scanner; import java.util.Stack; public class Main { static char[][] arr; static int[][] visited; static char searchType; static int[] dx, dy; static Stack stack; static int N; public static void main(String[.. 2021. 2. 24.
[BOJ] 백준 17471 게리맨더링 출처: https://www.acmicpc.net/problem/17471 Input 6 2 3 4 5 6 7 2 2 3 2 1 3 2 1 2 2 5 6 2 4 6 2 4 5 Output 9 다음과 같이 그래프 정보가 주어집니다. [그래프 형태] 하나의 정점을 지역이라고 정의하고 두 개의 선거구로 나누고자합니다. * 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 합니다. 다른 선거구에 속한 지역을 통해서 가는 경우는 해당되지 않습니다. * 각 구역은 두 선거구 중 하나에 포함되어야 합니다. * 선거구는 적어도 한개의 지역을 포함해야 합니다. [가능한 방법] [불가능한 방법] [좌측 그림]: 같은 선거구 지역 『5』, 『6』 연결 x [우측 그림]: 각 선거구는 적어도 1개의 지역을 포함 A, B.. 2021. 2. 24.
[BOJ] 백준 1011 Fly me to the Alpha Centauri 출처: https://www.acmicpc.net/problem/1011 Input 3 0 3 1 5 45 50 Output 3 3 4 이동 거리: 로켓의 직전 이동 거리를 k라고 했을 때, 다음에는 『k-1』, 『k』, 『k+1』 거리만큼 이동 ex) 로켓 위치= 2 / 직전 이동 거리 k = 4일 때, 『3』 『4』 『5』 만큼 이동하여 다음 로켓 위치 = 5 or 6 or 7 * 출발점 x에서 k=1만큼 이동하여 로켓의 위치 = 1 * 도착점 y에 도착하기 직전 이동거리는 반도시 『1』이어야만 합니다. ※ 최소 이동횟수에 따른 최대 이동거리 [횟수] [k] 1 1 ▶ 1 2 1→1 ▶ 2 3 1→2→1 ▶ 4 4 1→2→2→1 ▶ 6 5 1→2→3→2→1 ▶ 9 6 1→2→3→3→2→1 ▶ 12 7.. 2021. 2. 24.
[BOJ] 백준 1260 DFS와 BFS 출처: https://www.acmicpc.net/problem/1260 Input 4 5 1 1 2 1 3 1 4 2 4 3 4 Output 1 2 4 3 1 2 3 4 4개의 정점과 5개의 간선은 아래와 같은 상태입니다. DFS, BFS 방문 순서는 다음과 같습니다. [구현] ① 그래프 정보를 바탕으로 인접행렬 구현 ② 인접행렬에서 DFS, BFS 구현 Input 7 6 1 1 4 1 3 1 2 4 6 4 5 2 7 Output 1 2 7 3 4 5 6 1 2 3 4 7 5 6 import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stack; public class Main { pub.. 2021. 2. 24.
반응형

티스토리툴바