알고리즘 공부 및 문제 풀이/백준(BOJ) (220) 썸네일형 리스트형 [boj] 백준 16508 전공책 (Java) - 완전탐색 [문제] https://www.acmicpc.net/problem/16508 16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net [풀이] 정석적인 완전탐색 문제~ 전공책을 선택하는 경우, 선택하지 않는 경우 2가지에 대해 모두 dfs를 돌려준다. 전공책을 선택하는 경우 해당 전공책의 포함된 모든 알파벳들을 1씩 증가시켜 준다. 모든 전공책에 대한 선택이 끝난 후, 선택된 전공책들에 포함된 알파벳들의 select[] 값이 만들고자 하는 문자열의 알파벳들인 count[] 보다 작은 값이 존재한다면 불가능한 조합이므로 fa.. [boj] 백준 14501 퇴사 (Java) - 완전탐색 [문제] https://www.acmicpc.net/problem/14501 [풀이] 경우는 2가지이다. 1. 상담을 하는 경우. 그날의 비용과 그 다음 할 수 있는 상담일로 이동한다. 2. 상담을 하지 않는 경우. 비용 합은 그대로이고, 다음 날로 이동한다. 상담일이 n일을 벗어나면 안되기 때문에 범위를 체크해준 후 dfs를 호출했다. [코드] package 브루트포스; import java.util.*; import java.io.*; public class boj_14501_퇴사 { static int n; static int[] ti; static int[] pi; static int answer = -1; public static void main(String[] args) throws Exce.. [boj] 백준 2503 숫자 야구 (Java) - 완전 탐색 [문제] https://www.acmicpc.net/problem/2503 [풀이] 숫자는 중복될 수 없고 0이 들어갈 수 없다. 따라서 123~987 까지 중복되는 숫자와 0이 들어가는 숫자를 제외한 모든 숫자에 대해서 n개의 숫자와 비교한다. n개의 숫자에 대해서 strike와 ball의 개수가 모두 일치한다면 가능성이 있는 수이므로 answer를 증가시킨다. [코드] package 브루트포스; import java.io.*; import java.util.*; public class boj_2503_숫자야구 { static int n; static List list; static int answer; public static void main(String[] args) throws Exception.. [boj] 백준 14620 꽃길 (Java) - 완전탐색(백트래킹) [문제] https://www.acmicpc.net/problem/14620 [풀이] 기본 백트래킹을 이용한 완전 탐색 문제. [코드] package 브루트포스; import java.io.*; import java.util.*; public class boj_14620_꽃길 { static int n; static int[][] board; static boolean[][] visited; static int answer = Integer.MAX_VALUE; static int[] dr = {0, 0, 1, -1}; static int[] dc = {1, -1, 0, 0}; public static void main(String[] args) throws Exception{ //진아가 꽃을 심기 위해 .. [boj] 백준 gold5 13164 행복 유치원 (Java) - 그리디 [문제] https://www.acmicpc.net/problem/13164 13164번: 행복 유치원 행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 www.acmicpc.net [풀이] 개인적으로 이런 문제가 제일 싫고 제일 어렵다..코드가 복잡하진 않지만 그 로직을 생각해내는게..머리가 핑핑 잘돌아갔으면 좋겠당 이 문제의 핵심은 어떻게 최소 비용의 합을 가지는 k개의 그룹으로 묶을 것인지이다. 이를 위해 먼저 모든 인접한 학생들 간의 차이를 구해서 리스트에 넣어줘야 한다. 예제처럼 1 3 4 6 10 의 학생들이 있다고 하면 1번 학생과 4번 학생의 차이.. [boj] 백준 gold5 11000 강의실 배정 (Java) - 그리디 [문제] https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net [풀이] 처음에는 앞서 풀었던 회의실 배정 문제와 같이 한 강의실에 최대한의 인원을 넣고 강의실에 배정받았다는 bool 변수를 둔 후 while문을 돌며 관리하려고 했다. 그런데 N이 커서 시간이 너무 커진다.. 풀이 시나리오는 다음과 같다. 1. 강의 시작 시간 오름차순으로 정렬해준다. 2. 강의 종료 시간을 저장하는 우선순위 큐를 선언한다. 우선순위 큐는 기본 오름차순으로 데이터를 저장한다. 3. 회의실 배정 문제와 같이 현재 강의.. [boj] 백준 silver1 1931 회의실 배정 (Java) - 그리디 [문제] https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net [풀이] 이상하게 그리디에 머리가 잘 안돌아간다(다른 건 잘 돌아가는 줄ㅋ)...그래서 오늘은 그리디 데이로.. 최대한 많은 회의실을 배정하려면 어떻게 해야 하는가? 그리디하게 종료시간이 빠른 순서대로 착착 회의실을 배정해주면 된다. 종료시간이 빠른 순서대로 정렬 후, 그 다음 회의의 시작 시간이 현재 회의의 종료 시간과 같거나 더 늦다면 다음 회의실을 배정 받을 수 있다. 여기서 주의할 점은 정렬 시 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬해줘야 한다는 것이다!!! 예를 들어, (시작 시간, .. [boj] 백준 gold5 14567 선수 과목 (Java) - dp [문제] https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net [풀이] 과목 별 진입차수를 계산하여 진입 차수가 0이면 dp[i]에 1을 저장한다. 이는 선수과목이 없으므로 1학기 째에 바로 들을 수 있음을 의미한다. dp[i] = k는 i번 과목을 이수하기 위해 필요한 최소 학기를 저장한다. 만약 5번 과목의 선수관계가 1 - 3 - 5, 4 - 5 두 가지 존재한다면 5번 과목을 이수하기 위한 최소 학기는 3학기이다. 즉, 1~n번까지 과목을 순회하며 i번 과목을 선수 과.. 이전 1 2 3 4 5 ··· 28 다음 목록 더보기