분류 전체보기
13913_숨바꼭질
https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 숨바꼭질의 연장선 문제이다. bfs를 통해서 카운트를 통해 몇초가 걸리는지 걸리는건 해볼 수 있다. 이때 0~100000까지의 배열을 만들어두고 해당하는 초를 새기면서 카운팅을 한다. 그렇다면 이 배열을 기록해나갈때 어느 점에서 나왔는지도 기록을 하면 쉽게 역추적을 할 수 있다. 이배열의 이름을 cnt라고 해보자 예를 들어 5 17인경우 5 10 9 18 17 5..
9252_LCS2
https://www.acmicpc.net/problem/9252 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이전에 LCS문제를 풀어봤다면 비슷하게 풀 수 있다. 해당 예제를 dp에 넣을때 위처럼 쌓여지게 된다. 첫째줄부터 살펴보면 C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 순서대로 비교하면서 배열을 찾는 것이다. 두번재줄은 A,C를 가지고 A, AC , ACA, ACAY, ACAYK, ACAYKP 랑 비교하면서 길이를 찾는..
파이참에서 GPU사용!
인공지능을 공부할때는 보통 코랩을 통해서 GPU를 사용한다! 하지만 집의 컴퓨터에 GPU가 장착되어 있다면 이를 활용해서 코드를 돌려볼 수도있다. 파이참에서 GPU를 사용하는 방법에 대해 다뤄보겠다 우선 아나콘다를 설치해야 한다. https://www.anaconda.com/products/distribution Anaconda | Anaconda Distribution Anaconda's open-source Distribution is the easiest way to perform Python/R data science and machine learning on a single machine. www.anaconda.com 그리고 파이썬과 파이참은 설치되어 있다고 가정해보겠다. 아나콘다는 가장 최신..
14003_ 가장 긴 증가하는 수열
https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 이전에 dp를 이용해서 for문을 두번 돌리는 방식으로 가장 긴 증가하는 수열을 구했었다. 하지만 위 문제는 같은 시간복잡도를 가지고는 풀 수 없다. 시간복잡도를 줄이기 위해서 기록을 위한 dp를 두개를 사용할 것이다. 하나는 해당 숫자가 가진 가장 긴증가하는 부분 수열의 길이를 저장할 것이고 하나는 수열을 증가시킬지 이전 수열과 비교할지를 판독하는데 사용할 임시 배..
14002_가장 긴 증가하는 수열
https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 다시 돌아온 dp파트이다. 이전에 가장 긴 증가하는 부분수열의 개수만 구하는 코드를 짠 적이 있는데 이번에는 그 수열자체를 구하는 코드이다. 하지만 첫번째 줄부터 기록해나가면서 작성하는 방법인데는 변함이 없다 1 2 1 3 2 5 라고 생각해보자. 그리고 dp를 [ [1] [2] [1] [3] [2] [5] ] 이렇..
12582_1로 만들기 2
https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 이전에 풀어보았었던 내용이지만 값이 엄청 커졌다. dp를 활용해서 푸니까 잘 풀렸다. 1부터 시작해서 *2, *4, +1 을 해서 저장된 값보다 길이가 적으면 그 값들을 리스트형태로 전달하게 해주었다. n = int(input()) dp = [ [] for i in range(n+1) ] dp[1].append(1) for i in range(1,n+1): LEN = len(dp[i]) if i*3