본문 바로가기

알고리즘

 (5)
[프로그래머스/lv1]비밀지도/c++ 비밀지도 문제 설명 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을..
[프로그래머스/lv1]나누어 떨어지는 숫자 배열/c++ 나누어 떨어지는 숫자 배열 문제 설명 array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요 코드 #include #include #include using namespace std; vector solution(vector arr, int divisor) { vector answer; int num = arr.size(); for(int i =0 ; i< num ; i++){ if(arr[i] % divisor ==0){ answer.push_back(arr[i]); } } if(answer.size()==0){ answ..
[프로그래머스/lv1]체육복/c++ 체육복 문제 설명 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번호의 학생이나 바로 뒷번호의 학생에게만 체육복을 빌려줄 수 있습니다. 예를 들어, 4번 학생은 3번 학생이나 5번 학생에게만 체육복을 빌려줄 수 있습니다. 체육복이 없으면 수업을 들을 수 없기 때문에 체육복을 적절히 빌려 최대한 많은 학생이 체육수업을 들어야 합니다. 전체 학생의 수 n, 체육복을 도난당한 학생들의 번호가 담긴 배열 lost, 여벌의 체육복을 가져온 학생들의 번호가 담긴 배열 reserve가 매개변수로 주어질 때, 체육수업을 들을 수 있는 학생의 최댓값을 return 하도록 solution..
[프로그래머스 / lv 1.] 모의고사/C++ 모의고사 문제 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 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 함수를..
[DP]집합의 분할 인적성을 공부하는 친구가 단체 톡방에 노가다 말고 순열공식이 없냐고 물어봤다. 해당 문제는 자연수의 분할 문제이다. 문득 작년 알고리즘 경진대회에서 집합의 분할 / 자연수의 분할 문제를 못풀어서 부들부들했던 기억이 새록새록 났다. 동적 계획법(DP)문제인 건 알았지만 끝내 점화식을 세우지 못했다. 1. 집합의 분할(partion of set)이란? 위의 문제는 같은 종류의 쿠키 10개를 나누는 문제이다. 하지만 집합의 분할은 서로 다른 쿠키 10개를 나누는 문제와 같다. 예를 들어 {1,2,3}은 다음과 같이 총 5개의 분할이 생긴다. 1|2|3 1|2,3 1,2|,3 2|1,3 1,2,3 이를 기호로 표현하면 S(n,k) n개의 원소를 k개의 집합으로 분류한 수를 의미한다. 저 위의 집합을 기호로 표현..

티스토리툴바