본문 바로가기
반응형

PS 문제 풀이/Baekjoon446

[BOJ] 백준 2623 음악프로그램 출처: https://www.acmicpc.net/problem/2623 Input 6 3 3 1 4 3 4 6 2 5 4 2 2 3 Output 6 2 1 5 4 3 정점별 선후관계 DFS를 활용한 위상정렬 (Topological sort) 이용 * 그래프가 사이클을 형성하여 위상정렬 되지 않는지 확인 필요. 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 구현 ① 그래프 표현(인접리스트, 인접행렬) → 인접리스트 ② 위상정렬 구현 (진입indeg.. 2021. 2. 22.
[BOJ] 백준 1516 게임개발 출처: https://www.acmicpc.net/problem/1516 Input 5 10 -1 10 1 -1 4 1 -1 4 3 1 -1 3 3 -1 Output 10 20 14 18 17 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com ▶ 진입차수를 이용한 위상 정렬 이용. 1. 자기 자신으로 들어오는 간선이 없는 정점을 모두 찾아 queue 저장 2. 위에서 찾은 정점(들)과 그 정점으로 부터 나오는.. 2021. 2. 22.
[BOJ] 백준 1005 ACM Craft 출처: https://www.acmicpc.net/problem/1005 Input 2 4 4 10 1 100 10 1 2 1 3 2 4 3 4 4 8 8 10 20 1 5 8 7 1 43 1 2 1 3 2 4 2 5 3 6 5 7 6 7 7 8 7 Output 120 39 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 시뮬레이션 ▶ 진입차수가 0인 정점의 cost를 answer에 할당 indegree =.. 2021. 2. 22.
[BOJ] 백준 1766 문제집 출처: https://www.acmicpc.net/problem/1766 Input 4 2 4 2 3 1 Output 3 1 4 2 위상정렬 (Topological sort) 위상정렬 (Topological sort) 개념 DAG에서 의존성에 맞게 그래프의 정점을 정렬 DAG (Directed Acyclic graph) 간선에 방향이 존재하고, 사이클(cycle)이 없는 그래프. DAG는 노드간의 의존성을 나타내는데, 작업 간의 순서를 표현하는 zoosso.tistory.com 구현 - 인접리스트로 그래프 표현 - 진입차수 방식의 위상정렬 - 사이클 유무 확인 필요 X - 위상 정렬 결과가 여러개 나올 수 있지만, 번호가 낮은 정점이 우선시 되므로 결과를 한 개로 제한. → 우선순위 큐 이용 우선순위 큐.. 2021. 2. 22.
[BOJ] 백준 2234 성곽 출처: https://www.acmicpc.net/problem/2234 Input 4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13 Output 5 9 16 ① BFS 탐색으로 연결되어 있는 방을 확인합니다. 연결된 공간은 동일한 방 번호를 매기고 그 크기를 동시에 측정합니다. ② 벽이 0(0000) ~ 15(1111) 형태로 주어져 있으므로 벽 존재 여부는 아래와 같이 확인 가능합니다. ③ 하나의 벽을 제거하여 얻을 수 있는 가장 넓은 방의 크기는 어떤 벽이든 한 곳만 뚫을 수 있으므로, 이중 for문으로 map[][]을 탐색하면서 오른쪽과 아래쪽에 위치한 공간 확인합니다. 같은 방번호가 아닌 경우, 두 방의 크기를 더.. 2021. 2. 22.
[BOJ] 백준 2156 포도주 시식 출처: https://www.acmicpc.net/problem/2156 Input 6 6 10 13 9 8 1 Output 33 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com * 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. O O X X O O O X O wine[i] ; i 번째 포도잔에 들어있는 포도주의 양(비용) dp[i] = Max(dp[i-1], wine[i] + wine[i-1].. 2021. 2. 22.
[BOJ] 백준 9461 파도반 수열 출처: https://www.acmicpc.net/problem/9461 Input 2 6 12 Output 3 16 ▶ 동적계획법(Dynamic Programming, DP) 동적계획법(Dynamic Programming, DP) 동적 계획법(Dynamic Programming)은 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 zoosso.tistory.com - 처음 정삼각형의 변의 길이는 1입니다. - 나선형으로 정삼각형들이 추가되는데, 나선에서 가장 긴 변의 길이를 k 일 때, 추가되는 정삼각형의 길이는 k 입니다. P(N) = {1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 1.. 2021. 2. 22.
[BOJ] 백준 1012 유기농 배추 출처: https://www.acmicpc.net/problem/1012 Input 1 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 5 9 5 7 6 8 6 9 62 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 5 9 5 7 6 8 6 9 6 10 10 1 5 5 Output 5 1 배추의 위치는 다음과 같다. 0: 배추가 심어져 있지 않은 땅 / 1: 배추가 심어져 있는 땅 해충을 방지하기 위해 지렁이를 배추 근처에 서식 시키려고 합니다. 지렁이는 인접한(상하좌우) 배추를 통해 이동할 수 있기에 인접한 배추들도 보호받을 수 있습니다. 최소 몇 마리의 지렁이가 필요한지 구하는 문제로 배추.. 2021. 2. 22.
[BOJ] 백준 1759 암호 만들기 출처: https://www.acmicpc.net/problem/1759 Input 4 6 a t c i s w Output acis acit aciw acst acsw actw aist aisw aitw astw cist cisw citw istw 완성되는 문자의 길이는 L이며 다음의 조건을 만족해야 합니다. - 최소 한 개의 모음 { a e i o u }과 최소 두 개의 자음으로 구성 - 암호는 증가하는 순서(오름차순)으로 구성. ex) abc ( O ) / bac ( X ) ▶ 가능한 암호 조합을 사전순으로 모두 출력하는 문제입니다. 구현 ① 주어진 알파벳을 먼저 사전순으로 정렬. ② DFS를 통해 구성가능한 모든 경우의 수를 구합니다. ← 순열 ③ 구성된 문자열에서 최소 모음 1개와 자음 2개 존.. 2021. 2. 22.
[BOJ] 백준 1065 한수 출처: https://www.acmicpc.net/problem/1065 Input 110 Output 99 어떤 양의 정수 X의 자리수가 등차수열을 이루면 『한수』 라고 합니다. ※ 등차수열: 연속된 두 개의 수의 차이가 일정한 수열. ex) [123]: 1 → 2 → 3 ▶ +1 ex) [531]: 5 → 3 → 1 ▶ -2 ex) [222]: 2 → 2 → 2 ▶ +0 주어진 수를 한자리씩 비교하여 등차수열을 이루고 있는지 확인. import java.util.Scanner; public class Main { public static int checkNumberLength(int num) { int len = 0; while (true) { int temp = num / 10; len++; // .. 2021. 2. 22.
반응형

티스토리툴바