컴퓨터 알고리즘4 백트래킹[Back tracking] 1. 백트래킹 = 모든 경우의 수를 다 탐색하는 알고리즘 -> 조합이나 그래프와 같이 모든 경우의 수를 탐색해야 하는 문제에 적합 2. 어떻게 모든 경우의 수를 탐색하는가? 주어진 조건과 제약 사항을 만족하는 해를 찾는 과정에서, 현재 상태에서 조건을 만족하지 않으면 이전 단계로 돌아가서(Back) 다른 선택지를 시도 3. 예시 조합 문제. 3C2 def backtrack(nums, path, M, result): if M == 0: # M개의 수를 모두 선택한 경우 result.append(path[:]) # 결과에 추가 return for i in range(len(nums)): path.append(nums[i]) # 수 선택 backtrack(nums[i+1:], path, M-1, result).. 2023. 5. 21. Dynamic Programming Dynamic Programming, 동적 프로그래밍이란 무엇인가? 동적 + 프로그래밍. 동적의 정의는, [움직이는 성격의] 이다. 무엇이 어떻게 움직인다는 것일까? -> 찾아보니, 이름 붙인 사람도 별 뜻 없이 붙인 것이라고 한다..ㅎㅎ 동적 프로그래밍을 이해하기 위해, divide-and-conquer(분할 정복)방식과 비교해 보자. 분할 정복은 쉽게 말해 트리 구조를 생각하면 된다. 큰 문제를 작은 문제들로 점차 분해한 뒤 부모가 자식의 결과를 이용해 최종 결과를 도출한다. 동적 프로그래밍도 이와 비슷한 방식으로 동작한다. 단 차이점이 있는데, 분할 정복은 중간 결과를 저장하지 않고, 계산만 해나가는 반면, 동적 프로그래밍은 중간 결과를 저장함으로써 중복된 계산을 막을 수 있다는 점이다. 그렇다면 .. 2023. 4. 2. Algorithm Analysis 왜 알고리즘을 분석해야 하는가? 알고리즘 분석을 하는 것은 프로그래머에게 매우 중요한 일이다. 알고리즘을 분석할 줄 알아야, 알고리즘의 성능을 체크한 뒤 향상시킬 수 있고, 어느 알고리즘이 더 좋은 알고리즘인가에 대한 판단을 내릴 수 있기 때문이다. 최근 점점 더 방대한 양의 데이터가 컴퓨터 작업에 이용되면서 효율적인 알고리즘 작성의 중요성은 이전보다도 훨씬 높아졌다. 알고리즘 분석에는 총 3가지 측면이 있다. 시간 복잡도 공간 복잡도 최적성 시간 복잡도 먼저, 시간 복잡도에 대해 이야기해 보고자 한다. 사실 세 개념 중에서도 가장 많이 쓰이고, 그만큼 중요한 것이 바로 이 시간 복잡도이다. 시간 복잡도는 간단히 말해 "선택받은 연산자의 시행 횟수"라고 할 수 있다. 선택받은_ 이라는 단어에서 알 수 있.. 2023. 3. 17. Introduction to Computer Algorithms 알고리즘이란 무엇일까? 알고리즘의 정의는 다양하다. 컴퓨터 용어가 아닌 의미의 알고리즘도 정의가 다양할 뿐더러, 컴퓨터공학 내에서 알고리즘의 정의도 다양하다. 다음은 컴퓨터학에서 쓰이는 알고리즘의 다양한 정의의 두 가지 예이다. 몇 개의 값 혹은 값들의 집합을 input 으로 가지고 몇 개의 값 혹은 값드의 집합을 output 으로 도출하는 컴퓨터적 수행 절차. 입력값을 출력값으로 변환하는 컴퓨터적 단계의 순서 이를 보고 내 나름대로 알고리즘에 대한 정의를 내려 보았다. 아하, 컴퓨터 알고리즘이란, 인풋(입력값)을 가지고 컴퓨터가 이해할 수 있는 방식으로 인풋을 가공한 다음에 아웃풋(출력값)을 내는, 일종의 함수같은 것이구나 내가 내린 정의인 만큼, 틀릴 가능성은 열어 두어야 겠다. 이번 학기가 끝나고 .. 2023. 3. 16. 이전 1 다음
