[Java] BaekJoon 1806. 부분합 (골드4) (투포인터)

문제출처: https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제이해 목표 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하시오 !! (단 시간제한 0.5초 !!) 풀이 시간제한 0.5초안에 해결하기 위해서는 선형으로 한 번의 탐색으로 정답을 도출할 수 있어야 한다. 투포인터를 이용하자. 첫 번째 포인터: for문의 i 두 번..

[Java] BaekJoon 5557. 1학년 (골드5) (dp)

문제출처: https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제이해 목표 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다. 이렇게 등식이 성립하는 올바른 등식의 개수를 구하시오. 풀이 단서는 "왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이상 2..

[Java] BaekJoon 12869. 뮤탈리스크 (골드4) (dfs) (dp)

문제 출처: https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 문제 이해 목표 (1

[Java] BaekJoon 14238. 출근 기록 (골드3) (DFS) (DP)

문제 출처: https://www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net 문제 이해 목표 강호(A): 매일 준규(B): 다음날은 어야함 수빈(C): 다음날과 다다음날을 쉬어야함 주어진 출근 기록 S중 올바른 출근기록인것 아무거나 출력 풀이 1. 길이가 최대 50이 될 수 있는 S 2. S의 순서를 바꿀 수 있는 순열을 구한다. -> 가능한 순열이 있다면 출력한다. -> 모든 순열을 조사해도 없으면 -1을 출력한다. 3. 순열을 만들 때 -> 매..

LeetCode 152. Maximum Product Subarray (Java) (Medium) (DP)

문제출처: https://leetcode.com/problems/maximum-product-subarray/ Maximum Product Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제이해 목표 주어진 숫자 Array(nums)에서 연속된 숫자의 곱 중 최댓값이 되는 것을 찾아라 ! ex) [2,3,-2,4] 답: 6 풀이 1. 값이 0인 인덱스들을 찾아서 저장한다. 2. 검사할 배열범위를 (1) 처음 ~ (첫 0의 인덱스 - 1) (2..

BaekJoon 9935. 문자열 폭발 (Java) (골드4) (문자열 조회)

문제출처: https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 문제 이해 목표 문자열이 있고, 폭발 문자열이 있다. 문자열 안에 폭발 문자열이 있다면 없애고 이어붙인다. 만약 폭발 문자열을 다 터트리고 남아 있는 문자가 있다면 정답으로 출력하고, 없으면 "FRULA"를 출력한다. 풀이 실패한 풀이: StringBuilder에 문자열을 담고, 문자열을 탐색하는 인덱스를 가리키는 i를 설정한뒤 indexOf로 i이후의 폭발 문자열을 찾도..

SW Expert Academy 1206. View (Java)

문제출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV134DPqAA8CFAYh SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 이해 목표 왼쪽, 오른쪽이 2칸이상 비은 세대는 조망권이라고 한다. 조망권이 확보된 세대의 수를 출력하면 된다. 풀이 1. 현재 빌딩을 중심으로 좌,우로 두개의 빌딩을 조사해서 가장 높은 층을 구한다. -> maxFloor 2. 현재 빌딩에서 조망권이 확보된 세대수 = (현재 중심이 된 빌딩의 높이 - maxFloor) 단, 현재 중심이된 빌딩의 높이가 다른 4개의 빌딩의 높이보다 ..

BaekJoon 2023. 신기한 소수 (Java) (골드5) (조건이 있는 순열) (dfs)

문제출처: https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 문제 이해 목표 자릿수 N이 주어졌을 때 가장 높은 자릿수부터, 한 개, 두 개, 세 개... N개의 정수가 모두 소수가 되는 신기한 소수를 만드는 것이다. ex) 7331 -> 7 소수, 73 소수, 733 소수, 7331 소수 풀이 -> 1의 자릿수부터 시작해서 ~ N자릿수로 구성된 순열을 만들 것이다. ex) 7331을 만들기위해 7 검사, 73 검사, 733 검사, 7..