1. 순열 예시) 원소 개수 n = 4 -> 집합 = {A, B, C, D}, 4!인 24가지의 경우가 존재 따라서 상태 공간 트리에서의 단말노드의 수는 24개이다. 24개의 후보해가 존재한다는 것이고 이것은 단말노드의 수와 같다. 노드 방문 시마다 원소를 가리키는 인덱스 값을 저장 같은 원소 수를 갖는 부분집합과 순열의 상태 공간 트리의 높이는 같다. 순열의 경우 높이가 다른 노드는 선택지 수가 동일하지 않다. 선택할 때마다 다음 선택의 선택지 수가 하나씩 줄어든다. 소스코드 # order[] : 순열의 순서를 저장하는 리스트 def permutation(order, k, n): if k == n: # 다 선택하면 print_order_array(order, n): # 출력 else: check = [..

1. n-Queens 문제 n x n 체스판에서 n개의 퀸들을 서로 위협하지 않도록 배치하는 문제 2. 백트래킹 초기 상태에서 목표 상태로 가는 경로를 탐색하는 기법 해를 찾는 도중 해가 아니면 되돌아가서 다시 해를 찾는 기법 최적화(optimize)문제와 결정(decision)문제를 해결할 수 있다. 최적화 문제 미로 찾기, Subset sum 등 결정 문제 n-Queen, Map coloring 등 루트까지 되돌아갔는데 더이상 선택지가 없다면 답이 없는 것이다. 백트래킹의 핵심은 상태 공간 트리를 탐색하는 것! 해를 찾기 위한 선택의 과정을 트리로 표현 트리의 내부 노드는 해로 가는 중간 상태 트리의 단말 노드는 하나의 후보해에 대한 최종 상태 상태 공간 트리를 깊이 우선 탐색(DFS)하는 방법이 백..

https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 1주차에 배운 내용은 다음과 같다. 1. 완전검색 2. 탐욕 알고리즘 3. 분할 정복 스터디 진행은 이번 주 배운내용을 간략하게 복습하고, 각 알고리즘 문제를 풀고 풀이과정을 공유하는 방식으로 진행했다. 1. 완전검색 모든 경우의 수를 탐색하고 해답에 해당되는 경우를 선택한다. https://ohdowon064.tistory.com/189?category=859997 Algorithm 01. 완전 검색 1 1. baby-gin 게임 0~9사이에서 6장을 뽑고 3장의 카드가 연속숫자일 경..

1. 알고리즘 유한한 단계를 통해 문제해결 절차 및 방법 예) 1~100 합 1. 1 + 2 + 3 + ... 2. 100 * (1 + 100) / 2 = 5050 => 이런 해결 방법을 절차적으로 정리한것. 알고리즘을 효율적이어야 한다. > 입력이 커질 수록 효율에 따라 실행시간 차이 발생 알고리즘 설계 -> 실행 필요한 지원분석 -> 효율성 제시 효율성 -> 복잡도. 복잡도가 높을 수록 효율성 저하. 1. 공간 복잡도 2. 시간 복잡도 시간 복잡도 입력 크기에 대한 함수로 표기. 점근적 표기를 사용한다. 입력 n이 무한대로 커질 때를 가정. 1. 빅오, 2. 오메가, 3. 세타 빅오표기법 - worst case 점근적 상한을 의미한다. O(g(n)) = f(n)이라는 것은 g(n)이 모든 n에 대해서..

1. 정렬 2개 이상의 자료를 특정 기준에 의해 오름차순 또는 내림차순하는 것이다. Key : 자료를 정렬하는 기준이 되는 특정 값 예) 서류 번호대로 정렬하기 -> 키는 서류 번호가 된다. 2. 버블 정렬(Bubble Sort) 인접한 두 개의 원소를 비교하여 자리를 계속 교환하는 방식 첫번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막 자리까지 이동한다. 한 패스가 끝나면 가장 큰 원소 또는 가장 작은 원소가 마지막 자리로 정렬된다. 시간복잡도 = O(n^2) 예시) 55, 7, 78, 12, 42 1. 첫번째 패스 55 7 78 12 42 7 55 78 12 42 7 55 78 12 42 7 55 12 78 42 7 55 12 42 [78] 이렇게 한 패스가 끝나면 가장 큰 원소가 마..

1. 탐욕 알고리즘(Greedy Algorithm) 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식 최적 해를 구하는데 사용되는 근시안적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택의 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그것들을 계속 수집하여 최종적인 해답을 만들었다고 하여 그것이 최적이라는 보장은 없다. 일반적으로, 머리속에 떠오르는 생각을 검증없이 바로 구현하면 Greedy 접근이 된다. 2. 탐욕 알고리즘 수행 과정 1. 해 선택 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분 해 집합(Solution Set)에 추가한다. 2. 실행 가능성 검사 새로운 부분..

1. 완전 검색(Exhaustive Search) 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법이다. Brute-force 또는 Generate-and-Test 기법이라고도 불린다. 모든 경우의 수를 테스트한 후, 최종 해법을 도출한다. 일반적으로 경우의 수가 상대적으로 작을 때 유용하다. 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만 해답을 찾아내지 못할 확률이 작다. 따라서 주어진 문제를 풀 때, 우선 완전 검색으로 접근하여 푼 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다. 예시) Baby-gin Game 0 ~ 9사이의 숫자카드에서 임의의 카드 6장을 뽑아, 3장의 카드가 연속되면 run이라하고, 3장의 카드가 동일..

Python 1. 인터프리터 언어로 독립적인 플랫폼 2. 객체지향 3. IoT분야의 라즈베리파이, 빅데이터 자료분석 등에 쓰인다. 프로그램 실행속도 VS 개발속도 과거에는 실행속도가 느린 파이썬이 주목받지 못하다가 하드웨어의 성능개선과 개발 시간 단축에 관심이 집중되며 파이썬을 많이 사용한다. Yes, Python is Slow, and I Don't Care. A rant on sacrificing performance for productivity. 변수 1. 파이썬에서는 모든 자료가 객체 > Java, C에서 사용되는 기본형 타입 변수도 파이썬에서는 객체 2. 변수의 선언은 따로 없다. > 변수에 값을 초기화 시 변수가 메모리에 생성된다. > 하나의 변수에 다른 타입의 값을 변수에 저장할 수 있다...

해당 알고리즘 게시글은 SW Expert Academy를 공부하고 정리하기 위해 작성한 글입니다. 1. 알고리즘 유한한 단게를 통해 문제를 해결하기 위한 절차나 방법. 주로 컴퓨터가 어떤 일을 수행하기 위한 단계적 방법 예) 1 ~ 100까지의 합 1. 1 + 2 + 3 + ... + 100 = 5050 2. {(1+100) + (2 + 99) + ... + (50 + 51)} * 50 = 5050 2. 알고리즘 표현법 1. 슈도코드 2. 순서도 1. 슈도코드 일반적인 언어로 코드를 흉내내어 알고리즘을 써놓은 코드 특정 언어로 프로그램을 작성하기 전에 알고리즘을 대략적으로 모델링하는데에 쓰인다. 2. 순서도 프로그램이나 작업의 진행흐름을 순서에 따라 여러가지 기호나 문자로 나타낸 도표. 흐름도라고도 하며..