본문 바로가기

Tech67

나의 방학 2024. 3. 2.
가장 가까운 두 점 def closest_pair(points): def sq_dist(p1, p2): return (p1[0] - p2[0])**2 + (p1[1] - p2[1])**2 def closest_band(mid_band, d): min_d = d mid_band.sort(key=lambda x: x[1]) # y좌표정렬 for i in range(len(mid_band)): for j in range(i+1, len(mid_band)): if (mid_band[j][1] - mid_band[i][1])**2 < min_d: dist = sq_dist(mid_band[i], mid_band[j]) if dist < min_d: min_d = dist else: break return min_d def close.. 2024. 3. 2.
가장 긴 바이토닉 부분 수열 이번에는 글을 쓰면서 풀어 보자 . 이 문제는 최장 증가 수열 문제를 응용한 문제다. 그런데 최장 증가 수열 문제의 내 코드를 보아도 이해가 바로 안 가서 다시 공부했다. 먼저 LIS라고도 하는 최장 증가 수열 A에 대해 A[i]가 i번째 원소라고 하면 dp는 다음과 같이 정의할 수 있다. dp[i] = i번째 원소를 포함하는 가장 긴 증가하는 수열 증가하는 수열이 i번째 수를 포함하려면 포함시키려는 기존 수열의 마지막 원소가 i번째 수보다 작아야 한다. 만약, i번째 수를 포함시킬 수 있다면( 기존 수열의 마지막 원소가 i번째 수보다 작다면) 기존 수열의 길이에 + 1을 하면 된다. 그러니까 dp[i]를 정할 때, for i in range(n): for j in range(i): if a[i] > a.. 2024. 3. 2.
젯슨 나노 USB SSD 부팅 2024. 2. 29.
네 개의 다른 우분투 서버 카다스, 라즈베리파이4 젯슨 나노, amdPC 카다스는 정말 빠릿해요. 2024. 2. 28.
1932번 정수 삼각형 n = int(input()) delta = [list(map(int, input().split())) for _ in range(n)] dp = [[0]*x for x in range(1,n+1)] print(n) print(delta) print(dp) if n == 1: print(delta[0][0]) else: dp[0][0] = delta[0][0] for i in range(n): for j in range(i+1): print(i,j,len(dp[i-1])) if 0==j: dp[i][j] = dp[i-1][j] + delta[i][j] elif len(dp[i-1])==j: dp[i][j] = dp[i-1][j-1] + delta[i][j] else: dp[i][j] = max(dp[i-.. 2024. 2. 28.
1463번 1로 만들기 def counter(n): dp = [0] * (n + 1) for i in range(2, n + 1): dp[i] = dp[i - 1] + 1 if i % 2 == 0: dp[i] = min(dp[i], dp[i // 2] + 1) # 3으로 나누어 떨어지는 경우 if i % 3 == 0: dp[i] = min(dp[i], dp[i // 3] + 1) return dp[n] n = int(input()) print(counter(n)) 숫자 i를 1로 만들 수 있는 최소 계산 횟수를 dp[i] 라고 정의하면, 기본적으로 +1연산에 의해 1개씩 증가하고, 2로 나누어떨어지는 i의 경우 2분의 1 위치의 dp에 1을 더한 방법과 이전 수에 1을 더한 방법 중 최소 횟수를 저장한다. 3로 나누어떨어지는 .. 2024. 2. 28.
Raspberry Pi 5 8G 2024. 2. 27.
25494번 단순한 문제 (Small) 어이없게 푼 문제. 나는 이렇게 짰다. from itertools import product for _ in range(int(input())): a,b,c=map(int,input().split()) prod=list(product(range(1,a+1),range(1,b+1),range(1,c+1))) count = 0 for p in prod: if p[0]%p[1]==p[1]%p[2]==p[2]%p[0]: count += 1 print(count) 세 리스트를 조합해서 새로운 리스트를 만들고 나머지연산을 비교하는 거다. 말 그대로 시뮬레이션인데..... 시간초과가 떴다. 뭔가 이상해서 (x%y) = (y%z) = (z%x) 조건에 부합하는 조합을 출력해 보았다. 1 60 60 60 (1, 1, 1.. 2024. 2. 27.
Embedding a Python Playground 파이썬 3 플레이그라운드를 웹에 임베딩하고 싶어서 서비스를 찾아 보았다. datacamp라는 깃헙 소스가 있었는데. 티스토리에서 한 번 글을 수정할 때 마다 스크립트가 망가져서 불편했다. 그런데 아래 서비스를 찾았다. 그런데 임베딩을 하려면 유료인것 같은데 라고 적혀 있다. 해 보니까 과금 없이 공유 임베딩 가능하다. https://trinket.io/library/trinkets/create?lang=python3 Trinket Need to create an account? Sign Up trinket.io 일단 회원 가입 후 화면 우상단에서 내 아이디를 클릭하면 나오는 메뉴 중 새로 만들기 선택. 파이썬 3 선택하면 코드 편집창이 나온다. 코드 편집창에서 코드를 입력하고 쉐어 임베드를 선택하면 된다.. 2024. 2. 26.
# 20920번 영단어 암기는 괴로워 # 20920번 영단어 암기는 괴로워 영단어 암기는 괴로워 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 (추가 시간 없음) 1024 MB 14507 6620 5255 45.644% 문제 만들고자 하는 단어장의 단어 순서는 다음과 같은 우선순위를 차례로 적용하여 만들어진다. 자주 나오는 단어일수록 앞에 배치한다. 해당 단어의 길이가 길수록 앞에 배치한다. 알파벳 사전 순으로 앞에 있는 단어일수록 앞에 배치한다 +길이가 M이상인 단어들만 외운다고 한다. 입력 첫째 줄에는 영어 지문에 나오는 단어의 개수 N과 외울 단어의 길이 기준이 되는 M이 공백으로 구분되어 주어진다. $(1≤N≤100000, 1≤M≤10)$ 둘째 줄부터 N+1번째 줄까지 외울 단어를 입력받는다. 이때의 입력은 알파벳 소.. 2024. 2. 26.
1904번 01타일 동적 프로그래밍이 어려워서 한 문제씩 차근차근히 공부해 보기로 했다. 1. 문제의 이해 00이 쓰여진 타일과 1이 쓰여진 타일로 크기 N을 몇 가지 만들 수 있나? 라는 문제다. 문제를 단순화하면, 00은 길이2, 1은 길이1로 생각한다. 그러면 2와 1을 써서 만들 수 있는 합이 N나오는 순열 개수 구하기다. 길이가 1일 때 만들 수 있는 순열은 [1] 한 가지. 길이가 2일 때 만들 수 있는 순열은 [2]와 [1,1] 두 가지다. 2. dp의 정의 타일을 길이만큼 채워 나갈 때 공간이 점점 줄어들고, 그 과정에서 과거에 채워 본 공간이 계속 등장한다. 다시말해 과거의 연산을 이용해서 가짓수를 구할 수 있다. 길이 1과 2를 계산한 후 길이 3의 공간을 채운다고 했을 때, 길이 1짜리 타일을 붙이고 나.. 2024. 2. 25.

티스토리툴바