목록coding (165)

이모저모

동적 계획법 연습 - 집도둑(leetcode)

문제: https://leetcode.com/problems/house-robber/ # 프로그래머스의 도둑질과 거의 똑같은 문제!(다만 프로그래머스는 원형으로 집이 배열되어 있다) 📝 배운 점 처음에 내가 풀었던 방법은 시간 효율이 안 좋았다. 그래서 discuss에 추천을 많이 받은 풀이를 찾아보았는데, 좋은 방법을 배우게 되었다. - 내 접근: 훔치기로 확정한 집이 1번인 경우와 2번인 경우 이렇게 두 경우로 나누어서 for 문을 두 번 돌렸다. - 다른 분의 접근: for문을 한 번만 돌려서 해결한다! 훔칠 수 있는 최대 액수를 기록해가는 배열 맨 앞쪽에 0으로 초기화하는 빈 인덱스를 3개 추가해주면 1번을 fixed하는 경우나 2번을 fixed하는 경우가 다 고려된 동적 배열을 기록해갈 수 있기..
coding/알고리즘,자료구조 2022. 2. 9. 13:51
동적 계획법 연습 - 계단오르기(leetcode)

문제: https://leetcode.com/problems/climbing-stairs/ 1칸 혹은 2칸씩 오를 수 있다면 n번째 칸에 이를 수 있는 방법은 몇 가지인지 구하기 bottom-up의 대표적인 예제! class Solution: def climbStairs(self, n: int) -> int: # bottom-up 으로 동적으로 기록해갈 배열 dy = [0] * (n+1) # 작고 확실한 출발점 dy[0] = 1 dy[1] = 1 # 전칸, 전전칸까지 올 수 있던 방법수를 합하여 해당 칸에 기록 for i in range(2, n+1): dy[i] = dy[i-1] + dy[i-2] return dy[n]
coding/알고리즘,자료구조 2022. 2. 9. 13:03
동적 계획법 연습(bottom-up) - 최대서브배열(leetcode)

문제:https://leetcode.com/problems/maximum-subarray/ 손계획 코드 class Solution: def maxSubArray(self, nums) -> int: # 각 인덱스의 숫자를 끝점으로 하는 배열들 중 최대합을 적어가기 위한 기록 테이블 n = len(nums) record = [0] * n record[0] = nums[0] for i in range(1, n): # 이전칸까지의 최대합이 음수면 이전의 정보는 반영 안하고 자신만을 반영 if record[i-1] < 0: record[i] = nums[i] # 이전칸까지 최대합이 양수면 더하는 게 무조건 나으므로 반영하여 자신도 추가 else: record[i] = record[i-1] + nums[i] ret..
coding/알고리즘,자료구조 2022. 2. 9. 12:44
이분 탐색 연습 - 수찾기(백준)

문제: https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 코드 import collections import sys n = int(sys.stdin.readline().rstrip()) A = list(map(int, sys.stdin.readline().split())) m = int(sys.stdin.readline().rstrip()) B = list(map(int, sys.stdin.read..
coding/알고리즘,자료구조 2022. 2. 9. 01:53
동적 계획법 연습 - 도둑질(프로그래머스)

문제: https://programmers.co.kr/learn/courses/30/lessons/42897 코드 def solution(money): n = len(money) # 인덱스 사용 편하게 하려고 맨 앞에 0번 빈 자리 만들기 tmp = [0] money = tmp + money # 최대 돈 액수를 구하기 위한 다이나믹 테이블 # 앞 뒤로 한 칸씩 더 만들어줘서 0을 두면 인덱스 에러 없이 사용하기 위한, 무의미한 가장자리를 만들어줄 수 있다. dy = [0]*(n+2) # 첫 집은 털기로 결정한 경우. # 뒤에서부터 인접한 것을 건너서 해당 집을 털 경우의 가능한 최대 액수를 기록해가는 과정 # n 번째 집은 털 수 없으므로 for 범위에 미포함 dy[1] = money[1] for i i..
coding/알고리즘,자료구조 2022. 2. 9. 00:35
동적 계획법 연습 - 등굣길(프로그래머스)

문제: https://programmers.co.kr/learn/courses/30/lessons/42898 def solution(m, n, puddles): # 각 칸에 이르기 위한 최단거리의 가지 수 기록할 동적 배열 dy = [[0]*m for _ in range(n)] for i in range(n): for j in range(m): isPuddle = False # i, j가 물웅덩이라면 거기로 갈 수 있는 방법 수는 0 for puddle in puddles: if puddle[1] == i+1 and puddle[0] == j+1: dy[i][j] = 0 isPuddle = True break # 물웅덩이가 아니라면 if not isPuddle: # 시작점이라면 확실하게 1을 리턴 (작고..
coding/알고리즘,자료구조 2022. 2. 8. 16:23
Prev 1 2 3 4 5 6 7 ··· 28 Next