본문 바로가기

알고리즘31

Level2 - 귤 고르기 귤들의 크기가 담긴 배열이 주어진다. [1, 3, 2, 5, 4, 5, 2, 3] 1번 크기 1개2번 크기 2개3번 크기 2개4번 크기 1개5번 크기 2개 개수가 주어지는데 이 중 서로 다른 종류의 수의 최솟값을 리턴해라 6개의 개수가 주어진다면 2번 3번 4번을 담아야 최소크기로 6개를 담을 수 있다.키 값 형태로 접근 HashMap class Solution { public int solution(int k, int[] tangerine) { HashMap hashMap = new HashMap(); int max = 0; for(int x : tangerine){ if(hashMap.containsKey(x)) hashMap.put(x,hashMap.get(x)+1); else hashMap.put.. 2023. 5. 25.
Level2 - 점프와 순간 이동 한 칸 이동은 +1 두 칸 이동은 +0 #1 5 -> 2번만에 #2 6 -> 2번만에 #3 5000 -> 5번만에 입출력 예 #2 처음 위치 0 에서 1 칸을 앞으로 점프한 다음 순간이동 하면 (현재까지 온 거리 : 1) x 2에 해당하는 위치로 이동할 수 있으므로 위치 2로 이동합니다. 이때 1 칸을 앞으로 점프하면 위치3으로 이동합니다. 이때 다시 순간이동 하면 (현재까지 온 거리 : 3) x 2 이동할 수 있으므로 위치 6에 도착합니다. 이 경우가 건전지 사용량이 가장 적으므로 2를 반환해주면 됩니다. (1) 0 부터 어떻게 하면 5까지 아니면 6까지 5000까지 몇번만에 갈지를 생각하느라 고생을 오래 했다. 한칸 이동인 경우와 두 칸 이동인 경우를 DFS로 하여 탐색을 하면 답이 나오지만 범위가 .. 2023. 5. 23.
Level2 - 예상 대진표 레벨 2 부터는 단순 알고리즘이 아니라 문제를 어떻게 해결해야하는지 찾는데에 시간이 많이 걸리는거 같다. 대진표가 있다면 A랑 B랑 몇번째에 만날지 예측해주라는 문제 A = 1 B = 2 라면 1번째에 바로 만나는거라 1을 리턴 A = 1 B = 4 라면 2번째에 만나는 거라 2를 리턴 A = 4 B = 5 라면 최종 3번째 니깐 3을 리턴 무조건 A와 B는 이긴다는 규칙이 있으니깐 이런식으로 이긴다면 계속 좁혀지는걸 확인 뭔가 DP를 사용해야 하나 하다가 그냥 DFS각이 보여서 DFS로 접근 (찾게 된 규칙) + 둘의 차이가 1이면 리턴 && A가 홀수이면 리턴 A = 2 , B = 4 라면 , 위의 식이 만족이 안되니 다시 위로 승격, 그럼 2는 1이되고 4는 2가 되며 위의 조건이 만족하고 2를 리.. 2023. 5. 22.
Level2 구명보트 ( 탐욕법 Greedy ) 🤔어떻게 하면 효율 적으로 태울지 limit이 100 이고 (제한인원 2명) 10 20 60 80 (정렬하고) 의 몸무게를 가진 손님이 있으면 어떻게 하면 딱 100kg에 딱 맞춰 태울까를 고민했었다. 하지만 생각을 해 보다 최소 보트의 수를 구하는 문제이기에 (10 80) 먼저 하나 ( 20 80 ) 을하나 똑같다. 그 이유는 정렬이 되어있고 + (제한인원이 2명이고) 탐욕적으로 최대 큰 수인 80에서 10을 선택하지 않으면 그 밑에 수는 80보다 작기에 100까지 최대 값을 설정할 수 없기 떄문이다. 그렇기에 탐욕적으로 큰사람 한명을 태우고 작은사람 한명이 가능하면 2명을 태워 나가고 불가능 하다면 1명을 태워 나간다. ⭐투포인터알고리즘⭐ public static int solution(int[] p.. 2023. 5. 21.
인프런 JAVA 알고리즘 정리(Greedy Algorithm 1~8번) 1. 씨름 선수 키 몸무게가 있고 자신보다 키 몸무게 둘다 큰 사람이 없다면 선택 -> (183, 65) - 키가 제일 큼 -> (180, 70) - 자신보다 키가 큰 사람중 자신보다 몸무게 큰 사람이 없음 -> (170, 72) - 자신보다 키가 큰 사람중 자신보다 몸무게 큰 사람이 없음 1. 사람을 키순으로 정렬한다. ( 첫번째 사람은 일단 키가 제일 크니 픽) 2. 그 뒤로 몸무게가 앞 사람보다 크다면 픽 ( 앞사람보다 키는 작지만 몸무게는 제일 높다는 소리) public static void main(String[] args) { Scanner sc = new Scanner(System.in); int num = sc.nextInt(); ArrayList arr = new ArrayList(); .. 2023. 5. 14.
인프런 JAVA 알고리즘 정리(DFS, BFS 활용 8~15번) AccessDenied Access Denied 7VKㄹㄷ7ㄹㄹBS6FQ704K885 qIEAFwzuh+2t2fNXlzFm6QdvDF27FjvRN9nj2hacWFKfOatXaZ3PPoFx/vSRNTt10d60TRXD/nw= 8. ⭐수열 추측하기⭐ // 1부터 N 까지의 숫자가 한 개씩 적혀있는데 그 숫자를 추측해라. // N이 4라고 하고 마지막 값이 16이 주어진다면 맨 위의 숫자는? 여러 값이 있다면 가장 앞에 오는 것을 출력 조합을 먼저 구하고 -> 순열를 바꿔가며 재귀를 돈다. 4 의 값 (3*1) + (1*3) + (2*3) + (4*1) = 16 규칙이 존재 4자리수면 1 3 3 1 을 곱하는 최종 결과라는... 5자리면 1 4 6 4 1 1. 1 3 3 1 b { 1, 3, 3, 1 } 2... 2023. 5. 13.
(MySQL LEVEL-2) 재구매가 일어난 상품과 회원 리스트 구하기 - 프로그래머스 USER_ID 가 재구매한 상품이 있는지 있다면 USER_ID와 PRODUCT_ID를 출력 위 테이블에서는 1번 유저가 3번,4번을 재구매 했고 2번이 4번을 재구매했다. 이와 같은 결과를 출력해라 이 문제를 풀기 앞서 알아야 하는 개념 GROUP BY 그룹바이는 컬럼리스트중 같다면 하나의 그룹으로 만들어 준다. - 위의 테이블에서 GROUP BY USER_ID로 처리하게 된다면 1 2 3 의 그룹으로 묶인다. 하지만 저 문제에서는 하나의 컬럼이 아닌 두 개의 컬럼이 밑에서 중복이 된다면 그 두 개의 컬럼을 기준으로 중복된 값만 묶이길 원한다. 그렇다면 GROUP BY뒤에 2개의 컬럼을 설정해 주면 된다. 답 SELECT USER_ID, PRODUCT_ID FROM ONLINE_SALE GROUP BY .. 2023. 5. 12.
(MySQL LEVEL-2) 자동차 평균 대여 기간 구하기 - 프로그래머스 이 테이블에서 CAR_ID 별로 평균 대여일이 7일 이상인 CAR_ID를 대여일이 내림차순으로 출력하고 대여일이 같은게 있다면 CAR_ID를 내림차순으로 출력해라 이 문제를 풀기 앞서 알아야 하는 함수 DATEDIFF( 날짜, 날짜 ) 두 날짜사이의 일 수를 계산 ROUND( 숫자, 숫자위치) 숫자의 어느지점에서 반올림을 할 지 뒤에 숫자를 적는다. SUM 합 GROUP으로 묶은 합 (집계함수) COUNT 갯수 GROUP으로 묶은 개수 (집계함수) 답 SELECT CAR_ID,ROUND(SUM(DATEDIFF(END_DATE, START_DATE)+1)/COUNT(END_DATE),1) AS AVERAGE_DURATION FROM CAR_RENTAL_COMPANY_RENTAL_HISTORY GROUP B.. 2023. 5. 11.
인프런 JAVA 알고리즘 정리(DFS, BFS 활용 1~7번) 1. 합이 같은 부분집합(DFS : 아마존 인터뷰) // 배열 {1, 3, 5, 6, 7, 10}이 입력되된다면 2 집합으로 나누었을 때 같은 합이 있냐? // { 1, 3, 5, 7 } == { 6, 10 }이 나올 수 있으므로 같은 합이 있다 -> YES 출력 // DFS를 알고리즘을 사용해서 각각의 숫자를 사용할때와 안할때를 비교해서 최종 합이 같은지 비교 public String DFS(int L, int[] arr){ if(L == n){ int sum=0; for(int x : result) sum+=x; int total_t = total-sum; System.out.println(sum); // *현재까지 사용한 값과 사용하지 않은 값의 합이 같으면 YES 리턴* if(sum==total_.. 2023. 5. 11.

티스토리툴바