코생코사

https://www.acmicpc.net/problem/11660처음에 dp의 누적합을 두고 풀어야 겠다는 생각을 했습니다.2024.09.28 - [분류 전체보기] - [Python] 누적합 알고리즘 [Python] 누적합 알고리즘[1,2,3,4,5,6,7,8,9,10] 리스트가 있다고 했을 때3번 인덱스부터 마지막 인덱스의 합을 구한다고 하자(인덱스는 1부터 시작)arr = [1,2,3,4,5,6,7,8,9,10]start = 3end = len(arr)print(sum(arr[start-1:end]))   그렇다면 이dogfoot1.tistory.com  1. 첫 번째 방법각 행마다 누적합을 구하고, x1행부터 x2행까지 반복문을 돌면서 값을 더한다.  누적합 리스트 sum_graph를 구하게 되면..

https://www.acmicpc.net/problem/1149 참고https://m.blog.naver.com/occidere/220785383050 [백준] 1149 - RGB거리 (2017-12-02 수정완료)문제 링크 : https://www.acmicpc.net/problem/1149 이 문제는 아주 전형적인 DP(동적 계획법) 문제 중 ...blog.naver.com dp를 사용하기 위해 점화식을 만든다현재 집의 R, G, B를 선택했을 때의 최솟값을 선택한다R이 0번 인덱스, G가 1번 인덱스, B가 2번 인덱스일 때현재 -1 집의 인덱스가 겹치지 않도록 점화식을 만든다 현재집에 R을 선택했을 때 -> R 선택 비용 + 현재-1집의 G, B 중 최소 비용dp[i][0] = lists[i][..

https://www.acmicpc.net/problem/9205저는 dfs를 사용하였습니다.DFS를 사용하는 이유: 거리가 되는 모든 방향을 탐색해야 하기 때문https://www.acmicpc.net/board/view/86660 x와 y의 값이 1000(20X50) 이하이면 갈 수 있다1000보다 크면 갈 수 없다  입력 받기from sys import stdint = int(stdin.readline())result = []for _ in range(t): n = int(stdin.readline()) # 편의점 개수 home_x, home_y = map(int, stdin.readline().split()) store = [] for _ in range(n): ..

+https://www.acmicpc.net/problem/1351 먼저 저는 다이나믹 프로그래밍을 사용해야겠다고 생각했습니다예를 들어 n=7, p=2, q=3이 나왔을 때 다이나믹 프로그래밍- 재귀 함수 + 메모제이션을 이용(탑다운 방식)- 반복문을 이용(보텀업 방식) 먼저 반복문을 이용하여 코드를 구현했습니다.from sys import stdinn, p, q = map(int, stdin.readline().split())dp = [0] * (n+1)dp[0] = 1for i in range(1, n+1): dp[i] = dp[i//p] + dp[i//q] print(dp[n])하지만 n이 최대 10의 12승이기 때문에 메모리 초과가 났습니다. 그래서 저는 메모리를 줄이기 위해 n//p와..

https://www.acmicpc.net/problem/1541  -40 +50-(40 +50) -40 +50 +30-(40 +50 +30) -40 +50 +30 +100-(40 +50 +30 +100) -40 +50 +30 +100 -1000-(40 +50 +30 +100) -1000 그리디를 이용- 뒤에 -가 올 때까지 모든 +를 -로 바꾼다 1. 입력 받기original = input() 2. 숫자와 기호를 분리# 숫자st = original.replace('+', ' ')st = st.replace('-', ' ')num = list(map(int, st.split()))여기에서 00009도 숫자로 바꿀 수 있다 # 기호pm = []for o in original: if o=='+' or ..

https://www.acmicpc.net/problem/2609 재귀함수를 이용한다 최대공약수: (나누는 수, 나머지) 최소 공배수: 최대 공약수 * 몫 * 몫# a가 더 큼def gcd(a, b): if a%b == 0: return b # 작은 수 return gcd(b, a%b)a, b = map(int, input().split())# a를 더 큰 값으로if b>a: a, b = b, a res = gcd(a, b)# 최대공약수print(res)# 최소공배수print(res * (a//res) * (b//res))

https://www.acmicpc.net/problem/4949  저는 stack을 이용하여 구현하였습니다.2023.12.16 - [코딩테스트 문제] - [프로그래머스/Python] 올바른 괄호 [프로그래머스/Python] 올바른 괄호문제 https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘dogfoot1.tistory.com의 상위 버전입니다. 1. 무한 반복문을 사용하고, '.'이 들어오면 break2. 들어온 문자열 중 ()[] 만 남긴다3. no가 되는 상황에 대한 함수 작성 no 가 되는 상황1. s..

https://www.acmicpc.net/problem/1929 소수 구하기 방법 3가지https://seongonion.tistory.com/43 소수판별 알고리즘 - 파이썬 (Python)알고리즘 문제를 풀다보면 특정 수들이 소수인지 판단하도록 요구하는 문제들이 줄곧 있다. 아예 대놓고 소수찾기라는 문제만 쳐봐도 꽤 많은 문제들이 나올 것이다. 소수는 영어로 Prime Number라seongonion.tistory.com 1. 하나씩 보기2. 제곱근3. 에라토스테네스의 체 저는 2번과 3번을 구현해보겠습니다. 2. 제곱근True: 소수False: 소수가 아님 제곱근을 위해서는 math 라이브러리를 임포트 합니다.from sys import stdinfrom math import sqrtm, n = ..

탐색- 순차 탐색데이터를 앞에서부터 순서대로 확인최악의 경우 시간 복잡도 O(N)- 이진 탐색데이터가 정렬이 되어있을 때 사용할 수 있지만 빠르게 찾을 수 있다.시작점, 끝점, 중간점이 필요시간 복잡도 O(logN) 탐색이 많은 문제에서 sort()를 하고 이진 탐색을 이용하는 방법이 있습니다 이진 탐색 구현data =[0,2,4,6,8,10,12,14,16,18]  재귀 함수를 이용한 이진 탐색 코드def binary_search(array, target, start, end): if start > end: # start, mid, end 다 같을 때 mid+1이나 mid-1하면 start>end가 됨 return None mid = (start + end)//2 ..

https://www.acmicpc.net/problem/11047  그리디(탐욕법)을 이용한다 n, k = map(int, input().split())money = []for _ in range(n): money.append(int(input()))cnt = 0for m in money[::-1]: if k//m == 0: continue else: cnt += k//m k = k % mprint(cnt)