Tech83 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. 음? 2024. 2. 24. 카데인 알고리즘(Kadane's Algorithm) 가장 큰 부분순열의 합을 구하는 문제는 "최대 부분 배열 합(Maximum Subarray Sum)" 문제로 알려진 유명한 문제다. 해결법으로 가장 유명한 알고리즘은 카데인 알고리즘(Kadane's Algorithm)이다. 카데인 알고리즘은 동적 프로그래밍을 활용하여, 배열을 한 번만 순회하면서 최대 부분 배열의 합을 효율적으로 찾는다. 이 알고리즘은 시간 복잡도 (O(n))을 가지며, 여기서 (n)은 배열의 크기다. 카데인 알고리즘의 기본 아이디어는 각 단계에서 현재까지의 최대 부분 배열 합을 계속 업데이트하는 것이다. 이때 두 가지 선택을 고려한다: 현재 원소를 포함하는 새로운 부분 배열을 시작하는 것이 더 나은지, 아니면 현재 원소를 이전 부분 배열에 추가하는 것이 더 나은지. 아래는 카데인 알고리.. 2024. 2. 24. RGB거리 import sys raw = sys.stdin.readlines() n = int(raw[0]) c = [[int(x) for x in line.split()] for line in raw[1:]] dp = [[0,0,0] for _ in range(n)] dp[0] = c[0] for i in range(1, n): dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + c[i][0] dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + c[i][1] dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + c[i][2] print(min(dp[n-1])) 이 코드는 집을 칠하는 데 필요한 최소 비용을 계산하는 동적 계획법(Dynamic Progr.. 2024. 2. 22. # 9251번 LCS def lcs(A, B): lenA, lenB = len(A), len(B) DP = [[0] * (lenB+1) for _ in range(lenA+1)] for i in range(1, lenA+1): for j in range(1, lenB+1): if A[i-1] == B[j-1]: DP[i][j] = DP[i-1][j-1] + 1 else: DP[i][j] = max(DP[i-1][j], DP[i][j-1]) return DP[lenA][lenB] def main(): A = input() B = input() print(lcs(A, B)) if __name__ == "__main__": main() lcs(A, B) 함수는 두 문자열 A와 B를 입력으로 받습니다. 변수 lenA와 lenB는 각.. 2024. 2. 19. # 12865 평범한 배낭(Python 파이썬) N, K = map(int, input().split()) # 물품의 수 N, 최대 무게 K 입력 받기 items = [(0, 0)] # 물건의 무게와 가치를 저장할 리스트, 0번 인덱스는 사용하지 않기 위해 초기값 설정 for _ in range(N): W, V = map(int, input().split()) # 각 물건의 무게 W와 가치 V 입력 받기 items.append((W, V)) # dp[i][w]: 처음 i개의 물건을 고려했을 때, 무게 w까지의 배낭에 담을 수 있는 최대 가치 dp = [[0 for _ in range(K+1)] for _ in range(N+1)] for i in range(1, N+1): for w in range(1, K+1): if items[i][0] 13 무게.. 2024. 2. 17. 백트래킹(Backtracking, 퇴각검색) # 14889번 스타트와 링크, # 9663번 N-Queen [파이썬] 목차 그래프와 트리 탐색 알고리즘 백트래킹의 소개 개념 방법 성능개선 개발 활용 사례(예산 활용법 찾기) 알고리즘 설명 코드보기 백준 문제 #14889 스타트와 링크 # 9663번 N-Queen α–β A* B* 퇴각검색 빔 벨먼-포드 최상 우선 양방향 Borůvka 분기 한정법 BFS 영국박물관 D* DFS 데이크스트라 에드먼즈 플로이드-워셜 Fringe search 언덕등반기법 IDA* 반복적 깊이심화 존슨 Jump point 크러스컬 Lexicographic BFS LPA* 프림 SMA* 출처: https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 퇴각검색 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 퇴각검색.. 2024. 2. 14. 프로필 마크다운 I'm Hyunsu Park(Hanzch, Uranus99.77) 2024. 2. 10. 14889번 스타트와 링크 - 백 트래킹 14889번 스타트와 링크 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 더보기 문제의 이해 어떤 사람과 팀이 되느냐에 따라 능력치가 달라질 때 두 팀의 능력치 차이가 가장 적을 때 얼마인지 알아내는 문제다. 직관적으로 떠오르는 방법은 조합을 구하고 팀 1,2를 조합해서 최소값을 찾으면 되는 문제인데 백트래킹이 붙어 있어서 아마 안 되겠지 생각하며 해 보았는데 성공. 조합을 생각해 보면 한 팀만 구성하면 나머지 팀이 완성되기 때문에, 그리고 인원이 짝수인 것이 보장되기 때문에 $$n C (n/2) = \frac{n!}{(n/2)!.. 2024. 2. 8. 이전 1 ··· 3 4 5 6 7 다음
