https://www.acmicpc.net/problem/15663 문제 풀이이전 N과 M문제들과 다른점은 이제 입력한 수들이 중복된 수가 들어갈 수 있다는 점이다. 또한 문제 조건에서 중복되는 수는 여러번 출력하면 안된다고 하였기 때문에 그에 대한 처리를 해줘야 한다.처음에 temp에 들어갈 수는 7 다시 백트래킹을 하고 난 뒤 다음에 들어갈 수는 1,9 7은9랑 겹치지 않으므로 그대로 출력. 그다음 temp는 9인데 그림에서 마지막에 1,9에서 9가 들어올 수인데 temp과 중복 되므로 if문 안드로 들어오지 못하고 넘어감. #include #include #include #include #include #include #include #include #include #include #include ..

15650번: N과 M (2)문제자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열고른 수열은 오름차순이어야 한다입력첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)출력한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 문제 풀이이 문제는 백트래킹을 사용하여 문제를 풀었습니다. 백트래킹이란 ? 현재 상태에서 가능한 모든 후보군을 따라 들어가며 탐색하는 알고리즘입니다.위와 같은 방식으로 한 배열와 특정한 수가 쓰였는지에 대한 배열을 선..

2748번: 피보나치 수 2-문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. -입력첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.문제풀이기본적인 피보나치수 문제중 하나입니다. 여기서 중요한 점 부분은 "n은 90보다 작거나 같은 자연수이다." ==>( ..

1629번: 곱셈자연수 A를 B번 곱한 수를 알고 싶다. 단 구하려는 수가 매우 커질 수 있으므로 이를 C로 나눈 나머지를 구하는 프로그램을 작성하시오.첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. 문제 풀기간단하게 for문을 사용해서 풀어서 A를B번 곱한 수를 구한다면 int, long long의 범위를 한참 벗어납니다(A와 B는 각각 대략 20억의 수이므로). 따라서 다른 접근방법을 생각해야 합니다.  주의 해야할 점  정답 코드#include #include #include #include #include #include #include #include #include #include #include #inclu..

동적 계획법⇒ 복잡한 문제를 단순한 하위 문제로 나눠서 접근하는 방법⇒ 중복 계산을 줄이기 위해, 이전에 구한 해를 활용 이전의 해를 활용해야 효율적인 문제의 조건최적 부분 구조문제의 최적 해결책이 하위 문제의 최적 해결책으로부터 구성되는 경우중복 부분 문제동일한 하위 문제가 여러번 계산 됨 예시 1 : 팩토리얼 예시 2 : 피보나치 수 동적 계획법 적용하는 법 예시 1 : 계단 오르기 ⇒N개의 계단이 존재하고, 한번에 1개 혹은 2개의 계단을 오를 수 있음. 계단을 오르는 방법의 총 수는? 1. 예제 입력으로 출력을 만드는 과정을 직접 손으로 작성2. 과정을 일반화. 이때 최종해를 구하는 과정을, 이전해를 구하는 과정을 통해 나타낼 수 있는지 확인한다.3. 2번의 과정에서 이전해를 구하는 과정이 ..

코테에서 정렬은 언제 필요한가? 대표적인 정렬 알고리즘 삽입 정렬 왼쪽 : 정렬된 영역 / 오른쪽 : 비 정렬된 영역정렬된 영역이 점점 확장되어 비 정렬된 영역이 사라짐비 정렬된 영역의 맨 앞의 원소를 정렬된 영역의 적절한 곳에 추가용도: 작은 데이터 셋에서 효율적이며, 이미 부분적으로 정렬된 배열에서 높은 성능을 보입니다.삽입정렬 과정 1. 첫 번째 원소를 정렬된 부분으로 간주합니다. 2. 다음 원소를 정렬된 부분과 비교하여, 올바른 위치에 삽입합니다. 3. 모든 원소가 정렬된 부분에 삽입될 때까지 2의 과정을 반복합니다.   삽입 정렬의 최고 / 최악 케이스 최선의 경우: O(n) - 이미 정렬된 배열의 경우평균의 경우: O(n^2) - 일반적인 경우최악의 경우: O(n^2) - 역순으로 정렬된 ..