1. 문제 자연수로 이루어진 어떤 수열이 주어질때, 이 수열의 모든 부분수열의 합을 생각해보자 이때 불가능한 합의 최솟값을 구해본다면? 예를 들어 s = [5,1,2]이면, 1,2,3,5,6,7,8은 만들 수 있는데 4를 만들 수가 없다 2. 알고리즘 2-1) 수열을 오름차순으로 정렬한다 2-2) sum = 0로 초기화한다 2-3) 수열을 하나씩 순회해서 그것을 x라고 하자. sum+1을 만들 수 있는지 확인해본다. 2-4) sum+1 >= x이면 sum+1까지 만들 수 있다. 그러면, sum + x를 sum으로 갱신한다. 2-5) sum+1 이것만 보면 아무리 생각해도 와닿지는 않는다 어떻게 보면 경이롭기까지하다. 진짜 이게 가능한건가? 여러가지 풀이를 보면서 이해해보도록 노력하자 3. 예시..
1. 문제 11000번: 강의실 배정 (acmicpc.net) 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si = 현재 종료시간"이면 하나의 회의실에서 가능하다는 알고리즘으로 해결했다 근데 이 문제는 모든 수업을 가능하게 하는 최소의 회의실 수를 구해야한다 어떻게 하냐면 시작시간이 빠른 순서대로 오름차순 정렬한다 먼저 가..
1. 최단경로 간선의 가중치가 있는 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소인 경로 최단경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 다양한 종류가 있지만 상황에 맞는 효율적인 알고리즘이 이미 정립되어 있다 예를 들어 "한 지점에서 다른 특정 지점까지의 최단 경로를 구해야하는 경우", "모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야하는 경우" 최단 경로 문제는 보통 그래프를 이용하여 표현하는데 각 지점은 그래프에서 "노드"로 표현되고, 지점간 연결된 도로는 그래프에서 "간선"으로 표현된다. 2. 다익스트라 최단경로 알고리즘 그래프에서 여러 개의 노드가 있을 때 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 시작 정점에서..
1. 문제 유형 1-1) 예시 윤대리는 소프트웨어 개발팀들의 회의실 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다. 회의는 시작 시간과 종료 시간이 있고 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다. 가능한 많은 회의가 열리기 위해 회의실은 어떻게 배정해야할까? 1-2) 정형화 시작시간과 종료시간 $(s_{i}, f_{i})$가 있는 n개의 활동들의 집합 $A = \left\{ A_{1}, A_{2},... , A_{n} \right\}$이고 i는 1이상 n이하이다. 여기서 서로 겹치지 않는 최대 개수의 활동들의 집합 S를 구하는 문제 2. 문제 해법 모든 경우의 수를 조사할 수도 있지만 탐욕 알고리즘이 가능한 대표적인 문제..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12941 코딩테스트 연습 - 최솟값 만들기 길이가 같은 배열 A, B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A, B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱 programmers.co.kr 길이가 같은 배열 A,B 두개가 있습니다. 각 배열은 자연수로 이루어져 있습니다. 배열 A,B에서 각각 한 개의 숫자를 뽑아 두 수를 곱합니다. 이러한 과정을 배열의 길이만큼 반복하며, 두 수를 곱한 값을 누적하여 더합니다. 이 때 최종적으로 누적된 값이 최소가 되도록 만드는 것이 목표입니다. 단 각 배열에서 k번째 숫자를 뽑았다..
1. 문제 https://programmers.co.kr/learn/courses/30/lessons/12982 코딩테스트 연습 - 예산 S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 programmers.co.kr S사에서는 각 부서에 필요한 물품을 지원해 주기 위해 부서별로 물품을 구매하는데 필요한 금액을 조사했습니다. 그러나, 전체 예산이 정해져 있기 때문에 모든 부서의 물품을 구매해 줄 수는 없습니다. 그래서 최대한 많은 부서의 물품을 구매해 줄 수 있도록 하려고 합니다 물품을 구매해 줄 때는 각 부서가 신청한 금액만큼을 모두 지원해 줘야 합니다. 예를 들어 ..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
