본문 바로가기

Algorithm44

[Algorithm] 조합 코드 구현 (Java) 완전탐색 알고리즘에서 모든 경우의 수를 계산한 후 결과 값을 찾는 방식이 자주 나온다. 그래서 재귀를 통해 조합을 구현하는 방법에 대해서 정리하려고 한다. 이때 기본 형식은 아래와 같다. 1. 조합(Combination) 조합은 고등학교 수학에서 경우의 수를 계산할 때 순열과 조합 파트로 배웠었다. 프로그래밍에서도 수학에서의 순열과 조합과 같다고 생각하면 된다. 잠시 고등학교 수학에서 배운걸 생각해보면 아래와 같다. 순서를 고려하지 않고 선택하는 방법 nCr : n개 중 r개를 순서에 상관없이 선택하는 방법의 수 nCr = nPr/r! / (n-r)!r! 간단히 예시를 들면 {1,2,3} 에서 2개를 뽑는 경우의 수 는 3C2로 3X2/2! = 6. 즉, 3가지가 나온다. {1,2} {1,3} {2,3}.. 2020. 7. 12.
[알고리즘] 프로그래머스-모의고사 (완전탐색) 1. 문제 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 1, 2, 3, 4, 5, ... 2번 수포자가 찍는 방식: 2, 1, 2, 3, 2, 4, 2, 5, 2, 1, 2, 3, 2, 4, 2, 5, ... 3번 수포자가 찍는 방식: 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, 3, 3, 1, 1, 2, 2, 4, 4, 5, 5, ... 1번 문제부터 마지막 문제까지의 정답이 순서대로 들은 배열 answers가 주어졌을 때, 가장 많은 문제를 맞힌 사람이 누구인지 배열에 담아 return 하도록 solution 함수를 작.. 2020. 6. 16.
[알고리즘] 프로그래머스-가장 큰 수 1. 문제 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 2. 나의 코드 import java.util.*; .. 2020. 6. 14.
[알고리즘] 해시 알고리즘 패턴 여러개의 해시 문제를 풀면서 이 알고리즘 문제 유형의 패턴을 분석해보기로했다. 1. 해시 알고리즘 문제인지 파악 문제에서 key와 value로 값으 저장해야한다면 해시 문제일 확률이 높다. 이럴 경우 HashMap 객체를 만들어서 그 안에 key와 value로 저장하고 활용하도록 한다. 2. 자주 사용하는 메소드 2.1 get, put, remove 메소드 map객체를 사용하는 기본 메소드이다. 각각 key값에 해당하는 값 조회, 입력, 삭제를 담당한다. map.get(key); map.put("값입력"); map.remove(key); 2. HashMap 객체 생성 아래 코드는 Key가 String이고, value가 Integer인 경우이다. HashMap map = new HashMap(); 2.3 .. 2020. 6. 14.
[알고리즘] 프로그래머스-베스트앨범 1. 문제 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 많이 재생된 장르를 먼저 수록합니다. 장르 내에서 많이 재생된 노래를 먼저 수록합니다. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요. 제한사항 genres[i]는 고유번호가 i인 노래의 장르입니다. plays[i]는 고유번호가 i인 노래가 재생된 횟수입니.. 2020. 6. 12.
[알고리즘] 프로그래머스-위장 1. 문제 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다. 스파이가 가진 의상의 수는 1개 이상 30개 이하입니다. 같은 이름을 가진 의상은 존재하지 않습니다. clothes의 모든 원소는 문자열로 이루어져 있습니다. 모든 문자열의 길이는 1 이상 20 이하인 .. 2020. 6. 12.

티스토리툴바