나의 공부 기록

합병 정렬 퀵 정렬 공통점 주어진 리스트를 두 개로 분할하고, 각각을 정렬 차이점 분할할 때, 단순하게 두 부분으로 나눔 분할할 때, 기준 아이템(Pivot Item)을 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킴 각 부분 정렬이 끝난 후, '합병'이란 후처리 작업이 필요 각 부분 정렬이 끝난 후, 후처리 작업이 필요로 하지 않음 퀵 정렬의 최악의 시간 복잡도는 O(n^2) 평균 복잡도는 nlogn

🧵 백트래킹(Backtracking) 해를 찾는 도중에 막히면(해가 아니면) 되돌아서 다시 해를 찾아가는 기법 최적화 문제, 결정 문제(문제의 조건을 만족하는 해가 존재하는지의 여부를 'yes' 또는 'no'로 답하는 문제. ex: 미로 찾기, n-Queen 문제, Map cloring, 부분 집합의 합(Subset Sum)문제 등)를 해결 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않음 반대로 해답의 가능성이 있으면 유망함. 가지치기(Pruning) : 유망하지 않은 노드가 포함되는 경로는 더 이상 고려하지 않음. 1. 상태 공간 Tree의 깊이 ..

출처 : sw expert academy 파이썬 SW문제해결 기본 - Stack2 1차시 01 계산기 🎇 중위표기식의 후위표기식으로 변환 방법1 1. 수식의 각 연산자에 대해서 우선순위에 따라 괄호를 사용하여 다시 표현 2. 각 연산자를 그에 대응하는 오른쪽 괄호의 뒤로 이동 3. 괄호 제거 A*B-C/D 1단계 : ((A*B)-(C/D)) 2단계 : ((AB)*(CD)/)- 3단계 : AB*CD/- 🎨 스택을 이용한 중위표기식의 후위표기식으로 변환 방법2 1. 입력 받은 중위표기식에서 토큰(수식에서 의미 있는 최소의 단위)을 읽음 2. 토큰이 피연산자이면 토큰을 출력 3. 토큰이 연산자(괄호포함)일 경우 - 우선순위가 높으면 스택에 push - 우선순위가 안높으면 연산자의 우선순위가 토큰의 우선순위보다..

😼 구현 방법 1. 문제를 해결할 수 있는 재귀 관계식을 구한다. 2. 가장 작은 입력사례로부터 상향식 방법으로 문제 해결. 🐸 상향식과 하향식 상향식 접근은 재귀를 사용하지 않는다. 부분 문제를 해결한 후 table에 저장한다. table에 저장된 값을 이용해서 계산해나간다. 하향식 접근은 재귀를 사용한다. 🐣 동적계획법은 문제를 작게 나누고 상향식 방법으로 점차 큰 문제 해결. 오버헤드 발생이 없다.(재귀호출과 비교했을 때 장점) 재귀호출은 내부 시스템 호출 Stack을 사용하는 오버헤드가 발생하기 때문. ★ 분할정복과 동적계획법 비교 - 문제를 작은 사례로 분할하여 해결한다는 점은 동일 - 분할정복은 재귀 호출을 통해 분할하여 정복(Top-Down) - 동적계획은 메모이제이션을 통해 상향식으로 정복..

def merge_sort(array): if len(array)

재귀 호출 수행할 작업을 작게 쪼갠 다음에 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출한다. 더이상 쪼개지지 않을 때 return을 해주는 조건문이 있어야 한다. Factorial 구현 예제 def solution(n): fact=1 for i in range(1, n+1): fact*=i return fact​ 반복문으로 구현 def solution(n): if n

1. Divide : 문제를 작은 문제로 나눈다. 2. Conquer : 작은 문제들을 재귀로 해결한다. 3. Combine : 답을 모두 합친다. merge sort 1. divide : p와 r사이에서 q의 위치를 찾는다. p와 r을 더하고 2로 나누고 내려간다. 2. Conquer : 윗 단계에서 만들어진 subarrays를 재귀적으로 정렬 3. Combine : 정렬된 subarrays를 하나의 정렬된 array로 만듦 ex) array=[14, 7, 3, 12, 9, 11, 6, 2] (p=0 and r=7) 1. divide : q=3 2. conquer : array[0..3]=[14, 7, 3, 12] and array[4..7]=[9, 11, 6, 2] [3, 7, 12, 14], [2,..

최악의 경우에 시간복잡도는 O(nlog2n) heap은 2가지 조건을 만족한다. 1. complete binary tree 2. heap property를 만족해야 함. - max heap property : 부모 노드 값 >= 자식 - min heap property : 부모 노드 값

안녕하세요 : ) 오늘은 검색알고리즘에 대해 알아보겠습니다. 1. 검색 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업이다. 자료들은 각각을 구별하여 인식할 수 있는 키인 탐색키를 가진다. 1-1. 순차검색(Sequential Search) 일렬로 되어있는 자료를 순서대로 검색하는 방법이다. 리스트나 연결 리스트와 같은 순차구조로 구현된 자료구조에서 유용하다. 구현이 쉽다. 검색 대상이 많은 경우 수행시간의 증가로 비효율적이다. 정렬, 정렬을 하지않는 2가지 경우가 있다. 정렬되지 않은 자료의 검색과정 1. 첫번째 원소부터 순서대로 검색대상과 키값이 같은 원소가 있는지를 비교하여 찾는다. 2. 키값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환. 3. 자료구조의 마지막에 갈 때까지 검색대상을 찾지 ..

안녕하세요 : ) 오늘은 부분집합에 대해 알아보겠습니다. 1. 부분집합의 합 문제 유한 개의 정수로 이루어진 집합이 있을 때, 부분집합 중에서 집합의 원소를 모두 더한 값이 0이 되는 경우가 있는지를 알아내는 문제. 완전검색기법으로 부분 집합 합 문제를 풀기 위해서는 먼저 모든 부분집합들을 만든 후 각 부분집합의 합을 계산한다. 각 원소를 부분집합에 포함시키거나 포함시키지 않는 2가지 경우를 모든 원소에 적용한 경우의 수와 같다. 따라서 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개이다. bit=[0,0,0,0] for i in range(2): bit[0]=i for j in range(2): bit[1]=j for k in range(2): bit[2]=k for m in ran..