문제 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의 크..
문제 https://programmers.co.kr/learn/courses/30/lessons/12921?language=cpp 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 풀이 알고리즘 문제에서 많이 나오는 소수 찾기 문제이다. 판별해야 하는 범위가 1 ~ n인데 n이 최대 1000000이므로 일반적인 소수 판별로는 시간 초과가 날 것이다. 필자는 에라토스테네스의 체로 접근하여서 문제를 해결할 수 있었다. 0, 1은 소수가 아니므로 처음부터 제외시켰고 바깥 for문의 범위를 n..
