문제 https://programmers.co.kr/learn/courses/30/lessons/12982?language=java 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr 풀이 그리디 유형의 문제이고, 처음에 자바로 백트래킹으로 접근했다가 테스트케이스는 통과하지만 시간초과가 났었다. 최종적으로 문제 해결은 C++로 진행하였다. 우선 최대한 많은 부서들의 물품을 구매하는 것이 정답이기에 부서별 신청 금액인 d를 오름차순 정렬해주었다. 오름차순 정렬을 통해 신청 금액이 낮은 부서부터 차례대로 값을 끼워넣어 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/42862 코딩테스트 연습 - 체육복 점심시간에 도둑이 들어, 일부 학생이 체육복을 도난당했습니다. 다행히 여벌 체육복이 있는 학생이 이들에게 체육복을 빌려주려 합니다. 학생들의 번호는 체격 순으로 매겨져 있어, 바로 앞번 programmers.co.kr 풀이 문제 태그 자체는 그리디 문제인데 필자는 조건을 많이 쳐서 구현식으로 문제를 풀었다. 일단 전체 체육복의 갯수를 관리하는 num이라는 테이블을 만들어주었고, lost에 대해선 -1, reserve에 대해선 +1을 해주어 초기값 세팅을 하였다. 이후에는 체육복의 테이블에 대해 for문을 돌아서 크게 3가지 분기로 나누어주었는데 i) i가 첫번째 사람일때 ..
문제 https://programmers.co.kr/learn/courses/30/lessons/12953 코딩테스트 연습 - N개의 최소공배수 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배 programmers.co.kr 풀이 유클리드 호제법을 통해 문제를 해결할 수 있었다. 일반적인 최소공배수 구하기 문제와 다르게 2개의 자연수만 비교하여 최소공배수를 리턴하는 것이 아닌 N개(N >= 2)가 모두 만족하는 최소공배수를 구해야하는 것이 조금 달랐다. 이는 최소공배수를 여러번 구해주면 되는데 예를들어 자연수 A, B, C가 있다고 가..
문제 https://programmers.co.kr/learn/courses/30/lessons/1845 코딩테스트 연습 - 폰켓몬 당신은 폰켓몬을 잡기 위한 오랜 여행 끝에, 홍 박사님의 연구실에 도착했습니다. 홍 박사님은 당신에게 자신의 연구실에 있는 총 N 마리의 폰켓몬 중에서 N/2마리를 가져가도 좋다고 했습니다. programmers.co.kr 풀이 문제를 풀기위한 알고리즘은 따로 필요 없었고, 오히려 쉽게 생각해야 금방 풀 수 있는 문제이다. 필자는 처음에 백트래킹으로 접근하려했지만 생각해보니 자료구조인 Set을 사용하면 금방 풀 수 있을 거 같아서 Set을 통해 해결할 수 있었다. Set에 모든 nums의 원소들을 담아주면 중복 없는(종류가 모두 다른) 값들만 얻을 수 있고 이후 Set의 크..
