Dogfootruler Kim

문제 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..

문제 www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 풀이 및 소스코드 입력 받은 박스 크기들을 순서대로 비교해나가서 dp에 저장해주면 된다. 인덱스 i에 대해 보고 있다면, 0부터 i-1번째 까지 박스 크기와 dp값들을 비교한다. box[i]보다 크기가 작고 dp 값이 최대라면 dp[i] 에 +1 해서 더해준다. 작은 박스가 없다면 1을 대입해주면 된다. import sys input = sys.stdin.readline n = int(input()) box = l..

문제 www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때 www.acmicpc.net 풀이 및 소스코드 gword 라는 그룹단어의 알파벳이 들어가는 리스트를 하나 만들어주었다. 이전에 나왔던 알파벳들을 기억해두려고 만들었다. 먼저, for 문으로 입력받은 단어의 맨 처음 알파벳부터 보면서 gword 에 담겨있는지 본다. 없으면 추가하고 카운트를 +1 해준다. 카운트는 전에 나왔던 알파벳이 연속된건지, 아니면 떨어져있던건지 보기위함이다 ! 만약, 담겨있다면 먼..