부트캠프교육중/알고리즘12 Greedy Algorithm (탐욕 알고리즘) 알고리즘 문제를 푼다 = 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현한다는 것 탐욕 알고리즘 -말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법. # Greedy Algorithm 문제 해결 단계 1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다. 2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다. 3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복합니다. # 특징 - 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 .. 2023. 4. 5. 공간 복잡도(Space Complexity) -알고리즘이 수행되는 데에 필요한 메모리의 총량을 의미. -프로그램이 필요로 하는 메모리 공간을 산출하는 것을 의미. -프로그램이 요구하는 공간은 고정적인 공간과 함께 가변적인 공간을 함께 요구합니다. 고정적인 공간은 처리할 데이터의 양에 무관하게 항상 요구되는 공간으로서, 프로그램의 성능에 큰 영향을 주지 않는다. 그러나 가변적인 공간은 처리할 데이터의 양에 따라 다르게 요구되는 공간으로서 프로그램의 성능에 큰 영향을 줍니다. -공간 복잡도 계산은 시간 복잡도 계산과 비슷하게 빅 오 (Big-O) 표기법으로 표현합니다. 아래의 가장 간단한 공간복잡도 예시를 보겠습니다. function factorial(n) { if(n === 1) { return n; } return n*factorial(n-1); .. 2023. 4. 5. 시간복잡도 #효율적인 방법을 고민한다 = 시간 복잡도를 고민한다 #시간복잡도를 고려한다 = 입력값의 변화에 따라 연산을 실행할때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가 효율적인 알고리즘을 구현한다 = 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다. #시간 복잡도를 표기하는 방법 -Big-O(빅-오) -Big-Ω(빅-오메가) -Big-θ(빅-세타) -위 세 가지 표기법은 시간 복잡도를 각각 최악, 최선, 중간(평균)의 경우에 대하여 나타내는 방법이다. -시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다. -빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문입니다. "최소한 특정 시간 이상이 걸린다" 혹은 "이 정도 시간.. 2023. 4. 5. 알고리즘 #알고리즘은 어떤 문제를 해결하기 위해서 일련의 절차를 정의하고, 공식화한 형태로 표현한 일종의 문제 풀이 방법, 해(解)를 의미합니다. 이런 알고리즘은 프로그래밍에서는 input 값을 통해 output 값을 얻기 위한 계산 과정을 의미합니다. #알고리즘이라 명시 되려면 일정한 조건들을 반드시 만족해야만 합니다. -입력(Input) : 알고리즘은 출력에 필요한 자료를 입력받을 수 있어야 합니다. 이 상황에서는 제일 먼저 빨간불인 신호등이 초록불이 되려면 5분이라는 시간을 입력 받아야 합니다. 하나 더 알아야 할 것은 신호등은 항상 시간을 입력받아야 알고리즘이 동작하지만 꼭 입력을 받지 않아도 되는 알고리즘도 있습니다. (ex. 원주율(pi)의 1조 번째 자리 수를 구하려는 경우 입력은 없지만 출력은 있다.. 2023. 4. 5. 이전 1 2 3 다음
