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 보다 길..

https://www.acmicpc.net/problem/1049 1049번: 기타줄 첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 1. 문제 N개의 줄을 교체하려고 한다. 6줄 패키지를 사거나 1개 또는 그 이상의 줄을 낱개로 살 수 있다. 이때 M개의 브랜드에 따른 패키지가격과 낱개 가격이 주어질 때 기타줄을 교체하는데 최소금액을 구하라. 2. 접근 1. M개의 브랜드를 모두 포함하여 최소 패키지 금액과 최소 낱개 금액을 구한다. 2. 패키지와 낱..

https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 길이는 B의 길이보다 작거나 같다. 이제 A의 길이가 B의 길이와 같아질 때 까지 다음과 같은 연산을 할 수 있다. A의 앞에 아무 알파벳이나 추가한다. A의 뒤에 아무 알파벳이나 추가한다. 이때, A와 B의 길이가 같으 www.acmicpc.net 1. 문제 문자열 A, B가 주어진다. A는 B보다 같거나 짧다. 1. A의 앞에 아무 알파벳을 추가한다. 2. A의 뒤에 아무 알파벳을 ..