csmoon1010의 SW 블로그

0. 문제 유형 : 조합(완전탐색, 재귀), 소수(에라토스테네스의 체) 1. 문제 이해 (1) 주요 요구사항 - nums : 숫자들이 들어가 있는 배열 - nums 중 3개의 수를 더했을 때 소수가 되는 경우의 개수를 return (2) 제한사항 - nums의 길이 : 3개 이상 50개이하 → 완전탐색 가능 - nums의 원소 : 1이상 1000이하 → 3개 수의 합 < 3000, int형 사용 가능 - nums의 원소 : 중복된 숫자 없음 → 중복 조합 상황 고려X 2. 전략 (1) 소수 판단 : public boolean[] calcPrime(int n) - 나올 수 있는 소수의 범위 : 3000보다 작음 ▶ 3000까지의 수에 대해 에라토스테네스의 체로 소수 구하기 - 에라토스테네스의 체 esw-c..

0. 문제 유형 : 반복문의 적절한 활용, (하위 버전의) 완전 탐색 1. 문제 이해 programmers.co.kr/learn/courses/30/lessons/68644 코딩테스트 연습 - 두 개 뽑아서 더하기 정수 배열 numbers가 주어집니다. numbers에서 서로 다른 인덱스에 있는 두 개의 수를 뽑아 더해서 만들 수 있는 모든 수를 배열에 오름차순으로 담아 return 하도록 solution 함수를 완성해주세요. 제한 programmers.co.kr (1) 주요 요구사항 : 주어진 정수 배열 numbers에서 서로 다른 인덱스의 두 수를 뽑아 더해서 만들 수 있는 모든 수 (2) 추가 조건 : 배열에 오름차순으로 담아 return 2. 전략 (1) 두 개의 수를 뽑아 더하기 - 모든 경우의..

**주목해야 할 문제 : 완전탐색의 대표적인 예인 "순열, 조합"을 이용한 문제 1. 문제 이해 - numbers : 한자리 숫자가 적힌 종이 조각(1~7의 길이인 문자열) - numbers의 종이 조각들을 조합하여 만들 수 있는 소수의 개수 return 2. 전략 (1) 종이조각 나누기 : substring을 이용해 String 배열에 넣기 (2) 대상이 되는 경우들 구하기(완전 탐색) - 순열을 이용해 모든 경우를 담은 HashSet 만들기 - 순열 : 자리 고정 & swap 방식 이용 esw-csmoon.tistory.com/entry/%EC%88%9C%EC%97%B4%EC%A1%B0%ED%95%A9-%EC%99%84%EC%A0%84%ED%83%90%EC%83%89 순열/조합 (완전탐색) 1. 완전..

1. 완전탐색(Brute-force)? : 모든 경우의 수를 탐색하여 문제를 푸는 방식. 대표적인 예로 순열, 조합이 있음 2. 순열(Permutation, nPk) : n개의 요소들 중 k개를 뽑아 '정렬'할 수 있는 경우의 수 (1) 전통적인 순열 구하는 방법 - k개의 자리에 올 수 있는 요소의 개수를 세는 방식 - n x (n-1) x (n-2) x ... x (n-k+1) = n! / (n-k) ! - 단, 위의 수식은 단순히 "개수"를 구하는 방법일 뿐 완전탐색에 조건을 적용하기엔 부족함 (2) 순열 알고리즘 : 0~k번째에 수를 고정시킨다. [과정] ① depth번째 수 고정 - 방법1) 첫번째 수와의 swap을 통해 지정 - 방법2) 고정여부를 담은 visited배열(n과 같은 길이)에 표..

level2 카카오의 단체사진찍기 문제에서 완전탐색을 구현하는 법을 완전 잊어버렸다!!ㅠㅠ 그래서 전에 풀어봤던 완전탐색 문제들을 먼저 풀어보기로 했다. 1. 문제 이해 - 3명의 수포자가 일정한 규칙에 따라 문제를 찍음 1번 수포자가 찍는 방식: 1, 2, 3, 4, 5, 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, ... ▶ {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, ... ▶ {3, 3, 1, 1, 2, 2, 4, 4, 5..