본문 바로가기

전체 글53

[백준/G3/백트래킹/자바] 15683 감시 💡 문제 링크 : https://www.acmicpc.net/problem/15683 ⌨ 입력 첫째줄 : 가로 세로의 크기 N ( 1 둘째줄 ~ N줄  : 사무실의 각 칸의 정보 1 ~ 5 cctv / 6 : 벽  💻 출력 / 제한 첫째 줄에 사각지대의 최소 크기를 출력 한다.  풀이 방법 백트래킹, 구현문제 입니다.( 방향을 어떻게 회전 시킬까가 어려웠습니다.) 시간 복잡도 CCTV CCTV 방향 전환 조합을 찾는다.-> 각 CCTV 별 0 ,1, 2, 3 조합을 찾는다. ( 90도, 180도, 270도, 360도 )  CCTV 기본 방향  방향을 어떻게 돌릴까?  예시) 3번 CCTV 180도 회전 인경우방향배열 크기가 4개 이므로 다음 방향은 (현재 방향 + 회전) % 4CCTVDirection.. 2024. 7. 7.
[백준/S1/투포인터/자바] 20922 겹치는건 싫어 💡 문제 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 K개 이하로 들어 있는 최장 연속 부분 수열의 길이를 구하려고 한다. 100 000이하의 양의 정수로 이루어진 길이가 N인 수열이 주어진다.이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자 ⌨ 입력 첫째줄 : N ( 1 둘째줄 : 수열의 원소 N개 💻 출력 / 제한  조건을 만족하는 최장 연속 부분 수열의 길이를 출력한다.   풀이 방법 투포인터 문제 입니다. 2가지 방법으로 구현 할 수 있습니다.1. Queue, Map 을 사용 하여 구현2. 투포인터 사용 하기 1.  큐, 맵으로 구현 하기 Qu.. 2024. 7. 5.
[백준/G3/Stack/자바] 17299 오등큰수 💡 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다.Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다.예를 들어, A = [1, 1, 2, 3, 4, 2, 1]인 경우 F(1) = 3, F(2) = 2, F(3) = 1, F(4) = 1이다. A1의 오른쪽에 있으면서 등장한 횟수가 3보다 큰 수는 없기 때문에, NGF(1) = -1이다. A3의 경우에는 A7이 오른쪽에 있으면서 F(A3=2) NGF(4) = 2, NGF(5) = 2, NG.. 2024. 6. 30.
[백준/G3/MST/자바] 14621 나만 안되는 연애 💡 문제 깽미는 24살 모태솔로이다. 깽미는 대마법사가 될 순 없다며 자신의 프로그래밍 능력을 이용하여 미팅 어플리케이션을 만들기로 결심했다. 미팅 앱은 대학생을 타겟으로 만들어졌으며 대학교간의 도로 데이터를 수집하여 만들었다.이 앱은 사용자들을 위해 사심 경로를 제공한다. 이 경로는 3가지 특징을 가지고 있다.사심 경로는 사용자들의 사심을 만족시키기 위해 남초 대학교와 여초 대학교들을 연결하는 도로로만 이루어져 있다.사용자들이 다양한 사람과 미팅할 수 있도록 어떤 대학교에서든 모든 대학교로 이동이 가능한 경로이다.시간을 낭비하지 않고 미팅할 수 있도록 이 경로의 길이는 최단 거리가 되어야 한다. 만약 도로 데이터가 만약 위의 그림과 같다면,오른쪽 그림의 보라색 선과 같이 경로를 구성하면 위의 3가지 .. 2024. 6. 26.
[백준/G5/구현/자바] 11509 풍선 맞추기 💡 문제 큰 방에 N개의 풍선이 떠있다. 풍선들은 왼쪽부터 오른쪽까지 일렬로 있다.진솔이는 화살 가지고 노는 것과 사냥 연습하는 것을 좋아한다. 진솔이는 화살을 왼쪽에서 오른쪽으로 쏜다. 높이는 임의로 선택한다. 화살은 선택된 높이 H에서 풍선을 마주칠 때까지 왼쪽에서 오른쪽으로 이동한다. 화살이 풍선을 마주치는 순간, 풍선은 터지고 사라진다. 화살은 계속해서 가던길을 가는데 높이는 1 줄어든다. 그러므로 만약 화살이 높이 H에서 이동 중이었다면 풍선을 터트린 후에는 높이가 H-1이 된다.우리의 목표는 모든 풍선을 터트리되 가능한한 적은 화살을 사용하는 것이다. ⌨ 입력 첫째 줄 정수 N ( 1 두번째 줄 N개 각 풍선의 높이 ( 1   💻 출력 / 제한 필요한 최소한의 화살의 수를 출력 하시오.  .. 2024. 6. 23.
[백준/S2/DP/자바] 11053 가장 긴 증가하는 부분 수열 💡 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. ⌨ 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 💻 출력 / 제한  첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다. ( 시간 제한 1초 )  풀이 방법 DP 문제 입니다. dp[i] =  i번째 인덱스 까지 만들수 있는 가장 긴 증가 하는 부분 수열 입니다.dp[i] = 1로 초기화 ( 가장 .. 2024. 5. 26.

티스토리툴바