alorithm 94

[LeetCode] Permutations

https://leetcode.com/problems/permutations/   문제 파악주어진 배열로 만들 수 있는 모든 순열 구하기1 10 All the integers of nums are unique. (요소 중복 허용)접근 방법💡 -재귀 함수가 리턴되면 마지막에 호출한 함수가 가장 먼저 리턴-리턴 되면 리스트에서 해당 원소 삭제, 방문 배열 초기화 - : 중복 허용, 순서 존재-방문 배열은 하나의 순열 안에서 이루어지는 것을 유의하자.해당 원소에 해당하는 경우의 수를 모두 순회하면서 겹치지 않게 표시 코드 구현import java.util.*;class Solution { //순열 문제 : 중복 허용, 순서 존재 public List> permute(int[] nums) { ..

[LeetCode] Combinations

https://leetcode.com/problems/combinations/ 문제 파악주어진 1~n까지의 범위 중에서, k개의 원소를 갖는 숫자 ‘조합’ 구하기1 1 접근 방법💡 backtrack() 함수 정의하여, 가장 작은 단위의 연산을 정의하고, 재귀적으로 해당 함수를 호출한다. 코드 구현class combinations { public List> combine(int n, int k) { //1~n까지 숫자 중에 k개를 짝지은 조합을 찾아내기 List> result = new ArrayList(); int start = 1; //시작점을 값으로 전달해주기. // 함수에 유동적으로 인자를 주고 싶을 때 사용, 함수에 인자가 증가하며 삽입될..

[LeetCode] Subsets

https://leetcode.com/problems/subsets/description/문제 파악주어진 배열에서 나올 수 있는 subset 모두 구하기(조합)1 10 All the numbers of nums are unique.접근 방법💡 -combination으로 순서가 없는 리스트를 담아 최종 result에 적재-”combinations” 문제와 흡사-조건 걸지 않고 조합 만들어지는대로(길이n) 결과로 반환하는 것이 포인트 코드 구현import java.util.*;class Solution { public List> subsets(int[] nums) { List> result = new ArrayList(); List curr = new ArrayList(); ..

[프로그래머스] 피로도

피로도https://campus.programmers.co.kr/tryouts/140902/challenges  문제 파악💡 -dfs, bfs, dp로도 풀 수 있는 문제-가진 체력으로 각 던전을 돌며 최대 던전 돌 수 있는 횟수 구하기-똑같은 게 계속 반복된다. ⇒ 작은 문제로 줄여서 풀기 (재귀)-순차적으로 돌 필요 없고 어떤 조합이든 많이 돌 수 있는 방법 찾기.k는 1 이상 5,000 이하인 자연수입니다.dungeons의 세로(행) 길이(즉, 던전의 개수)는 1 이상 8 이하입니다.dungeons의 가로(열) 길이는 2 입니다.dungeons의 각 행은 각 던전의 ["최소 필요 피로도", "소모 피로도"] 입니다."최소 필요 피로도"는 항상 "소모 피로도"보다 크거나 같습니다."최소 필요 피로도..

[프로그래머스] 소수 찾기

소수 찾기https://campus.programmers.co.kr/tryouts/140903/challenges 문제 파악순열 문제. 가장 효율적인 방법을 찾아보자.numbers는 길이 1 이상 7 이하인 문자열입니다.numbers는 0~9까지 숫자만으로 이루어져 있습니다."013"은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다. 접근 방법💡 permutations 문제와 비슷하지만, curr가 특정 길이 충족되면 result에 추가했던 것과 달리, 가는 도중에 보일 때마다 result에 curr값 추가한다.즉, 길이는 정해지지 않았고 길이가 어떻든 조건 만족하면 리스트에 추가.base case는 카운트되는 것으로 변경소수 구하는 함수는 isPrime() 으로 별도로 선언한다. (리..

[프로그래머스] 후보키

[문제]https://campus.programmers.co.kr/tryouts/140904/challenges  [문제 설명] 후보키프렌즈대학교 컴퓨터공학과 조교인 제이지는 네오 학과장님의 지시로, 학생들의 인적사항을 정리하는 업무를 담당하게 되었다.그의 학부 시절 프로그래밍 경험을 되살려, 모든 인적사항을 데이터베이스에 넣기로 하였고, 이를 위해 정리를 하던 중에 후보키(Candidate Key)에 대한 고민이 필요하게 되었다.후보키에 대한 내용이 잘 기억나지 않던 제이지는, 정확한 내용을 파악하기 위해 데이터베이스 관련 서적을 확인하여 아래와 같은 내용을 확인하였다.관계 데이터베이스에서 릴레이션(Relation)의 튜플(Tuple)을 유일하게 식별할 수 있는 속성(Attribute) 또는 속성의 집..

[JAVA/프로그래머스] 연속된 부분 수열의 합

[문제]https://campus.programmers.co.kr/tryouts/138985/challenges  [문제 설명]비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다.기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다.부분 수열의 합은 k입니다.합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다.길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다.수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 부분 수열의 시작 인덱스와 마지막 인덱스를 배열에 담아 return 하는 solution ..

[JAVA/프로그래머스] 완주하지 못한 선수

[문제]https://campus.programmers.co.kr/app/courses/24215/curriculum/lessons/322800#part-71108문제 설명수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다.마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요.제한사항마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다.completion의 길이는 participant의 길이보다 1 작습니다.참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로..

[JAVA/프로그래머스] 주식가격

[문제]https://campus.programmers.co.kr/tryouts/139163/challenges문제 설명초 단위로 기록된 주식가격이 담긴 배열 prices가 매개변수로 주어질 때, 가격이 떨어지지 않은 기간은 몇 초인지를 return 하도록 solution 함수를 완성하세요.제한사항prices의 각 가격은 1 이상 10,000 이하인 자연수입니다.prices의 길이는 2 이상 100,000 이하입니다.입출력 예pricesreturn[1, 2, 3, 2, 3][4, 3, 1, 1, 0]입출력 예 설명1초 시점의 ₩1은 끝까지 가격이 떨어지지 않았습니다.2초 시점의 ₩2은 끝까지 가격이 떨어지지 않았습니다.3초 시점의 ₩3은 1초뒤에 가격이 떨어집니다. 따라서 1초간 가격이 떨어지지 않은 것..

[JAVA/프로그래머스] 두 큐 합 같게 만들기

[문제]https://campus.programmers.co.kr/tryouts/139161/challenges문제 파악문제 설명길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다.큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다...