그리디 알고리즘(Greedy Algorithm) 그리디 알고리즘은 "매 선택에서 당장 좋은것만을 선택해 나가는 방법"을 뜻한다. 특정 기준에 따라서 좋은 것을 선택해야하는 알고리즘이기 때문에 문제에서 어느정도 제시해준다. 그리고 좋다, 나쁘다의 기준을 세워야하기 때문에 정렬 알고리즘과 섞여서 나오는 문제들이 많다. 간단한 예제 (거스름 돈) 그리디 알고리즘을 대표하는 문제로 '거스름 돈' 문제가 있다. 자판기에 거스름돈을 배출해야 하는데 , 자판기에는 500, 100, 50, 10원짜리가 무수히 존재한다. 이때 거슬러줄 최소 동전의 개수를 구하라. (단, 거스름 돈은 항상 10의 배수이다.) 이러한 문제가 있다면, 무조건 큰 단위의 동전(500원)으로 최대한 거슬러주고, 그 다음 가능한 큰 단위의 동전(..

문제 링크 : www.acmicpc.net/problem/2581 2581번: 소수 M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다. 단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다. www.acmicpc.net 소수와 관련된 문제는 왠만하면 전부 에라토스테네스를 사용하는게 편한것 같다. 일단, 테스트케이스에서 주어진 범위만큼 에라토스테네스의 체를 사용하여 소수를 구해놓는다. 그리고 문제의 조건에 맞 게 출력해주면 끝. infinitt.tistory.com/232 알고리즘 (1) - 수학 : 유클리드 호제법 , 에라토스테네스의 체 (나머지 연산, 최대 공약수, 최소�� 수학과 관련한 기초문제에는 크게 3가지 분류로 ..

문제 링크 : https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 두개의 리스트가 주어진다. 첫번째 리스트가 탐색할 대상이고, 두번째 리스트의 각 요소가 target 이다. 이를 for문을 통해 각각 이분탐색으로 문제를 해결했다. 이진탐색 , 이분탐색 https://infinitt.tistory.com/286 알고리즘 ) 이진 탐색, 이분 탐색 (Binary serach) _ python 재귀 * 이진 ..

문제 링크 : https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. �� www.acmicpc.net * 듣도 못한사람 N 과 보도 못한사람 M의 공통된 부분을 사전순으로 정렬해서 출력하면 된다. 공통된 부분이라 함은 set의 교집합을 이용하면 편할것같다는 생각이 들었다. https://infinitt.tistory.com/19?category=1071951 파이썬(Python) 기초 (8) 데이터 타입(Data Type) - 집합 (set) add , remove , int..

문제링크 :https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net itertools의 combination을 사용하여 풀었다. (자동으로 n개중에 r개를 뽑는 조합(combination)을 반환해주는... ) https://infinitt.tistory.com/114 순열과 조합 ( n! , nPr , nCr ) - (itertools) combinations, permutations + 중복순열, 중복조합 *n! ..

다이나믹 프로그래밍 (Dynamic Programming) : DP 개념 : 문제를 더 작은 단위로 쪼개어 해결하는 알고리즘. (분할 정복 알고리즘과 비슷하다. 차이점은 바로 아랫줄.) 핵심은, 그 작은 단위의 문제들이 반복해서 일어나기 때문에, 그값들을 저장해놓는 식으로 해결해나가는 알고리즘 (다이나믹이라는 이름에는 아무 뜻도 없다고 한다.) *다이나믹 프로그래밍을 사용하기 위한 조건 1. 부분 문제들이 겹치는가 (반복 되는가) ex ) 피보나치 수 : N번째 항(큰 문제) = N-1번째 항(작은 문제) + N-2 번째 항(작은 문제) 피보나치의 특성을 잘 살펴보면 Fibo(10)을 구할때는 Fibo(9)+Fibo(8)...........Fibo(1) 까지 모두 필요합니다. 이때 메모이제이션을 통해 배..