목록분류 전체보기 (106)
모눈종이에 사각사각
이번 포스팅에서는 다이나믹 프로그래밍에 대해 다뤄보고자 한다. 다이나믹 프로그래밍은 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀는 알고리즘 기법이다. 특정 조건이 만족되는 문제에서 다이나믹 프로그래밍을 사용하면, 중복되는 연산을 줄일 수 있다. 특정 조건은 다음과 같다. 1. 큰 문제를 작은 문제로 나눌 수 있다. (최적 부분 구조) 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. (중복되는 부분 문제) 다이나믹 프로그래밍을 구현하는 방법은 크게 두 가지가 있다. 첫 번째는 Top-down 방식인 메모이제이션(Memoization) 기법이다. 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. 메모..
🍎 Letter Combinations of a Phone Number 문제 링크 💿 문제 Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. ⚾ 코드 def solution(digits): # 알파벳 매핑 alpha = [[], [], ['a', 'b', '..
🍎 Number of Islands 문제 링크 💿 문제 Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. ⚾ 코드 def solution(grid): W = len(grid[0]) H = len(grid) visited = [[False]*W for _ in range(H)] count = 0 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def check_range(x, y): # print(x, y) if x >= 0 and x = 0 and y < W: # print(True) return Tr..
🍎 [백준 7569] 토마토 문제 링크 ⚾ 코드 from collections import deque M, N, H = map(int, input().split()) grid = [[] for _ in range(H)] for i in range(H): for _ in range(N): grid[i].append(list(map(int, input().split()))) # grid[i] = i층 # grid[i][x][y] = i층의 x, y좌표 q = deque() dh = [0, 0, 0, 0, 1, -1] dx = [-1, 1, 0, 0, 0, 0] dy = [0, 0, -1, 1, 0, 0] def check_range(h, x, y): if x >= 0 and x = 0 a..
🍎 [백준 7576] 토마토 문제 링크 ⚾ 코드 from collections import deque M, N = map(int, input().split()) grid = [] for _ in range(N): grid.append(list(map(int, input().split()))) q = deque() dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def check_range(x, y): if x >= 0 and x = 0 and y < M: return True return False def bfs(): while q: x, y = q.popleft() # 4 방향 살펴보기 for i in range(4): nx = x+dx[i] ny = y+dy[i..
🍎 [백준 2178] 미로 탐색 문제 링크 ⚾ 코드 from collections import deque N, M = map(int, input().split()) grid = [] visited = [[False]*M for _ in range(N)] for _ in range(N): grid.append(list(map(int, input()))) q = deque() dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def check_range(x, y): if x >= 0 and x = 0 and y < M: return True return False def bfs(a, b): visited[a][b] = True q.append([a, b]) while q..
🍎 [백준 1012] 유기농 배추 문제 링크 ⚾ 코드 import sys # 재귀 탐색 깊이 늘려주기 sys.setrecursionlimit(100000) input = sys.stdin.readline # 테스트케이스 T = int(input()) answer = [] for _ in range(T): M, N, K = map(int, input().split()) grid = [[0]*(M) for _ in range(N)] visited = [[False]*(M) for _ in range(N)] count = 0 for i in range(K): x, y = map(int, input().split()) grid[y][x] = 1 # 범위 체크 def check_range(x, y): if x >..
백준 1012번 문제 를 푸는데, 계속 런타임 에러가 떠서 헤매고 있었다. 백준의 자주 틀리는 요인을 참고했더니 파이썬의 재귀 깊이는 기본적으로 최대 1,000입니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다. 라고 나와있었다. 파이썬의 기본 재귀 깊이가 1000으로 얕기 때문에 더 깊이 조절해야 하는 것이다. 백준이나 다른 코딩테스트에서 파이썬을 이용하여 재귀 방식으로 코드를 구현할 경우 다음과 같은 코드를 상단에 써두어야 한다. import sys sys.setrecursionlimit(1000000) 1012번에 이 코드를 삽입했더니 바로 성공했다. 앞으로 잊지 않고 적도록 하자!
클래스를 사용하는 이유 추상화된 현실의 개념을 구체적인 파이썬 코드로 표현하기 위해 고양이 : 고양이 클래스(추상적인 개념) 주황색의 이름이 미미인 고양이 : 인스턴스(색, 이름등 구체적 값을 가짐) 클래스 생성 ## 클래스 정의하기 class Cat: # 인스턴스 변수와 메소드 구현하는 위치 def meow(self): # meow() 메소드 정의 print("야옹") ## 인스턴스 생성 및 메소드 호출 ### 메소드 호출은 마침표 연산자 사용 cat1 = Cat() # 인스턴스 생성 cat1.meow() # 메소드 호출 인스턴스 변수 생성 class Cat: def info(self): # info() 메소드 self.name = "나비" # 인스턴스 변수 name 생성 self.color = "검정..