SWEA 13

[SWEA]파이썬 SW문제해결 기본 - LIST 1 : Greedy Algorithm

파이썬 SW문제해결 기본 - LIST 1 04 Greedy Algorithm 04. Greedy Algorithm(탐욕적 알고리즘) ① 탐욕 알고리즘이란? ▣ 탐욕 알고리즘(Greedy Algorithm) - 최적 해를 구하는 데 사용되는 근시안적인 방법 - 각 순간에 최적이라고 생각되는 것을 선택해 나가는 방식 - 지역적으로는 최적이지만, 그것의 최종 해답이 최적이라는 보장은 없음 ▣ 탐욕 알고리즘 수행 과정 1) 해 선택 : 현재 상태에서 부분 문제의 해를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가한다. 2) 실행 가능성 검사 : 새로운 부분 해 집합이 실행 가능한지 확인한다.(문제 제약 조건 위반 검사) 3) 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는지를 확인한다. 전..

[SWEA]파이썬 SW문제해결 기본 - LIST 1 : Exhaustive Search(완전 탐색)

파이썬 SW문제해결 기본 - LIST 1 03 Exhaustive Search(완전 탐색) 03. Exhaustive Search ① 완전 검색 소개 ▣ 완전 검색(Exhaustive Search) - 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 - 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다. - 일반적으로 경우의 수가 적을 때 유용하다. - 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리다. - 그러나 해답을 찾아내지 못할 확률이 낮다. - 우선 완전 검색으로 해답을 도출한 후 성능 개선을 위해 다른 알고리즘 사용 ② Baby-gin Game ▣ Baby-gin 게임 - 0~9 사이의 숫자 카드에서 임의의 카드 6장을 뽑았을 때, 1) 3장의 카드..

[SWEA]파이썬 SW문제해결 기본 - LIST 1 : 알고리즘, 리스트

파이썬 SW문제해결 기본 - LIST 1 01 알고리즘 02 리스트 01. 알고리즘 ① 알고리즘 개요 ▣ 알고리즘이란? - 유한한 단계를 통해 문제를 해결하기 위한 절차나 방법 ▣ 알고리즘 표현법 - 슈도 코드 : 일반적인 언어 코드를 흉내 내어 알고리즘을 써 놓은 코드 - 순서도 : 프로그램이나 작업의 진행 흐름을 순서에 따라 여러 가지 기호나 문자로 나타낸 도표 ② 알고리즘의 성능 분석 ▣ 무엇이 좋은 알고리즘인가? - 정확성 : 얼마나 정확하게 동작하는가? - 작업량 : 얼마나 적은 연산으로 원하는 결과를 얻어내는가? - 메모리 사용량 : 얼마나 적은 메모리를 사용하는가? - 단순성 : 얼마나 단순한가? - 최적성 : 더 이상 개선할 여지없이 최적화되었는가? ▣ 시간 복잡도 ≒ 빅-오(O) 표기법 ..