Algorithm 728x90 (13) 썸네일형 리스트형 선택정렬(Selection Sort) C++ / 장단점 / 시간복잡도 / 공간복잡도 :: DANIDANI 알고리즘 개념 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 첫 번째 자리에는 첫 번째~마지막 원소 중 가장 작은 원소를, 두 번째 자리에는 두 번째~마지막 원소 중 가장 작은 원소를... 과정 주어진 배열에서 최솟값을 찾는다. 그 최솟값과 맨 앞에 위치한 값을 교체한다.(swap) 맨 앞에 위치한 값을 제외한 나머지 배열에 대해서 같은 방법으로 교체한다. 코드 for (int i = 0; i < n; i++){ int minIdx = i; for (int j = i + 1; j < n; j++){ if (arr[j] < arr[minIdx]) minIdx = j; } int temp = arr[i]; arr[i] = arr[minIdx]; arr[minIdx].. [백준] 2293 동전1 문제풀이 C++ :: DP(다이나믹 프로그래밍) :: DANIDANI 2293 동전1 https://www.acmicpc.net/problem/2293 동전 0 문제는 그리디 알고리즘을 활용했다면 동전 1 문제는 DP(Dinamic Algorithm, 다이나믹 알고리즘)을 사용한다. 예제에서 동전은 총 3 종류, 1 2 5 가 있다. arr 배열로 동전의 가치들을 저장해주고 문제는 dp 배열을 사용하여 접근한다. 먼저 dp [0]=1로 두는데, 이는 아무 동전도 선택하지 않은 경우도 하나의 경우의 수인 것이다. 각각의 동전에 대하여 for문을 돌린다. 먼저 동전 1에 대해서 10원을 만드는 경우의 수를 계산해준다. 1(=j)부터 10(=k)까지 dp[j] += dp[j - 1] 을 해준다. 동전 2에 대해서는 0원과 1원은 만들지 못하니 패쓰하고 j = 2부터 10(=k).. [백준] 1463 1로 만들기 문제풀이 C++ :: DP(다이나믹 프로그래밍) :: DANIDANI 1463 1로 만들기 https://www.acmicpc.net/problem/1463 DP(Dinamic Programming, 다이나믹 프로그래밍) 으로 푸는 문제! 시간 복잡도는 O(N) bottom-up 방식으로 for문을 사용해서 풀었다. index 가 n+1 인 배열을 만든다. index가 문제에서의 연산하는 숫자! dp [1] = 0로 초기화를 해준다. (1일 경우 연산 안 해도 됨) 할 수 있는 연산은 3가지 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 3가지 경우의 최솟값을 저장하면 된다. 예를들어 dp [4]인 경우 2로 나누어 떨어지는데 dp[4/2] + 1 = dp [2] + 1 = 2, dp [3] + 1 =.. [백준] 1806 부분합 문제풀이 C++ :: 투 포인터 :: DANIDANI 1806 부분합 https://www.acmicpc.net/problem/1806 기본적인 투 포인터 알고리즘 문제! (시간복잡도 O(N)) 문제 딱 보고 이중 for문으로 풀면 시간초과 날 수 있다. (시간복잡도 O(N^2)) #include #include #include using namespace std; int main() { int n, s; cin >> n >> s; vector arr(n); for (int i = 0; i > arr[i]; int start = 0, end = 0, sum = 0, minLen = 0x7FFFFFF; while (start = s) {// 현재 포인터의 합이 s보다 크거나 같으면 start ++ minLen = mi.. 투 포인터 알고리즘(Two Pointers Algorithm) :: DANIDANI 투 포인터 알고리즘은 1차원 배열이 있고 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태의 알고리즘이다. 절대 답이 되지 않는 경우는 계산하지 않아 시간을 단축시켜준다. Q. 배열에서 부분 배열의 합이 M이 되는 경우의 수를 구하여라! A1. 가장 쉽고 단순한 방법으로는 이중 for문을 이용해서 모든 경우의 수를 구할 수 있다. 시간 복잡도 O(N^2) A2. 투 포인터 알고리즘을 이용하면 시간복잡도를 O(N)으로 단축시킬 수 있다. 주로 적용되는 문제 유형 - 연속된 수들의 합 - 부분 배열의 합 풀이 방법 1. 포인터 2개가 같은 방향으로 진행해 나아가는 것 2. 포인터 2개가 양끝에서 반대로 진행하는 것 풀이 방법 1,2의 예제를 하나씩 풀어보자 대표.. 이전 1 2 다음
