알고리즘/개념공부(이것이코딩테스트다,스파르타) (3) 썸네일형 리스트형 1.Greedy(탐욕법) 1.그리디 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법 (단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토가 필요) -> 항상 최적의 해가 나오지 않을 수 있기 때문에 그리디를 사용할 땐 정당성을 분석해야한다. case1. 거스름돈 문제 O(K) : 화폐의 종류 K 만큼 시간복잡도가 걸린다. (정당성 : 10, 50 100, 500 중 큰 금액은 작은 금액의 배수이므로 큰 동전부터 거슬러 계산해주면 된다) case2. 1이 될 때 까지 : 조건(1.N에서 1을 빼거나, 2.N에서 K로 나눌 수 있다(나누어떨어질 경우만) (정당성 K값이 1보다 클 경우, 나누어 떨어질 경우에 나누기 부터 한다. case3. 곱하기 혹은 더하기 : 0,1인 경우는 더하기 나머지 숫자와.. 1. 알고리즘 알고리즘 개요 : 경우에 따라 시간과 공간에 얼마나 효율적인지 파악하여 적절한 알고리즘을 생각해 구현하자!! 0.Computational Thinking이란? Computational Thinking은 4가지로 되어 있습니다. 분해: 복잡한 문제를 작은 문제로 나눕니다. 패턴 인식: 문제 안에서 유사성을 발견합니다. 추상화: 문제의 핵심에만 집중하고, 부차적인 것은 제외합니다. 알고리즘: 이렇게 정의한 문제를 해결하는 절차입니다(일반화와 모델링은 여기에 포함됩니다). 복잡한 문제를 해결하는 것은 어렵지만, 작은 문제를 해결하는 것은 비교적 쉽습니다. 작은 문제를 해결하다 보면 복잡한 문제를 해결하게 됩니다. 컴퓨터 공학에서 배우는 알고리즘은 대부분 정형화된 문제에 대해 검증된 해법을 제시하는 과목입니다... 알고리즘 시작 알고리즘 개요 : 경우에 따라 시간과 공간에 얼마나 효율적인지 파악하여 적절한 알고리즘을 생각해 구현하자!! 0.Computational Thinking이란? Computational Thinking은 4가지로 되어 있습니다. 분해: 복잡한 문제를 작은 문제로 나눕니다. 패턴 인식: 문제 안에서 유사성을 발견합니다. 추상화: 문제의 핵심에만 집중하고, 부차적인 것은 제외합니다. 알고리즘: 이렇게 정의한 문제를 해결하는 절차입니다(일반화와 모델링은 여기에 포함됩니다). 복잡한 문제를 해결하는 것은 어렵지만, 작은 문제를 해결하는 것은 비교적 쉽습니다. 작은 문제를 해결하다 보면 복잡한 문제를 해결하게 됩니다. 컴퓨터 공학에서 배우는 알고리즘은 대부분 정형화된 문제에 대해 검증된 해법을 제시하는 과목입니다... 이전 1 다음
