본문 바로가기

Algorithm

 (7)
조합의 수 구하기 순열과 조합.. 학창시절 nPr이니 nCr이니 하며 수학시간에 열심히 배웠던 기억이 있다. 알고리즘을 공부하면서 다시 보려고 하니 까먹은 기억을 되살리려다보니 기억보다 기록을 해두자 라는 생각으로 정리하게 되었다. 먼저, 간단한 개념은 알고 있었다. 내가 이해가 잘안됬던 것은.... 그렇다.. 조합에서 위와 같은 식이 어떻게 적용이 되는 것인지 바로 확 와닿지 않았다. 공부하다 보면서 아! 그렇구나 하며 다시 알게 되었고, 이를 까먹지 않기 위해 알기 쉽게 정리하려고 한다. 서론이 너무 길었던 것 같다.. 자 지금부터 예를 들어 설명해 보겠다. 여기 아래와 같이 6명의 사람이 있다. 면접을 보는 사람들이다. 총 6명의 사람이 면접을 보았고, 이 회사에서는 3명을 채용하고자 한다. 먼저 조합의 개념을 간단..
피보나치 수열(배열 vs 재귀 비교) 피보나치 수열은 알고리즘 및 자료구조를 공부하는데 있어서 여러 유형에서 기본으로 나오게된다. 아래 두가지 예시를 가지고 비교해보며 설명하고자 한다. 물론 기억력의 한계가 있다보니 기록해두려는 목적 또한 있다는 점도 포함! 먼저 배열을 이용한 피보나치 예시이다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 피보나치 수열 public class infArray4 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Sy..
(Lv2) 더 맵게 문제 설명 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) Leo는 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞습니다. Leo가 가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요. 제한 사항 scovil..
(Lv2) 가장 큰 수 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbersreturn [6, 10, 2..
(lv2) 주식가격 문제 설명 초 단위로 기록된 주식가격이 담긴 배열 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초간 가격이 떨어지지 않은 것으로 봅니다. 4초 시점의 ₩2은 1초간 가격이 떨어지지 않았습니다. 5초 시점의 ₩3은 ..
완주하지 못한 선수(Lv1) 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요. 제한사항 마라톤 경기에 참여한 선수의 수는 1명 이상 100,000명 이하입니다. completion의 길이는 participant의 길이보다 1 작습니다. 참가자의 이름은 1개 이상 20개 이하의 알파벳 소문자로 이루어져 있습니다. 참가자 중에는 동명이인이 있을 수 있습니다. 입출력 예 participantcompletionreturn [leo, kiki, ed..
두 개 뽑아서 더하기(Lv1) 문제 정리 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한사항 numbers의 길이는 2 이상 100 이하입니다. numbers의 모든 수는 0 이상 100 이하입니다. 입출력 예 numbersresult [2,1,3,4,1] [2,3,4,5,6,7] [5,0,2,7] [2,5,7,9,12] 문제 생각 정리 이중 for문을 쓸줄 아는지? 중복 제거를 위해서 List 혹은 Set 이용 등을 사용할 수 있는지 오름차순 정렬을 할수 있는지를 물어보는 것 같다. 아래는 내가 작성한 코드이다. import java.util.ArrayList;..

티스토리툴바