본문 바로가기

알고리즘

 (13)
[백준 - 2096] 내려가기 - Java https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net DP 문제이다 각 줄의 max값과 min값을 기록하는 Dmax, Dmin이라는 이차원 배열을 만들어서 사용한다. public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.p..
[백준 - 1806] 부분합 - Java https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net two pointer를 사용한 간단한 문제이다. low와 high 사이의 합이 C 미만이라면 high를 한 칸 증가시키고, C와 같거나 크다면 minlength를 갱신시키고 low를 한 칸 증가시킨다. public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new ..
[백준 - 3055] 탈출 - Java https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net BFS의 응용 문제이다. BFS queue에서 꺼내옴 목적지인가? 연결된 곳 순회 갈 수 있는가? 체크인 queue에 넣음 체크아웃(잘 사용하지 x) 한 큐에 물과 고슴도치를 같이 넣어 고려한다. 다음 턴에 물이 찰 예정인 칸에 고슴도치가 갈 수 없기 때문에 물을 먼저 체크한다. 물의 방문 체크는 *인 곳을 그냥 물로 만들고 고슴도치의 방문 체크는 time이라는 이차원 배열을 map사이즈 만큼 할당해서 방문 ..
[백준 - 1759] 암호 만들기 - Java https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 백트래킹으로 DFS를 응용했다. 조합으로 길이가 L인, 최소 한 개의 모음과 최소 두 개의 자음이 포함된 암호를 만든다. 시간제한이 넉넉했기 때문에 한 암호를 만들고 모음이 한 개 이상이고 자음이 두 개 이상인지 체크했다. public class Main { static int L; static int C; public static void main(String[] args) throws IOExcep..
2021 KAKAO BLIND RECURUITMENT 메뉴 리뉴얼 문제 설명 레스토랑을 운영하던 스카피 는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면, (각 손님은 단품메뉴를 2개 이상 주문해야..

티스토리툴바