전.py 검색 결과

338 개의 검색 결과가 있습니다.

전.py

[python] 1로 만들기

1) X가 5로 나누어 떨어지면, 5로 나눔 2) X가 3으로 나누어 떨어지면, 3으로 나눔 3) X가 2로 나누어 떨어지면, 2로 나눔 4) X에서 1을 뺌 - 4가지 연산을 사용해서 1로 만듦 - 최소 연산 횟수 출력 x = int(input()) # DP 테이블 초기화 d = [0] * 1000001 # 다이나믹 프로그래밍 (보텀업) for i in range(2, x + 1): # 현재의 수에서 1을 빼는 경우 d[i] = d[i - 1] + 1 # 현재의 수가 2로 나누어 떨어지는 경우 if i % 2 == 0: d[i] = min(d[i], d[i // 2] + 1) # 현재의 수가 3으로 나누어 떨어지는 경우 if i % 3 == 0: d[i] = min(d[i], d[i // 3] + 1)..

2022. 2. 25. 16:01

전.py

[python] 개미 전사 (다이나믹 프로그래밍)

- 식량을 억기 위해 최소 한 칸 이상 떨어진 식량 창고 약탈 - 얻을 수 있는 식량의 최댓값 n = int(input()) # 식량 개수 array = list(map(int, input().split())) # 식량 데이터 # DP 테이블 초기화 d = [0] * 100 # 다이나믹 프로그래밍 (보텀업) d[0] = array[0] d[1] = max(array[0], array[1]) for i in range(2, n): d[i] = max(d[i - 1], d[i - 2] + array[i]) # 결과 출력 print(d[n - 1])

2022. 2. 25. 15:52

전.py

[python] 다이나믹 프로그래밍

- 중복 연산 줄임 1) 최적 부분 구조 2) 중복되는 부분 문제 - 두 조건 만족하면 사용 가능 예) 피보나치 수열 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 - 점화식 : 인접한 항들 사이의 관계식 # 피보나치 함수 (재귀 함수) # 피보나치 함수(재귀함수) def fibo(x): if x == 1 or x == 2: return 1 return fibo(x - 1) + fibo(x - 2) print(fibo(4)) # 메모이제이션 - 탑다운, 하향식 - 메모했던 결과를 그대로 가져옴 - 캐싱 (값을 기록) d = [0] * 100 # 피보나치 함수(재귀함수) - 탑다운 다이나믹 프로그래밍 def fibo(x): if x == 1 or x == 2: return 1 if d[..

2022. 2. 25. 15:21

전.py

[python] 정렬된 배열에서 특정 수의 개수 구하기

- N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬 - x가 등장하는 횟수 계산 예) [1, 1, 2, 2, 2, 2, 3] 에서 x = 2 이면, 현재 수열에서 값이 2인 원소가 4개 from bisect import bisect_left, bisect_right def count_by_range(array, left_value, right_value): right_index = bisect_right(array, right_value) left_index = bisect_left(array, left_value) return right_index - left_index n, x = map(int, input().split()) # n, x 입력 array = list(map(int, input(..

2022. 2. 24. 12:09

전.py

[python] 떡볶이 떡 만들기 (이진 탐색)

- 높이(H) 보다 긴 떡은 H 위의 부분이 잘림, 낮은 떡은 잘리지 않음 예) 19, 14, 10, 17인 떡, 높이 H는 15 이면 => 15, 14, 10, 15 (잘린 떡의 길이 4, 0, 0, 2) => 6만큼 가져감 - 떡의 개수 N, 요청한 떡의 길이 M - 떡의 개별 높이 주어짐 - 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값 # 떡의 개수(N)와 요청한 떡의 길이(M) 입력 n, m = list(map(int, input().split())) # 각 떡의 개별 높이 정보 입력 array = list(map(int, input().split())) # 이진 탐색을 위한 시작점과 끝점 설정 start = 0 end = max(array) # 이진 탐색 수행 (반복문..

2022. 2. 24. 12:00

전.py

[python] 두 배열의 원소 교체 (정렬)

- 두 개의 배열 A, B - N개의 원소로 구성 - 최대 K 번 바꿔치기 연산 수행 - 배열 A의 모든 원소의 합이 최대가 되도록 n, k = map(int, input().split()) a = list(map(int, input().split())) # 배열 A b = list(map(int, input().split())) # 배열 B a.sort() # 배열 A는 오름차순 정렬 b.sort(reverse=True) # 배열 B는 내림차순 정렬 # 첫 번째 인덱스부터 확인하며, 두 배열의 원소를 최대 K번 비교 for i in range(k): # A의 원소가 B의 원소보다 작은 경우 if a[i] < b[i]: # 두 원소 교체 a[i], b[i] = b[i], a[i] else: # A의 원소..

2022. 2. 23. 18:30

전.py

[python] 정렬

- 데이터를 특정한 기준에 따라 순서대로 나열 # 선택 정렬 - 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것 반복 # 선택 정렬 array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], array[i] print(array) # 삽입 정렬 - 데이터를 하나씩 골라 적절한 위치에 삽입 # 삽입 정렬 array = [7, 5, 9, 0, 3, 1, 6,..

2022. 2. 23. 18:26

전.py

[python] 프로그래머스 내적

https://programmers.co.kr/learn/courses/30/lessons/70128 코딩테스트 연습 - 내적 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 programmers.co.kr def solution(a, b): answer = 0 for i in range(len(a)): answer += a[i]*b[i] return answer

2022. 2. 23. 14:10

전.py

[python] 백준 1448 삼각형 만들기

https://www.acmicpc.net/problem/1448 1448번: 삼각형 만들기 첫째 줄에 빨대의 개수 N이 주어진다. N은 3보다 크거나 같고, 1,000,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 빨대의 길이가 한 줄에 하나씩 주어진다. 빨대의 길이는 1,000,000보다 www.acmicpc.net import sys n = int(sys.stdin.readline()) data = [] for _ in range(n): data.append(int(sys.stdin.readline())) data.sort(reverse=True) flag = 0 for i in range(n-2): if data[i] < data[i+1] + data[i+2]: print(data[..

2022. 2. 23. 14:08

전.py

[python] 미로 탈출

- N x M 미로 - 시작 위치 (1, 1) - 출구 (N, M) - 괴물 있는 부분 0, 없는 부분 1 - 탈출하기 위해 움직여야 하는 최소 칸의 개수 => BFS 수행 from collections import deque # N x M 미로 n, m = map(int, input().split()) # 미로 정보 입력 graph = [] for i in range(n): graph.append(list(map(int, input()))) # 이동할 네 가지 방향 정의 (상, 하, 좌, 우) dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] # BFS def bfs(x, y): queue = deque() queue.append((x, y)) # 큐가 빌 때까지 반복 while qu..

2022. 2. 18. 15:01

전.py

[python] 음료수 얼려 먹기

- N x M 얼음 틀 - 구멍 0, 칸막이 1 - 생성되는 아이스크림 개수 1) 상하좌우 살펴본 뒤 '0' 이면서 아직 방문하지 않은 지점이면 방문 2) 방문한 지점에서 상하좌우 살펴보면서 방문 진행 과정 반복 => 연결된 모든 지점 방문 3) 1, 2 반복하여 방문하지 않는 지점의 수 카운트 # N x M 얼음 틀 n, m = map(int, input().split()) # 얼음 틀의 형태 graph = [] for i in range(n): graph.append(list(map(int, input()))) # DFS def dfs(x, y): if x = n or y = m: return False if graph[x][y] == 0: graph[x][y] = 1 dfs(x - 1, y) dfs..

2022. 2. 18. 14:50

전.py

[python] DFS & BFS

## DFS - 깊이 우선 탐색 - 최상단 노드 기준 - 스택 이용 # DFS 함수 정의 def dfs(graph, v, visited): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: if not visited[i]: dfs(graph, i, visited) # 각 노드가 연결된 정보를 리스트 자료형으로 표현(2차원 리스트) graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트) visited = [False] ..

2022. 2. 18. 14:44

전.py

[python] 유클리드 호제법 (재귀 함수)

- 두 개의 자연수에 대한 최대공약수 구함 - 두 자연수 A, B 에 대하여 (A > B) A를 B로 나눈 나머지를 R - A, B의 최대공약수는 B와 R의 최대공약수와 같음 # 재귀 함수 def gcd(a, b): if a % b == 0: return b else: return gcd(b, a % b) print(gcd(192, 162))

2022. 2. 18. 14:31

전.py

[python] 팩토리얼 (재귀 함수)

# 재귀 함수 def factorial(n): if n

2022. 2. 18. 14:28

전.py

[python] 재귀 함수

- 자기 자신을 다시 호출 def rf(): print('재귀 함수 호출') rf() rf() => 무한 호출 * 종료 조건 명시

2022. 2. 18. 14:27