알고리즘

학습 후 24시간 내에 복습일주일 후에 복습한 달 후 복습알고리즘 강의 후 약 10분 정도의 짧은 미팅일요일 스터디 전 일주일 공부 계획과 강의에서 어려웠던 부분 공유하기개인 블로그에 이번주에 배운 내용을 자기만의 방식으로 요약 정리해서 업로드하기포스팅을 보고 타인이

:whitecheckmark: 알고리즘이란? 개념 문제 해결 위한 단계적 절차 컴퓨터로 해결 가능 입력 존재, 결과(해) 출력 특성 ㅈㅎㅅ: 입력에 대한 올바른 해 ㅅㅎㅅ: 각 단계 수행 가능 ㅇㅎㅅ: 일정 시간 내 종료 ㅎㅇㅅ: 효율적일수록 가치 상승 표현 방법 단계

분할한 입력 -> 동일 알고리즘 적용 -> 해 계산 -> 취합부분문제: 분할된 입력에 대한 문제부분해: 부분문제의 해분할 정복(분할 가능 상태일 경우 '분할'로 돌아감)결합

n 개 숫자 중 k번째로 작은 숫자 찾기최소 숫자 k 번 찾기 => O(kn)오름차순 정렬 후 k번째 숫자 찾기 => O(nlogn) (힙 정렬)이진탐색 알고리즘 이용!그러나 이진탐색과는 다르게 정렬되어 있지 않은 배열랜덤 피봇 선택, 퀵 정렬처럼 피봇 기준 Small

그리디 알고리즘 개념 가능한 해 중, 가장 좋은 해를 찾는 문제 특징 전체 고려하지 않고 한 시점에서 최솟값/최댓값 데이터를 선택(= 근시안적) 한 번 선택하면 절대 번복하지 않는다. 4.1 동전 거스름돈 그리디 알고리즘 아이디어 남은 액수 초과하지 않는 조건 하,

남은 액수 초과하지 않는 조건 하, 욕심내어 가장 큰 액면의 동전부터 취하는 것!최소 동전 수 찾기Pseudocode입력: 거스름돈 액수 W거스름돈이 200원이고, 160원인 동전이 있다면?160원 1개, 10원 4개BUT! 100원 2개가 최적그리디 알고리즘을 적용한

버블 정렬선택 정렬삽입 정렬쉘 정렬힙 정렬합병 정렬퀵 정렬기수 정렬내부정렬: 입력의 크기가 주기억 장치 공간보다 크지 않은 경우외부정렬: 입력의 크기가 주기억 장치 공간보다 커서 입력을 여러 번 나누어 주기억 장치에 읽어들인 후 정렬하여 보조기억장치에 다시 저장이웃하는

비교 정렬 X자릿수별로 정렬어느 비교정렬 알고리즘보다 빠르다안정한 정렬입력 순으로 정렬LSD, MSDPseudo code입력: n 개의 r진수의 k자리 숫자출력: 정렬된 숫자 $$O(k(n+r))$$ 단, k 또는 r이 n보다 매우 작을 경우 $$O(n)$$입력 크

다항식 시간복잡도 가진 알고리즘으로 해결되는 문제들$$O(log n), O(n), O(nlogn),...$$NP 문제다항식보다 큰 시간복잡도를 가진 알고리즘으로 해결되는 문제들NP 알고리즘비결정적 다항식 시간 알고리즘해를 찾는 알고리즘 아님! 해를 다항식 시간 안에 확

논리식 여러 개 -> 논리식 모두 만족하는 부울 변수 값 찾기정수 집합 S 원소 합이 K가 되는 S의 부분 집합 찾는 문제S = {20, 30, 40, 80, 90}, 합 200 되는 부분 집합?{30, 80, 90}정수 집합 S 분할해서 원소 합 같은 부분 집합 찾기

8.2 정점 커버 문제

통 용량 C, 물건 n개일 때 모든 물건을 가장 적은 수의 통에 채우는 문제그리디 방법으로 넣을 통 결정최초 적합 (First Fit)첫 번째 통부터 차례로 살펴보며, 가장 먼저 여유가 있는 통에 새 물건을 넣는다.다음 적합 (Next Fit)직전에 물건을 넣은 통에

문제가 매우 복잡근사 알고리즘 설계가 어려움다항식 시간 내 찾기 어려움백트래킹 기법분기 한정 기법유전자 알고리즘모의 담금질 기법해를 찾는 도중에 막히면 되돌아가서 해를 탐색하는 방법최적화 문제(최솟값, 최댓값 찾는 문제)와 결정 문제(해가 존재하는지 yes or no)

적당히 좋은 해들의 집합(여러 개의 해)에서 출발, 적자생존의 개념으로 최적화 문제를 해결현재 세대의 해로부터 다음 세대의 해를 생성해가며 마지막 세대에서 가장 우수한 해를 반환후보해각 세대에서의 해들최적해 또는 최적해에 근접한 해가 될 수 있으므로 후보해후보해의 평가