Dogfootruler Kim

문제 programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr 풀이 및 소스코드 def solution(progresses, speeds): answer = [] while progresses: cnt = 0 for i in range(len(progresses)): progresses[i] += speeds[i] if progresses[0] >= 100: while progresses: if progresses[0] >=..

문제 www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 및 소스코드 jainn.tistory.com/90 최장 증가 부분 수열(LIS) 알고리즘 LIS(Longest increasing Subsequence)란, 가장 긴 증가하는 부분 수열이다. 예를 들어, [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 된다. 증가하는 부분 수열 중 가장 긴 것이기 때.. jainn.tistory.com 이걸 보..

문제 www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 및 소스코드 난 당연히 맨 앞에 오는 숫자부터 고려를 해주면서 규칙을 찾아보았다. 앞에서부터 하니 규칙은 보이나 규칙을 dp로 정의하기가 어려웠다. 자릿수가 주어졌을 때 맨 뒤에 오는 숫자에 대해 표를 만들어 구해보면 규칙을 쉽게 알 수 있었다. 위와 같이 num[i] += num[i-1] 이라는 규칙이 보인다. 따라서 끝까지 적용해주면 된다. n = int(inp..

LIS(Longest increasing Subsequence)란, 가장 긴 증가하는 부분 수열이다. 예를 들어, [6, 2, 5, 1, 7, 4, 8, 3] 이라는 배열이 있을 경우, LIS는 [2, 5, 7, 8]이 된다. 증가하는 부분 수열 중 가장 긴 것이기 때문. LIS를 풀기 위한 가장 일반적인 방법은 DP를 이용하는 것이다. dp = [1]*n for i in range(n): for j in range(i): #첫번째 요소부터 i번째까지 위와 비교 if arr[i] > arr[j]: #뒤에 있는 요소(arr[i])가 크면 dp[i] = max(dp[i], dp[k]+1) 위 알고리즘의 시간복잡도는 O(n^2)을 갖게 됩니다. 시간복잡도를 개선하기 위해서는 이분탐색을 활용합니다. 주어진 배열..

문제 programmers.co.kr/learn/courses/30/lessons/42583?language=python3 코딩테스트 연습 - 다리를 지나는 트럭 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이 programmers.co.kr 풀이 및 소스코드 처음에는 cross 덱에 time 덱까지 넣어서 cross.append([truck_weights[0], 0]) 이렇게 해주려고 했으나, 시간 1초 더하는 부분에서 TypeError: unsupported operand type(s) for +: 'int' and 'list' 이런 오류가 떠서 2차원이 아닌..

문제 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 유니온 파인드 문제이다. 유니온 파인드에 대해 이해가 가지 않는다면 , jainn.tistory.com/87 유니온 파인드(UNION-FIND) 파이썬 구현 유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다. 합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 ..

유니온 파인드(Union-Find)는 트리형태를 갖는 자료구조이다. 합집합 찾기 및 상호 배타적 집합(Disjoint-set)이라고도 한다. 이름 그대로 상호 배타적인 부분 집합들로 나누어진 원소들을 저장하고 조작하는데 사용된다. 유니온 파인드(Union-Find)의 기능에 대해서 설명해보겠다. 1) Union : 두 집합을 하나의 집합으로 합치는 연산 2) Find : 어떤 원소 x가 주어졌을 때 이 원소가 속한 집합을 반환 위와 같이 두 가지 연산을 해주는 자료구조라고 할 수 있다. 정의를 알았다면 구현을 해보자 ! 구현 1. 초기화 parent 배열을 만들어준다. 파이썬 parent[a] = b #배열은 a 원소의 부모는 b이다. 라는 뜻으로 해석하면 된다. #초기화 시작 parent[i] = i ..

문제 www.acmicpc.net/problem/17144 문제가 요즘 날씨와 아쥬 어울린다 ,, 미세먼지 싫어 ,,,,, ㅠ 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 풀이 및 소스코드 확산이 동시에 진행된다는 점을 고려해야한다. 주석과 함께 코드를 보면 이해하기 쉬울거다 ! import sys from copy import deepcopy input = sys.stdin.readline def airclear(x, y, diff): #공기청정기 작동 for i in range(4): while Tru..