Tie up loose ends!

2020년 전면 개편된 정보처리기사 필기 내용을 정리하면서 만든 블로그 '2020 시나공 정보처리기사 필기' 기본서를 바탕으로 정리함 http://mcchae.dothome.co.kr/ 정보처리기사 공부 블로그 중요도 높은 순(A>B>C) 및 키워드, 그리고 주요 특징 위주로 공부! [1과목] 소프트웨어 설계 Click! 1장. 요구사항 확인폭포수 모형, 나선형 모형, 애자일, 스크럼, XP, mcchae.dothome.co.kr

여러 경우 중 하나를 결정해야할 때마다 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종 값을 구함 (예제 1) 지불해야 하는 값이 4,720원일 때 1원, 50원, 100원, 500원으로 동전의 수가 가장 적게 지불할 경우는? (예제 2) 부분 배낭 문제(Fractional Knapsack Problem) - 무게 제한이 k인 배낭에 최대 가치를 가지도록 물건을 넣는 문제, 물건을 쪼개 일부분만 배낭에 넣을 수 있음 탐욕 알고리즘은 매순간 판단에 의존하므로 반드시 최적의 해를 구할 수 있는 것은 아니다. 따라서 근사치 추정에 활용된다. '시작' 노드에서 leaf node까지 가장 작은 값을 찾는 경로 탐욕 알고리즘 적용시 : 시작 → 7 → 12 이므로 19..

너비 우선 탐색(Breadth First Search) : 정점들과 같은 레벨에 있는 노드들(형제 노드들)을 먼저 탐색하는 방식(Queue 활용) 깊이 우선 탐색(Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식(Stack 활용) 노드 수를 V, 간선 수를 E라고 하면 BFS, DFS 모두 시간 복잡도는 O(V+E)

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법 탐색할 자료는 반드시 정렬이 되어있어야 함 탐색할 자료의 중간 값과 찾을 데이터를 비교해서 찾을 데이터가 더 크면, 자료의 첫번째 값에서 중간 값까지 값 중에서 다시 탐색함 시간 복잡도는 O(𝑙𝑜𝑔𝑛)

기준점(Pivot)을 정해서 기준점보다 작은 데이터는 왼쪽(Left), 큰 데이터는 오른쪽(Right)으로 모으는 작업을 재귀적으로 수행한 뒤, Left + Pivot + Right 값을 리턴하는 알고리즘 기준점은 보통 리스트의 맨 앞, 또는 맨 뒤의 데이터를 사용함 분할 정복(DAC; Divide and Conquer) 기법 중 하나로 재귀 함수를 이용함 시간 복잡도는 O(𝑛𝑙𝑜𝑔𝑛)

리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나누고, 각 부분 리스트를 정렬 후 다시 하나의 리스트로 병합함 분할 정복(DAC; Divide and Conquer) 기법 중 하나로 재귀 함수를 이용함 시간 복잡도는 O(𝑛𝑙𝑜𝑔𝑛)

동적 계획법 (DP; Dynamic Programming) 입력 크기가 작은 문제들을 해결한 후, 해당 문제의 해를 활용해서 보다 큰 크기의 문제를 해결하며 최종적으로 전체 문제를 해결하는 알고리즘 (상향식 접근법) Memoization 기법(프로그램 실행시 이전에 계산한 값을 저장하고 재활용해서 전체 실행 속도를 높이는 기술)을 사용함 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨 예) 피보나치 수열 분할 정복 (DAC; Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 병합하여 문제의 답을 얻는 알고리즘 (하향식 접근법) 일반적으로 재귀 함수로 구현함 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음 예) 병합 정렬, 퀵 정렬 (예제) 피보나치 수열

함수 안에서 동일한 함수를 호출하는 형태 파이썬은 한번에 호출되는 재귀 호출이 1000회 이하가 되어야 함 (예제 1) 팩토리얼 값을 구하는 함수 (예제 2) 숫자가 들어있는 리스트의 모든 요소 합을 구하는 함수 (예제 3) 거꾸로 읽어도 같은 단어(회문, Palindrome)를 판별할 수 있는 함수 (예제 4) n이 1이 될 때까지 홀수면 (3*n+1)을 하고, 짝수면 2로 나누는 함수 (예제 5) 정수 n을 1, 2, 3의 합으로 나타낼 수 있는 방법의 수를 구하는 함수