반응형 알고리즘35 #31 [파이썬] LeetCode: Number of Islands https://leetcode.com/problems/number-of-islands/ Number of Islands - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 코드 class Solution: def dfs(self, grid: List[List[str]], i: int, j: int): if i = len(grid) or j = len(grid[0]) or grid[i][j] == '0': return grid[i.. 2022. 2. 12. #30 [파이썬] 프로그래머스: N으로 표현 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 해결 과정 1~8개의 N을 사용할 수 있다. 사용 개수에 따라 가능한 모든 경우를 저장한 후, number가 있는 지 없는 지 판단한다. 사용 개수를 key, 가능한 경우를 value로 하여 dictionary를 만든다. 5, 55, 555, 5555와 같이 연산이 아닌 단순히 이어붙인 경우는 따로 미리 포함시킨다. 첫번째 for문은 1~8개를 차례대로 고려하는 것이다. (최솟값을 찾는 것이므로 작은 수 부터) 두번째 for문을 이해하기 위해서는 아래 예시를 이해해야 한다. [3개 경우] 1개 리스트 원소 (+, -, *, //) 2개 리스.. 2022. 1. 17. [알고리즘] 다이나믹 프로그래밍이란? 다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개어 해결하는 것을 말한다. 분할정복과 다른 점은 쪼개진 작은 문제가 여러 곳에서 중복적으로 발생한다는 점이다. 따라서 같은 문제를 중복 계산하지 않고 솔루션을 공유하여 효율화하는 것이 중요하다. Dynamic Programming 알고리즘 조건 1) problem이 sub-problem으로 나누어 질 때 2) 각 sub-problem의 solution을 통해 상위 problem의 솔루션을 구할 수 있을 때 3) sub-problem들이 중복되며, 그 문제의 솔루션이 같을 때 → memoizaion 위 세 가지 조건을 충족하는 문제는 dynamic programming으로 해결할 수 있으며, 대표적인 예시로 피보나치 수열이 있다. Top-down (재귀함수).. 2022. 1. 16. #28 [파이썬] 백준 2579번: 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 1. Index Error가 난 코드 (실패) import sys input = sys.stdin.readline score = [] n = int(input()) for _ in range(n): score.append(int(input())) result = [0]*n result[0] = score[0] result[1] = score[0] + score[1] result[2] = max(score[0].. 2021. 7. 1. 이전 1 2 3 4 5 ··· 9 다음 728x90 반응형
