프로그래머스 문제 중 "소수 찾기"라는 문제를 푸는데 이렇게 풀었더니 몇몇 테스트케이스에서 오류초과가 났다. 구글링을 했더니 "에라토스테네스의 체" 라는 방법을 알게 되었다. "에라토스테네스의 체" 란? 범위에서 합성수를 지우는 방식으로 소수를 찾는 방법. 1. 1은 제거 2. 지워지지 않은 수 중 제일 작은 2를 소수로 채택하고, 나머지 2의 배수를 모두 지운다. 3. 지워지지 않은 수 중 제일 작은 3을 소수로 채택하고, 나머지 3의 배수를 모두 지운다. 4. 지워지지 않은 수 중 제일 작은 5를 소수로 채택하고, 나머지 5의 배수를 모두 지운다. 5. (반복) 답 def solution(n): answer = set(range(2,n+1)) for i in range(2,n+1): if i in a..

baaaarking dog 님 알고리즘강의 백트래킹파트를 참고하여 작성한 글입니다. 문제 https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 설명 백트래킹이란?? 현재상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘이다. 가지치기처럼 그러셔 모든 경우의 수를 따라 그려볼 수 있다 (상태공간트리 라고도 불린다) arr는 m개 만큼 원소를 담을 배열 isused는 1~N까지의 숫자가 사용되었는지 안되었는지 확인하는 배열 사용 - True..

baaaaarking dog님 알고리즘 강의를 참고한 내용입니당 문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 설명 재귀 문제를 풀때 절차지향적 사고로 풀기보단 귀납적 사고로 푸는것이 좋다. (절차지향적 사고로 생각하려다가 머리속이 꼬일 수 있기때문에) 그럼 귀납적 방법이란게 뭐냐?? 1번 도미노가 쓰러진다 k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다. 이 문제는 b가 최대 21억 가까이 되기때문에 시간초과가 발생할 것이다. 이 사진의 로직을 이용하면 1승을 계산할 수 있다. k승을 계산했으면 2..

문제 https://www.acmicpc.net/problem/1431 1431번: 시리얼 번호 첫째 줄에 기타의 개수 N이 주어진다. N은 50보다 작거나 같다. 둘째 줄부터 N개의 줄에 시리얼 번호가 하나씩 주어진다. 시리얼 번호의 길이는 최대 50이고, 알파벳 대문자 또는 숫자로만 이루어 www.acmicpc.net 코드 #include #include #include #include using namespace std; bool com(string& a, string& b) { int sum_a = 0; int sum_b = 0; if (a.size() != b.size()) //1. 길이가 다르면 짧은것 먼저 return a.size() < b.size(); for (int i = 0; i < ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 설명 이 문제는 DP로 풀 수 있다. 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정의하기 이 세가지 과정을 거쳐 문제를 풀 수 있다. 1. 테이블 정의하기 D[i]= i를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값 2. 점화식 찾기 D[12] =? D[1]부터 D[11]까지의 값을 다 알고 있다고 가정하면 1, 2, 3, ..., 11을 1로 만들기 위한 최소 횟수를 다 알고 있다고 하면 이런 상황에서 D[12]를 구하는 방법은 12에서 할 수 있는 연산을 생각하면 된다. D[4], D[6..