i != 1, V = {v1, v2, v3, v4}, A는 v1을 포함하지않는 V의 부분집합, {v2, v3, v4} = 111 1. vi 가 A에 포함되는가? A & (1 011 v2가 A에 포함되는가? v2 -> i = 2 1

2주차 스터디 계획 https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 주에 공부할 내용은 백트래킹과 그래프입니다! 1. 백트래킹 1) 학습 목표 1. 백트래킹 개념을 학습하고 최적화 문제와 결정 문제에 적용할 수 있음을 이해한다. 2. 백트래킹으로 상태 공간 트리를 탐색하는 방법에 대해 이해한다. 3. 모든 부분 집합과 모든 순열을 백트래킹으로 생성할 수 있다. 2) 학습 구성 (5강 + 2문제) 1강 : 백트래킹 개념 2강 : 부분 집합 3강 : 순열 ..

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. 분할 -> 정복 -> 통합 분할(divide) 문제를 여러개의 작은 부분 문제로 분할 정복(conquer) 부분 문제를 각각 해결 통합(combine) 필요 시 부분문제 해답을 모음 2. 거듭 제곱 문제 1. O(n) def iterative_power(c, n): result = 1 for _ in range(n): result *= c return result 2. 분할정복 O(logn) C^n n 짝수 -> C^(n/2) * C(n/2) n 홀수 -> C^((n-1)/2) * C^((n-1)/2) * C def recursive_power(c, n): if n == 1: return c if n % 2 == 0: y = recursive_power(c, n/2) return y*y else: ..

1. 탐욕(그리디) 알고리즘 최적화 문제를 해결하는 알고리즘 최적해를 구하는 근시안적인 방법 최적화 문제는 최적값(최대값 또는 최소값 등)을 구하는 문제 여러 경우 중 하나 선택 -> 선택시 마다 최적을 선택 -> 최종 해답 도달 대부분의 그리디 알고리즘은 단순하며, 제한적인 문제들에 적용 각 선택은 지역적으로 최적 지역적 최적해를 수집하여 최종 해답을 만들었다고해서 그것도 최적이라는 보장은 없다. 2. 수행 과정 해 선택 현재 상태에서 최적이라고 여겨지는 해답을 해집합에 추가 하나의 해 선택이 이루어지면 새로운 부분 문제 발생 실행 가능성 검사 실시 새로운 부분 해 집합의 실행가능 여부 확인 문제의 제약 조건 위반을 검사 해 검사 새로운 부분 해 집합이 문제의 해가 되는지 확인 전체 문제의 해가 완성되..

https://www.acmicpc.net/problem/1969 1969번: DNA 문제 DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클 www.acmicpc.net 1. 문제

1. 조합적 문제 완전 검색은 특정 조건을 만족하는 경우나 요소를 찾는 검색 알고리즘이다. 이것은 순열(Permutation), 조합(Combination), 부분집합(Subset)과 같은 조합적 문제(Combinatorial Problems)들과 관련이 많다. 다음 이동비용이 가중치와 숙박비로 주어진 그래프에서 출발 도시에서 도착 도시까지 다른 도시들을 한번씩만 방문하여 도착하는 최소비용 경로는 무엇일까? 완전검색으로는 어떻게 풀고 완전 검색보다 더 좋은 알고리즘은 무엇일까? 2. 순열 서로 다른 n개중 r개를 택하는 순열 nPr = n * (n - 1) * (n - 2) * ... * (n - r + 1) nPn = n! 예시) 1, 2, 3, 4 순열 생성 첫번째로 1을 선택하면 나머지 2, 3, ..

1. baby-gin 게임 0~9사이에서 6장을 뽑고 3장의 카드가 연속숫자일 경우 Run, 3장이 동일한 숫자일 경우 Trplete이라 한다. 만약 6장이 run과 triplete으로만 구성될 수 있으면 baby-gin이라 한다. 예시) 667767 -> 666, 777 baby-gin 054060 -> 000. 456 baby-gin 101134 -> baby-gin X 6자리 숫자를 입력받아 baby-gin 여부를 판단하는 알고리즘은? 가장 쉬운 방법은 완전검색이다. 2. 완전 검색(Brute-force) 문제의 해를 위해 모든 경우의 수를 나열하는 기법 문제를 해결하기 위한 가장 쉬운 접근법 상대적으로 빠른 시간에 문제 해결 알고리즘을 설계할 수 있다. 대부분의 문제에 적용가능 문제의 자료의 수가..

1주차 스터디 계획 https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPDYSqAAbw5UW6 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 이번 주에 공부할 내용은 완전검색, 그리디, 분할정복 입니다! 1. 완전검색 1) 학습 목표 1. 완전 검색의 개념을 이해하고 완전 검색을 통한 문제 해결 방법에 대해 학습한다. 2. 조합적 문제와 완전 검색의 연관성을 이해한다. 3. 순열, 조합, 부분집합을 생성하는 방법에 대해 이해한다. 동영상 강의 2개와 완전 검색 2문제로 이루어져 있습니다. 2. 그리디 1. 탐욕 알고리즘 기법의 개..

https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 길이가 L인 테이프를 가지고, 물이 새는 곳을 막아야한다. 물을 막을 때는 좌우 0.5만큼을 더 붙여줘야한다. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다. 2. 접근 물이 새는 연속된 위치의 길이가 테이프-1 (-1은 좌우 0.5를 의미) 보다 짧을 경우, 테이프를 한번에 붙인다. 물이 새는 연속된 위치의 길이가 테이프 -1 보다 길..