전체보기 (462) 썸네일형 리스트형 [462] 이분 매칭 알고리즘(파이썬 코드) 위와 같은 이분 그래프가 있을 때 이분 매칭을 구해봅시다. 1. 종만북 참고 소스코드종만북 코드는 C언어이므로 파이썬 코드로 옮기면 다음과 같습니다.n, m = 5, 5adj = [ [1, 1, 1, 1, 1], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 0], [1, 0, 0, 0, 1], ]a_match, b_match = [-1, -1, -1, -1, -1], [-1, -1, -1, -1, -1]def dfs(a): if visited[a]: return False visited[a] = True for b in range(m): if adj[a][b]: if b_match[b].. [461] 여러 수열에서 수 하나씩 골라 최소 범위 만들기 1. 문제수열이 여러 개(N개) 있을 때, 각 수열에서 수를 하나씩만 고릅니다.그렇게 고른 수 중 최대값과 최소값의 차이가 가장 작게 골라봅시다.예를 들어, {49, 97, 1, 64, 25}, {93, 33, 54, 78, 12}, {71, 6, 80, 20, 44}가 있을 때, 각 수열에서 수 하나씩 고릅니다.이 때 만약 첫 번째 수열에서 49, 두 번째 수열에서 54, 세 번째 수열에서 44를 고른다면, 이 중 최대값인 54와 최소값인 44의 차이는 10입니다.이렇게 선택한 수 중 최대값과 최소값의 차이가 가장 작게 고르는 방법을 알아봅시다.2. 해결 방법가. Brute-force모든 경우의 수를 일일이 살펴보고, 정답을 찾는 방법입니다.구현하기 가장 쉽지만, 비효율적입니다.시간복잡도를 계산해보면 .. [460] 특정 간격 이하로 선택하여 합이 최소인 부분 수열 구하기 1. 문제임의의 자연수로 이루어진 수열(nums)이 있을 때, 특정 간격(k) 이상으로 떨어지지 않도록 연속되게 수들을 선택하여 그 합이 최소가 되게 하는 부분 수열(result)을 구해보자.2. 준비물임의의 수열(array) : nums넘으면 안 되는 간격(int) : k = 2index를 관리할 deque : dq조건을 만족하는 최소값을 관리할 dp테이블 : dp부분 수열을 구할 배열(array) : sub3. 해결 방법가. 아이디어i번째 수까지의 최적해를 dp[i]라고 했을 때, dp[i]는 dp[i-k-1] ~ dp[i-1] 중 최소값에 i번째 수를 더한 값입니다.식으로 쓰면 아래와 같습니다.dp[i]=minj=i−k−1i−1dp[j] 그리고 위 .. [459] 백준 11062번 카드 게임 - 게임 이론 1. 문제https://www.acmicpc.net/problem/110622. 문제 이해카드 n장이 일렬로 주어집니다.카드 양쪽 끝 두 장 중에 한 장을 골라 가져옵니다.점수는 카드에 적혀있는 숫자를 계속해서 누적합니다.번갈아가며 카드가 모두 없어질 때까지 반복합니다.최종적으로 점수가 더 높은 사람이 승리합니다.3. 해결 방법가. DP 가능성 확인브루트포스로 해결할 경우 시간 복잡도가 O(2N) 으로 N의 최대값이 1000이기 때문에 불가능합니다.그리디로 해결 가능하다면 O(N) 만에 해결 가능합니다. 하지만 위의 예시처럼 매 순간 최선의 선택을 할 경우, 큰 수를 가진 카드가 언제 나올지 모르기 때문에 그리디로 해결할 수 없습니다.이 문제를 DP로 풀 수 있는지 확인하기 위해 Ov.. [458] 시간복잡도와 1초에 해결 가능한 입력의 크기 1. PS에서 1초 동안 가능한 연산 횟수프로그래밍 대회나 알고리즘 문제 풀이에서 시간 제한 1초는 약 1억 번 정도의 연산 수행 제한을 의미합니다.여기서 말하는 연산은 사칙 연산, 비교 연산, 대입 연산 등으로 이루어진 O(1) 시간에 수행되는 연산을 의미합니다.이 수치는 실제 CPU가 수행하는 연산 시간이 아니라, 온라인 저지 시스템에서 시간 초과(TLE)를 피하기 위한 기준선입니다.2. 시간 복잡도에 따른 해결 가능한 입력의 크기1초에 1억 번의 연산이 가능하다고 했을 때, 시간 복잡도에 따른 1초에 해결 가능한 입력의 크기는 다음과 같이 주먹구구식으로 계산할 수 있습니다.입력 N의 크기시간 복잡도최악의 경우 연산 횟수N≤11O(N!)11!=39,916,800\(N .. [457] 백준 2225번 합분해 - 최단경로 경우의 수와 중복 조합 1. 문제https://www.acmicpc.net/problem/22252. 문제 이해0부터 N까지의 정수 중에 아무 수나 K개(중복 가능)를 더해서 그 합이 N이 되는 경우의 수를 구하는 문제입니다.예를 들어 N이 5이고 K가 3이면,위 그림과 같이 21가지입니다.3. 해결 방법가. 동적 프로그래밍숫자가 K개가 될 때까지 하나씩 추가해가며 합이 N보다 작거나 같은 경우의 수를 관리해봅시다.먼저, 숫자를 1개만 사용하면 경우의 수는 각각 고른 숫자만큼 합이 되므로 경우는 모두 각각 1가지 입니다.다음으로 숫자를 2개 사용하는 경우에는 이전에 숫자 1개를 사용하여 만든 값을 활용하여 빠르게 계산할 수 있습니다.(DP)이렇게 표를 채워가면 3중 for문으로 채워지게 됩니다.(행, 열, 이전 행)그러나 굳이.. [456] 색종이 3등분 접는 법 - 두 일차함수의 교점 1. 색종이 3등분 접는 법2. 왜 그럴까?색종이의 한 변의 길이를 1이라고 가정합니다.비스듬하게 접은 선을 함수의 그래프로 표현하면,y=−x+1, y=2x, y=12x 으로 나타낼 수 있습니다.이 함수의 그래프와 교점을 살펴보면 (13,23) 와 (23,13) 입니다. 따라서 이 교점을 기준으로 접으면 3등분을 할 수 있습니다. [455] [수업 자료] 에라토스테네스의 체 에라토스테네스의 체 – 소수를 찾는 똑똑한 방법!1. 수업 개요주제에라토스테네스의 체 & 함수교과 연계수학: 소수의 개념, 체를 이용한 소수 탐색정보: 함수 개념, Python 프로그래밍수업 목표수학: 소수가 무엇인지 이해하고, 에라토스테네스의 체를 활용해 1부터 100까지의 소수를 찾아볼 수 있다.정보: 에라토스테네스의 체 알고리즘을 함수로 정의하고, Python 코드로 구현할 수 있다.2. 수업 흐름도입 - 소수의 개념 이해하기간단한 퀴즈로 '소수'의 개념을 학습하고, 소수와 합성수의 차이를 비교함.전개1 - 체를 활용한 소수 찾기 활동활동지를 활용해 직접 에라토스테네스의 체 활동 수행2의 배수 지우기 → 3의 배수 지우기 → … 반복남은 수들이 소수라는 것을 체험적으로 이해전개2 - 알고리즘으로 일.. 이전 1 2 3 4 ··· 58 다음 목록 더보기
