본문 바로가기
반응형

분류 전체보기1308

[BOJ] 백준 2252 줄 세우기 출처: https://www.acmicpc.net/problem/2252 Input 3 2 1 3 2 3 Output 1 2 3 N명(정점)의 학생들의 비교한 키가 일부 제공되었습니다. (방식: 두 학생의 키를 비교 ← 방향성 그래프) 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 구현 위상 정렬을 활용했으면 그 중 인접리스트 이용. ※ 해당 문제는 사이클을 형성하지 않는 Input Data이기에 코드에 .. 2021. 2. 24.
[BOJ] 백준 16637 괄호 추가하기 출처: https://www.acmicpc.net/problem/16637 Input 9 3+8*7-9*2 Output 136 길이가 N인 수식은 {+, -, x }로 이루어져 있습니다. 연산자 우선수위 동일하며, 수식을 왼쪽에서부터 순서대로 계산. ex) 3+8*7-9*2 = 136 수식에 소괄호를 추가하여 식의 순서를 바꿀 수 있습니다. ex) 3+(8×7)-(9×2) = 41 하지만, 괄호 안에는 연산자가 하나만 있어야 하며 괄호 안에 괄호가 있는 중첩된 형태는 허용하지 않습니다. ex) 3+((8×7)-9)×2, 3+((8×7)-(9×2)) ▶ 수식이 주어졌을 때, 괄호를 적절히 추가해서 최댓값 구하기. 단계별 구현 ① 완전탐색으로 괄호가 놓일 수 곳에 배치하여 수식 완성 ex) 3+(8×7)-9.. 2021. 2. 24.
[BOJ] 백준 2661 좋은수열 출처: https://www.acmicpc.net/problem/2661 Input 7 Output 1213121 "나쁜 수열": 임의의 길이의 인접한 두 개의 부분 수열이 동일한 것이 있는 수열. 그렇지 않은 수열을 『좋은 수열』 이라고 함. 구현 N 길이의 모든 수열 중 주먹구구 방식으로 구한 후, ex) N=4 일때, 1111 → 1112 → 1113 → 1121 → ... → 3333 좋은 수열 여부를 파악하기에는 시간제한. 길이 1→N 까지 좋은 수열인지 확인하며 길이 N인 수열을 만들어 갑니다. ← DFS ※ 코드에서 『좋은 수열』인지 판단할 때, 부분문자열의 길이를 {문자열 길이}/2 까지만 계산 while(size str.length()) { break; } // 나쁜 수열에 해당된다면 i.. 2021. 2. 24.
[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.
반응형

티스토리툴바