{Programing}/Algorithm21 알고리즘 - 동적 계획법(Dynamic Programming) 큰 문제를 잘게 나누어 풀어놓고 그 해들을 이용해 큰 문제의 해를 찾는 방법. 1. 최적 부분 구조 : 문제의 답이 잘게 나눈 문제에 대해서도 답이어야함. 2. 부분 문제 반복 : Top - Down or Down - Top 으로 문제를 나누어 내려올 수 있음. 큰 문제와 나눈 문제와의 풀이법이 같아야함. 똑같은 문제를 여러번 푸는 낭비를 막기 위해 "메모이제이션" 기법을 사용. 메모이제이션 : 미리 구해둔 정답을 메모해놓고 만약 다음에 같은 문제를 다시 풀어야 하면 불러와서 쓰는 방법. 대표적 예) 점화식. 등비,등차수열 하향식 방법 : Top - Down 방식으로 큰 문제를 계속 나누어 풀 수 있을 정도까지 나누고 문제를 풀어서 다시 올라가는 방식. 상향식 방법 : Down - Top 방식으로 작은 .. 2020. 3. 4. 알고리즘 - 투 포인터(two pointer) 이미 정렬이 완료된 배열 or 리스트에서 두 개의 인덱스(포인터)를 이용해 포인터에 담긴 값과 원하는 결과를 비교해 원하는 해를 구하는 알고리즘. 이중 반복문으로도 해결가능한 문제이나 O(N^2) 의 시간이 소요. 정렬이 안된 배열에서도 O(NlogN), 정렬된 배열에선 O(N)의 시간으로 단축됨. ex) 배열 내 합이 S가 되는 순서쌍 찾기. 배열의 앞 뒤에서 포인터로 좁혀오며 순서쌍을 찾찾. 투 포인터(앞 : l 뒤 : r)가 지시하는 두 요소의 합을 S 와 비교 l 2020. 3. 4. 알고리즘 - Greedy(탐욕) 문제 해결 기준으로 조건탐색 시기 기준으로 최적의 요소를 선택해서 해결해가는 알고리즘. 즉, 매우 근시안적 선택을 이용해 문제를 해결하는 방식. 최적화 문제에 자주 사용됨. 주의할 점은 " 최적을 선택하는 조건 " 이다. 조건이 잘못되면 해를 구할 수 없는 경우가 생길 수 있기 때문. 거스름돈 문제와 최소비용 신장 트리에서 많이 사용됨. Greedy 알고리즘은 최선의 해를 구하는 것이 아닌 최적 or 적당히 납득할만한 해를 구하는 것이 목표. 2020. 3. 4. 알고리즘 - 완전 탐색 어떠한 문제에 대해 모든 경우의 수를 찾아 답을 찾아내는 알고리즘. 반복문이나 재귀 함수로 작성. 반복문을 사용한 구현이 더욱 직관적이며 알아보기 쉽다. 재귀함수를 이용할 때에는 꼭 탈출 조건을 명확하게 발생시킬 수 있어야하고 호출 깊이가 너무 깊어지지 않도록 해야한다. 호출 깊이를 제한해야하는 이유는 메모리 때문. 함수는 호출되면 스택에 데이터가 저장되며, 재귀함수로 인해 스택 오버플로우의 발생가능성이 높아지기 때문. 코딩테스트에서 메모리 초과 or 런타임 에러로 오답처리되면 메모리 문제를 체크해보자. 2020. 3. 4. 이전 1 2 3 4 5 6 다음