본문 바로가기

⌨️코딩테스트20

[JAVA/백준/11660] 구간 합 구하기 5 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 방법 구간합은 특정한 구간의 합을 의미합니다. 왼쪽과 같은 입력이 주어졌을 때 해당 칸의 앞 칸까지의 모든 수의 합을 더한 값이 구간합이 됩니다. 만약 2열 2행부터 3행 3열까지의 구간합을 구하고 싶다면 다음과 같이 구할 수 있습니다. 1행 1열부터 3행 3열까지의 구간합에서 회색 구간을 빼주고 겹쳐지는 노란 색 한 칸을 더하면 최종적으로 구하고자하는 구간의 합을 구할 수 있습니다. 결과 코드 BufferedRea.. 2023. 7. 12.
[JAVA/프로그래머스] 가장 큰 수 / 정렬, 스트림 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는.. 2023. 4. 20.
[JAVA/프로그래머스] 전화번호 목록 / 해시 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성.. 2023. 3. 31.
[JAVA/백준/2457] 공주님의 정원 / Greedy 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 이 문제는 그리디 알고리즘을 사용하여 풀 수 있다 풀이과정은 다음과 같다 꽃을 시작 날짜를 기준으로 정렬, 시작 날짜가 같다면 종료 날짜를 기준으로 정렬 꽃의 시작 날짜가 현재 날짜보다 크면 탐색을 종료 현재 날짜보다 작거나 같은 시작 날짜를 가진 꽃 중 끝나는 날짜가 가장 큰 꽃을 선택 선택한 꽃의 끝나는 날짜를 기준으로 다시 시작 위와 같은 과정을 반복하면 최대로 심을 수 있는 꽃의 수를 계산할 수 있으며 자세한 설명은 주석으로 달아놨다 .. 2023. 3. 27.
[JAVA/백준/1520] 내리막길 / DP, DFS 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 이 문제는 출발점에서 도착점까지 가는 경로의 수를 구하는 것이다 DFS를 통해 도착하는 모든 경로를 얻을 수 있지만 시간초과가 발생하게 된다 같은 경로를 중복해서 탐색할 수가 있기 때문에 시간 복잡도를 효율적으로 개성해야 한다 따라서 DFS + DP를 이용해 풀이를 했다 우선, DFS를 이용해 출발점에서 도착점까지 모든 경로를 탐색하는데 현재 위치에서 갈 수 있는 높이가 낮은 지점으로 이동하면서 경로의 수를 누적한다. 이미 계산한 경로는 중복 계산하지 않도록 .. 2023. 3. 25.
[JAVA/백준/1495] 기타리스트 / DP 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 풀이 과정 기타의 볼륨을 조절하여 연주할 수 있는 곡 중에서, 마지막 곡을 연주할 때 볼륨의 최댓값을 구하는 문제다 이 문제를 해결하기 위해서는 가능한 모든 볼륨을 조합해봐야 하며 시간과 메모리를 적게 소모하기 위해서는 동적 계획법(Dynamic Programming)을 사용할 수 있다 우선 입력값을 받아와서, 가능한 볼륨을 저장하는 배열인 dp를 초기화한다 그리고 첫번째 곡을 연주할 때, 현재 볼륨(S)을 인덱스로 가지는 .. 2023. 3. 20.

티스토리툴바