개발 · 컴퓨터공학/알고리즘

백준 2503 숫자야구 파이썬 문제풀이 (python 완전탐색, 재귀, 백트래킹)

문제 보러가기 백준 숫자야구 파이썬 문제풀이 숫자야구는 저번에 풀었었지만, 이번에는 재귀를 사용해서 풀어볼 것이다.  재귀로 각각의 중복되지 않은 세 자리 자연수를 검사하고, 그 안에서 모든 조건을 만족하는 수의 개수를 카운트 하는 방식으로 진행하면 될 것이다. 정답 코드 1n = int(input())answer = 0def check(number, question, strk, ball): s = 0 b = 0 for i in range(3): if number[i] == int(question[i]): s+=1 elif int(question[i]) in number: b+=1 if strk == s and ball..

2024. 9. 26. 11:37

개발 · 컴퓨터공학/알고리즘

백준 15649 N과M 파이썬 문제풀이 (python 완전탐색, 재귀, 백트래킹)

문제 보러가기 백준 N과M 파이썬 문제풀이자연수 N과 M 이 있으면 1~N까지 수로 길이가 M인 중복 없는 수열을 모두 구하는 문제이다. 제약이 많지 않아서 반복문으로도 단순히 구현할 수 있지만 재귀함수를 사용해보자. 정답코드n,m = map(int,input().split())# m = depthdef recur(depth, lst): if depth == m: for l in lst: print(l,end=' ') print() return else: for i in range(1,n+1): if i not in lst: recur(depth+1, lst+[i])recur(0..

2024. 9. 25. 12:02

개발 · 컴퓨터공학/알고리즘

백준 3020 개똥벌레 파이썬 문제풀이 (python 누적합)

문제 보러가기 백준 개똥벌레 파이썬 문제풀이동굴에 아래에서 올라오는 석순과 위에서 내려오는 종유석이 한 칸씩 번갈아 나온다.이 중 하나의 높이에 고정해서 벌레는 뚫고 가는데,가장 적게 장애물을 뚫는 곳의 개수와 몇 개를 뚫는지 구하는 문제이다.  단순하게 생각하면 오른쪽으로 이동하면서장애물의 누적 개수를 쌓아가며 최소인 칸들을 구하면 될 것 같은데 정말 신기한 방법이 다있다.장애물이 시작되는 칸을 1이라고 하고, 끝난 다음칸을 -1로 설정한다.  -1 -1  -1    1 1  -1   1 1 예를 들어 그림의 경우 4까지의 길이만 표현해보면 이런 식이다.원래 5칸인데, 가장 위의 칸은 여분으로 하나를 추가한 것이다. 위 숫자들을 더하면 아래-위 순서대로2 -1 1 1 -1 -2 가 된다.마지막 6번째는..

2024. 9. 24. 11:16

개발 · 컴퓨터공학/알고리즘

백준 11660 구간 합 구하기 파이썬 문제풀이 (python 누적합)

문제 보러가기  백준 구간 합 구하기 파이썬 문제풀이문제는 주어진 2차원 배열 안에서 특정 범위의 합을 구하는 문제이다.범위의 합을 구하는 문제는 누적합으로 접근하면 좋다. n,m = map(int, input().split())arr = []for _ in range(n): arr.append(list(map(int, input().split())))xy = []for _ in range(m): xy.append(list(map(int, input().split())))# 누적합 구하기 크기는 1칸 더 크게accum = [[0] * (n+1) for _ in range(n+1)]for i in range(n): for j in range(n): accum[i+1][j+1] ..

2024. 9. 23. 12:00

개발 · 컴퓨터공학/알고리즘

백준 2304 창고 다각형 파이썬 문제풀이 (python 누적합)

문제 보러가기   백준 창고 다각형 파이썬 문제풀이기둥들을 가지고 가장 적은 넓이를 만드는 문제이다.왔다갔다 안하고 최대한 일직선이 많은 방향으로 오목하지 않으면서 최소 넓이를 만드려면 어떻게 할까.양쪽에서부터 최대 높이인 지점까지 양 방향으로 면적을 구하는 방법을 사용해야한다. 왼쪽에서부터 최대 높이까지 지점의 넓이 누적합을 구하고,오른쪽에서부터 최대 높이까지 지점의넓이 누적합을 구한다. n = int(input())graph = [0]*10001x_list = []y_list = []for i in range(n): x,y = map(int, input().split()) graph[x] = y x_list.append(x) y_list.append(y)maxHeight = ma..

2024. 9. 22. 11:36

개발 · 컴퓨터공학/알고리즘

백준 1912 연속합 파이썬 문제풀이 (python 누적합)

문제 보러가기  백준 연속합 파이썬 문제풀이n개의 정수 수열이 주어지면, 몇 개의 연속 수를 가지고 만들 수 있는 가장 큰 합을 구하는 문제이다. 이전 포스팅의 문제와 달리, 몇 개 연속인지 알려주지 않는다.그렇다면 일일히 찾아야한다는 점. 그러면 더더욱 누적합을 잘 이용해야한다. N = int(input())arr = list(map(int, input().split()))accum = [0 for _ in range(N+1)]answer = float('-inf')# 누적합 구하기for i in range(N): accum[i+1] = accum[i] + arr[i]cont = []# 연속되는 수열 합 구하기for i in range(1,N+1): list = [] for j in r..

2024. 9. 21. 11:14