huiyu's blog

- 잘하는 사람과 못하는 사람의 생산성 차이가 스무배- 대부분 컴퓨터 과학 교육 과정이 프로그래밍의 기술과 지식을 가르칠 뿐, 그것을 스스로 응용할 수 있는 능력을 주지 못하기 때문.- 대부분의 교과서에서는 발전 과정의 최종 결과물인 복잡한 개념과 도구를 먼저 제시하고, 그 개념의 이론에 대해 설명한 뒤, 곧장 연습문제를 풀도록 합니다. -> 이러한 방법은 학문 발전의 결과물에 대한 체계적인 지식을 학생에게 주입하는 데는 좋을지 몰라도, 문제의 답을 슷로 고안할 수 있는 학생을 기르기에는 턱없이 부족합니다. : 프로그래밍은 어려운 만큼 재미있는 작업이기도 합니다. 문제를 푸는 것도 그렇습니다. 문제가 풀리지 않을 때의 괴로움은 문제가 풀렸을 때의 기쁨과 그 과정에서 얻은 통차을 자신의 것으로 만들었을 때..

1. 동적 계획법(Dynamic Programming)이란?분할 정복과 같은 접근방식을 갖고 있습니다. 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 각 조각의 답을 계산하고, 이 답들로부터 원래 문제에 대한 답을 계산해 내기 때문입니다. 차이가 발생하는 부분은 문제를 나누는 방식입니다. 부분문제가 여러번 사용될 수 있을 때 여러번 중복 계산하는 것이 아닌, 한번만 계산하고 저장해둬 재활용해 사용합니다. (a)서로 연관이 없는 부분문제 (b)서로 의존하고 있는 부분문제 (a)는 서로 연관이 없어 단순히 재귀 호출을 통해 문제를 풀어도 한 부분문제를 한 번만 해결합니다. (b)는 부분문제가 서로 의존하고 있어, 단순 재귀로 풀면 중복 계산이 많아집니다. 예를 들면 cde는 abcde를 해결할 때, cdef..

병합정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이다. 병합정렬 작동 순서1. 정렬한 데이터 집합을 반으로 나눈다.2. 나누어진 하위 데이터 집합의 크기가 2이상이면 이 하위 데이터 집합에 대해 1을 반복한다.3. 원래 같은 집합에서 나뉘어져 나온 하위 데이터 집합 둘을 병합하여 하나의 데이터 집합으로 만든다. 단 병합할 때 데이터 집합의 원소는 순서에 맞춰서 정렬한다.4. 데이터 집합이 다시 하나가 될 때까지 3을 반복한다. 5, 1, 6, 4, 8, 3, 7, 9, 2의 데이터를 정렬한다고 할 때 다음의 과정을 거쳐서 정렬을 한다.먼저 알고리즘의 1-2 과정을 반복해 데이터 집합을 나눈다.파란색 블록은 중간의 기준점을 의미 분할을 끝낸 뒤에는 '정복'을 수행, 합칠..

분할정복이란?문제를 더 이상 나눌 수 없을 때까지 나누고, 이렇게 나누어진 문제들을 각각 풂으로써 결국 전체 문제의 답을 얻는 알고리즘 분할 정복의 과정 1. 분할(Divide) : 문제가 분할이 가능한 경우, 2개 이상의 하위 문제로 나눕니다. 2. 정복(Conquer) : 하위 문제가 여전히 분할이 가능한 상태라면 하위 집합에 대해 1-을 수행합니다. 그렇지 않다면 하위 문제를 푼다. 3. 결합(Combine) : 2과정에서 정복된 답을 취한다. 분할정복법은 어떤 것에 적용하는가? 1. 문제를 작게 쪼개는 것이 가능한가?(Divide) 2. 쪼개진 문제들을 조합하여 문제의 답을 효율적으로 구할수 있는지(Merge & Conquer)