1. 문제1 2529번: 부등호 (acmicpc.net) 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시 www.acmicpc.net k개의 부등호가 주어질때, 0~9까지에서 k+1개의 수를 1번씩만 선택해 주어진 부등호 순서를 모두 만족시킬때 이들을 하나로 합친 수의 최댓값과 최솟값을 구하는 문제 2. 풀이 10개중에 k+1개를 선택하는 순열을 검사해서 부등호를 모두 만족시키는지 검사해보고 조건을 만족시키면 최댓값과 최솟값을 갱신한다 어차피 각 수는 1개씩만 사용가능하니까 숫자를 문자열로 다뤄도 될 것이다 숫자문자열끼리 비교하면 맨 앞자리부터 크면..
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. 문제 유형 1-1) 예시 윤대리는 소프트웨어 개발팀들의 회의실 사용 신청을 처리하는 업무를 한다. 이번 주 금요일에 사용 가능한 회의실은 하나만 존재하고 다수의 회의가 신청된 상태이다. 회의는 시작 시간과 종료 시간이 있고 회의 시간이 겹치는 회의들은 동시에 열릴 수 없다. 가능한 많은 회의가 열리기 위해 회의실은 어떻게 배정해야할까? 1-2) 정형화 시작시간과 종료시간 $(s_{i}, f_{i})$가 있는 n개의 활동들의 집합 $A = \left\{ A_{1}, A_{2},... , A_{n} \right\}$이고 i는 1이상 n이하이다. 여기서 서로 겹치지 않는 최대 개수의 활동들의 집합 S를 구하는 문제 2. 문제 해법 모든 경우의 수를 조사할 수도 있지만 탐욕 알고리즘이 가능한 대표적인 문제..
1. 문제 N개의 block이 일렬로 있고 0부터 N-1까지 숫자가 붙어있다. 사이가 안좋은 개구리가 하나의 block위에 함께 있는데 이들이 서로 최대한 멀리 떨어지려고 한다. 만약 J와 K, J= s_h: s_h = h first += 1 else: break 현재 s-1에 첫번째 개구리가 시작할건데 blocks의 s부터 오른쪽으로 순회를 해서 h라고 두는거임 만약 h가 시작높이 s_h보다 크거나 같으면 점프할 수 있고 현재 개구리 높이 s_h를 h로 두고 first에 1을 더해서 개구리 위치를 갱신한다 근데 점프를 못하는 순간 더 이상 오른쪽으로는 못간다는 소리이므로 반복문을 탈출 s_h = blocks[s] #second frog for ind,h in enumerate(blocks[s::-1])..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
