[Java/자바] 프로그래머스 Lv2 - 연속 부분 수열 합의 개수 (Set)

문제 설명 철호는 수열을 가지고 놀기 좋아합니다. 어느 날 철호는 어떤 자연수로 이루어진 원형 수열의 연속하는 부분 수열의 합으로 만들 수 있는 수가 모두 몇 가지인지 알아보고 싶어졌습니다. 원형 수열이란 일반적인 수열에서 처음과 끝이 연결된 형태의 수열을 말합니다. 예를 들어 수열 [7, 9, 1, 1, 4] 로 원형 수열을 만들면 다음과 같습니다. 원형 수열은 처음과 끝이 연결되어 끊기는 부분이 없기 때문에 연속하는 부분 수열도 일반적인 수열보다 많아집니다.원형 수열의 모든 원소 elements가 순서대로 주어질 때, 원형 수열의 연속 부분 수열 합으로 만들 수 있는 수의 개수를 return 하도록 solution 함수를 완성해주세요. 제한사항 3 ≤ elements의 길이 ≤ 1,000 1 ≤ el..

• format_list_bulleted ◼ 코딩테스트/구현 (Implementation)
• · 2023. 1. 26.
• textsms

[알고리즘] LIS(최장 증가 부분 수열)이란 ?

LIS (Longest Increasing Subsequence) 최장 증가 부분 수열 최장 증가 부분 수열은 말 그대로 가장 길게 증가하는 부분 수열으로 즉, 어떤 수열에서 만들 수 있는 부분 수열 중에서 가장 길면서 오름차순을 유지하는 수열을 LIS라고 합니다. 좀 더 이해하기 쉽도록 아래 그림을 봅시다. 만약 위와 같은 배열이 있을 때 만들수 있는 증가 부분 수열은 위와 같으며 최장 증가 부분 수열은 만들 수 있는 증가 부분 수열 중 길이가 가장 긴 [1, 2, 6]이 됩니다. LIS를 구현하는 방법으로는 두가지가 있습니다. DP [알고리즘] 동적 프로그래밍 (DP) 란? feat.동적 계획법 동적 프로그래밍(Dynamic programming) 란? 동적 프로그래밍은 "큰 문제"를 "부분 문제"로..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 26.
• textsms

[Java/자바] 프로그래머스 Lv2 - k진수에서 소수 개수 구하기

문제 설명 양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다. 0P0처럼 소수 양쪽에 0이 있는 경우 P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우 0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우 P처럼 소수 양쪽에 아무것도 없는 경우 단, P는 각 자릿수에 0을 포함하지 않는 소수입니다. 예를 들어, 101은 P가 될 수 없습니다. 예를 들어, 437674을 3진수로 바꾸면 211020101011입니다. 여기서 찾을 수 있는 조건에 맞는 소수는 왼쪽부터 순서대로 211, 2, 11이 있으며, 총 3개입니다. (211, 2, 11을 k진법으로 보았을 때가 아닌, 10진..

• format_list_bulleted ◼ 코딩테스트/구현 (Implementation)
• · 2023. 1. 25.
• textsms

[Java/자바] 프로그래머스 Lv2 - 타겟 넘버 (DFS 깊이 우선 탐색)

문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 20개 이하입니다. 각 숫자는 1 이상 50 이하인 자연수입니다. 타겟 넘버는 1 이상 100..

• format_list_bulleted ◼ 코딩테스트/DFS,BFS
• · 2023. 1. 22.
• textsms

[Java/자바] 프로그래머스 Lv2 - 귤 고르기 (getOrDefault 활용)

문제 설명 경화는 과수원에서 귤을 수확했습니다. 경화는 수확한 귤 중 'k'개를 골라 상자 하나에 담아 판매하려고 합니다. 그런데 수확한 귤의 크기가 일정하지 않아 보기에 좋지 않다고 생각한 경화는 귤을 크기별로 분류했을 때 서로 다른 종류의 수를 최소화하고 싶습니다. 예를 들어, 경화가 수확한 귤 8개의 크기가 [1, 3, 2, 5, 4, 5, 2, 3] 이라고 합시다. 경화가 귤 6개를 판매하고 싶다면, 크기가 1, 4인 귤을 제외한 여섯 개의 귤을 상자에 담으면, 귤의 크기의 종류가 2, 3, 5로 총 3가지가 되며 이때가 서로 다른 종류가 최소일 때입니다. 경화가 한 상자에 담으려는 귤의 개수 k와 귤의 크기를 담은 배열 tangerine이 매개변수로 주어집니다. 경화가 귤 k개를 고를 때 크기가..

• format_list_bulleted ◼ 코딩테스트/구현 (Implementation)
• · 2023. 1. 21.
• textsms

[알고리즘] 힙 정렬(Heap Sort)이란?

먼저 힙 정렬에 대해 다루기 전에 "힙"에 대한 이해가 필요합니다. 힙에 대해 알고 싶다면 아래 링크를 참고하시면 도움됩니다. 힙(Heap) 자료구조 힙(Heap)이란 ? 완전 이진 트리의 일종으로, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조입니다. 힙을 사용하는 이유는 최댓값과 최솟값을 찾기 위해 배열을 사용하는 경 hstory0208.tistory.com 힙 정렬(Heap Sort) 힙 정렬 알고리즘은 삽입과정 없이 삭제과정만이 이뤄집니다. 최대힙(max heap)을 구현한뒤, 루트 노드를 삭제하여 마지막 노드가 루트 노드가 되어 최대힙의 규칙에 맞게 재구조화 되며 정렬합니다. 힙 정렬 알고리즘은 주로 다음과 같은 경우에 유용하게 사용됩니다. 최댓값과 최솟값을 구할 때 최대 k만..

• format_list_bulleted ◼ CS 기초 지식/[알고리즘]
• · 2023. 1. 21.
• textsms