🕹️ 알고리즘

[알고리즘]다이나믹 프로그래밍(DP, 동적계획법)

다이나믹 프로그래밍이란? 다이나믹 프로그래밍(Dynamic Programming)은 다른말로 동적계획법 이라고 합니다. 저도 처음에는 동적계획법을 듣고 왜 동적계획법일까? 했는데 이름 지으신분이 그냥 이 이름이 멋있어서 이렇게 지었다고 하네요... DP(다이나믹 프로그래밍)알고리즘은 백준 사이트 알고리즘별로 문제풀기에서 가장많은 문제수를 가지고 있어요! 그만큼 종류도 다양하고, 출제빈도도 높습니다. ​ DP는 작은문제를 풀어서 큰문제를 해결하는 알고리즘입니다. 여기서 주의할점은 작은문제들을 여러번에 걸쳐서 다시 푸는일이 없도록 어딘가에 값을 저장해두고, 필요할 때 그 값만 가져와서 사용한다는 점입니다. ​ 즉, 문제를 여러번 풀지않고 단 한번만 계산을 할 수 있는 거죠. ​ ​ 예) 피보나치 수열 위는 ..

[C++] 코딩테스트를 위한 C++ 기본

안녕하세요:) 코테 문제 풀 때 주로 C++사용하는데요 여러문제에서 아주유용하게 사용하면서, 자주사용한다 싶은 코드위주로 요약해서 설명드릴려고해요 (사실 정리해두고 제가 쓰려고하는...) 1.using namespace std; 저는 처음에 책으로 c++배울때는 무조건 std를 일일이 붙여줘야하는 줄 알았습니다. 위 코드를 상단에 써놓으면 std를 일일이 안붙여주어도 cin,cout등을 그냥 사용가능합니다. #include using namespace std; int main() { cout > N; int* arr = new int[N]; delete[] arr; //메모리 해제 } +2차원배열 동적할당 이것도 은근 많이 씁니다! 1차원 배열을 만든뒤 각 행에 배열을 추가하여 2차원 배열을 나타내도록 ..

[알고리즘]삽입정렬(Insertion Sort)

삽입정렬이란? 두번째 수부터 자신 왼쪽의 수와 비교하여 내가 더 작으면 왼쪽으로 이동하고, 크면 오른쪽 위치를 유지합니다. 위치를 유지했으면 그 수에 대한 비교는 종료 왼쪽으로 이동했으면, 다시 자신의 왼쪽 수와 비교를 반복합니다. 내 왼쪽과 비교 내가 더 크면 현재 위치 유지 내가 더 작으면 왼쪽 수와 교체(swap) 다시 1번단계부터 비교 반복 마지막 수 까지 비교완료하면 종료 시간복잡도 최악의 경우는 역으로 정렬되어 있는 경우 n-1, n-2, ... 1만큼 비교하여 시간복잡도 O(n^2)입니다. 소스코드(C++) #include using namespace std; void insertion_sort(int arr[],int size){ //삽입정렬 for(int i = 1;i0&&arr[j-1]..

[알고리즘]선택정렬(Selection Sort)

선택정렬이란? 선택정렬은 앞에서부터 쭉 탐색하면서 가장 작은 수를 찾습니다.(오름차순의 경우) 그리고 그 수를 (정렬되지 않은 부분의)맨앞의 수와 교체합니다. 이 과정을 정렬되지 않은 수가 1개 남을 때까지 반복하면 됩니다. 이 때 배열을 정렬된 부분과 정렬되지 않은 부분으로 나눌 수 있습니다. 탐색은 정렬되지 않은 부분에 대해서만 이루어 집니다. 주황색 - 정렬된 부분 흰색 - 정렬되지 않은 부분 하늘색 - 정렬되지 않은 수 중 가장 작은 수 정렬되지 않은 부분에서 가장 작은 수를 찾는다. 정렬되지 않은 부분의 맨 앞의 수와 가장 작은 수를 교환(swap)한다. 교환된 가장 작은 수는 정렬된 부분이 된다. 정렬되지 않은 부분에서 위 과정을 반복하고, 모두 정렬되면 종료 시간복잡도 가장 작은 수를 찾는데..

[알고리즘]버블 정렬(Bubble Sort)

정렬 알고리즘에는 대표적으로 병합정렬, 퀵정렬, 삽입정렬, 선택정렬, 버블정렬 등이 있습니다. 이번에는 그 중에서 제일 간단하게 구현할 수 있는 버블 정렬을 알아보겠습니다! 버블 정렬(오름차순) 버블 정렬은 앞에서부터 두수를 비교하며 가장 큰수를 찾고, 남은 수를 다시 두개씩 비교하며 그 다음으로 큰 수를 찾는 과정을 원소가 1개 남을 때까지 반복하는 정렬 알고리즘입니다. 시간 복잡도 위 예시에서 n = 5이므로 제일 큰 숫자인 5를 찾는데까지 4번(=n-1번)이 걸리고 다음으로 큰 숫자인 4를 찾는데까지 3번(=n-2번)이 걸립니다 총 4+3+2+1번이 걸립니다. n개의 수를 정렬하는 시간은 n-1+n-2+n-3+...1이므로 ((n-1)(n-2))/2 = O(n^2)입니다. 최선, 최악의 경우 모두 ..

[백준-9020]골드바흐의 추측(C++)

https://www.acmicpc.net/problem/9020 9020번: 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수 www.acmicpc.net 모든 짝수는 두 소수의 합으로 표현할 수 있다는 것이 골드바흐의 추측입니다. 짝수가 주어졌을 때 합으로 표현할 수 있는 두 소수를 찾으면 됩니다. (여러개일 경우 차이가 가장 적은 두 소수를 찾으면 됩니다) 예) 8 = 3+5 10 = 5+5 16 = 5+11 이전에 포스팅한 소수찾기 문제를 응용하면 풀 수 있는 문제입니다. 문제 해결한 알고리즘 주어진 짝수를 n이라 하겠습니다..

[백준-1978]소수 찾기(C++)

https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 입력받은 수 중에서 소수의 개수를 찾는 간단한 문제입니다. 예전에 프로그래머스에서 풀어봤는데 그 때 막코딩으로 풀었다가 계속 시간초과 났던게 생각나네요ㅜㅜ 우리가 수학시간에 배워서 알고있던 소수의 정의로 푸는 것 보다 좀더 빠르게 구현할 수 있는 소수찾는 알고리즘이 있습니다. 소수 찾는 알고리즘 소수 배열이 있다고 생각해봅시다. 소수 배열에는 일단 확실히 소수인 2만 들어가있습니다. 2부터 시작해서 3,4,5,6,7,8,9... 이 수들이 소수인지 판별해볼건데요 방..

[백준-1011]Fly me to the centauri(C++)

https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행�� www.acmicpc.net 출발지에서 도착지까지 이동하는데, 처음, 마지막 속도는 1이고 속도를 k-1,k,k+1로 설정하여 이동할 수 있습니다. 이 때 도착지까지 최소한으로 이동하는 횟수를 구하는 문제입니다. 예) 출발지 = 1, 도착지 = 5 1, 2, 1 이렇게 이동하면 최소한으로 이동한 것이 됩니다. 횟수는 3이므로 답은 3입니다. 처음에 문제 풀 때, 시간 초과가 계..