본문 바로가기

Algorithm

 (5)
20210630 Algorithm 05 : 탐욕 알고리즘(동전, 부분배낭), 최단경로 알고리즘 이해, 다익스트라 알고리즘 Algorithm 05 Greedy algorithm(탐욕 알고리즘) 의 이해 Greedy algorithm 또는 탐욕 알고리즘 이라고 불림 최적의 해에 가까운 값을 구하기 위해 사용됨 여러 경우 중 하나를 결정해야 할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식 총체적인 고려보단, 현재 활용하는 것에서 최적을 선택 탐욕 알고리즘 예 예시1: 동전 문제 지불해야 하는 값이 4720원 일 때 1원, 50원, 100원, 500원 짜리 동전으로 가장 적은 동전의 수로 값을 지불하는 경우 가장 금액이 큰 동전부터 최대한 지불해서 값을 채우는 방식으로 구현 가능 500원 짜리로 4500원까지 채우기 -> 9개 100원 짜리로 4700원까지 채우기 -> 2개 1..
20210629 Algorithm 04 : Binary Search(이진 탐색), Sequential Search(순차 탐색), Graph의 이해, BFS(너비우선탐색), DFS(깊이우선탐색) Algorithm 04 Binary Search (이진 탐색) 탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 정열이 되어 있다는 가정하에 순차적으로 탐색하지 않고, 중간을 탐색해서 어디에 있는지 판단하는 방식 분할 정복 알고리즘과 이진 탐색 분할 정복 알고리즘 : Divide(문제를 하나 또는 둘 이상으로 분할), Conquer(나눠진 문제가 충분히 작고, 해결가능하면 해결하고 그렇지 않으면 다시 분할함) 이진 탐색: Divide : 리스트를 두 개의 서브 리스트로 나눔 Conquer : 검색할 숫자 > 중간값 -> 뒷부분의 서브 리스트에서 검색할 숫자를 찾음 검색할 숫자 앞부분의 서브 리스트에서 검색할 숫자를 찾음 이진 탐색도 분할 정복 알고리즘에 해당하므로, 전..
20210628 Algorithm 03 : 동적 계획법(Dynamic Programming), 분할정복(Divide and Conquer), 퀵 정렬(Quick sort), 병합정렬(Merge sort) Algorithm 03 동적 계획법 (Dynamic Programming)과 분할 정복(Divide and Conquer) 동적 계획법 (DP) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구해서 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용 Memoization(메모이제이션) : 프로그램 실행시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 작은 문제에서의 결과값을 메모이제이션을 통해서 기억하고, 큰 문제에서는 따로 작은 문제를 다시 실행시키지 않고 기억하고 ..
20210625 Algorithm 02 : 공간 복잡도, 재귀용법(Recursive call), 재귀 패턴, 재귀용법 활용한 예제(리스트합, 회문, 홀짝, 123표현) Algorithm 02 공간 복잡도 시간 복잡도 : 얼마나 빠르게 실행 되는지 공간 복잡도 : 얼마나 많은 저장 공간이 필요한지 실행시간이 짧고, 공간도 적게쓰는 알고리즘이 좋은 알고리즘 둘다 만족시키기는 어려움 완전하진 않지만, 시간과 공간은 반비례적 경향이 있음 최근에는 대용량 시스템이 보편화 되면서, 시간복잡도를 우선시킴 공간 복잡도 대략적인 계산 필요함 기존 알고리즘 문제는 공간 복잡도 고려해서 만들어진 경우가 많아 시간 + 공간 복잡도에 대한 제약 사항이 있음 공간 복잡도 프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함 총 필요 저장 공간 고정 공간 (알고리즘과 무관한 공간): 코드 저장 공간, 단순 변수 및 상수 가변 공간 (알고리즘 실행과 관련 있는 공간) : 실행 중 동적으로 필..
20210624 Algorithm 01 : 알고리즘, Bubble sort(버블 정렬), Selection sort(선택정렬), Insertion sort(삽입 정렬) Algorithm 01 알고리즘 실제로 개발자들이 해당 알고리즘을 하나하나 작성하여 쓰지는 않음, 모두 좋은 패키지로 함수화 되어 나와 있음 그럼에도 익히는 이유는 지금까지 존재하는 알고리즘 중에 잘 만들어진 알고리즘을 익힘으로서 잘 알고리즘을 만들수 방법을 잘 이해하고, 이를 기반으로 새로운 문제들을 풀수 있는 능력을 기르기 위함 알고리즘 연습 방법 효과적인 알고리즘을 작성하기 위해서는 바로 코드를 작성하지 말고, 전통적인 알고리즘 연습 방법으로 진행하자 문제를 쓰고, 연습장에 고안해서 최종적으로 에디터에 코드를 작성해서 테스트를 함 효율적인 알고리즘을 고안을 하고 테스트를 해야함 연습장과 펜 준비 알고리즘 문제를 읽고 분석 간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서,..

티스토리툴바