본문 바로가기

전체 글

 (131)
[백준 / Python] 동전 1_2293 n, k = map(int, input().split()) data = [] for _ in range(n): data.append(int(input())) counts = [0 for _ in range(10001)] counts[0] = 1 for coin in data: for price in range(10001): if price >= coin: counts[price] += counts[price-coin] print(counts[k]) 이 문제는 전형적인 DP문제이다. DP에서는 분할정복과 같은 방법으로 문제를 작은 부분문제로 나눠서 풀고, 캐시하여 재사용될 때 활용해 해결하는 것이다. 왜 이전의 counts값을 더하는걸까? -> 가장 작은 단위의 부분 문제로 본다면, counts[price..
[백준 / Python] 차이를 최대로_10819 정답 코드 n = int(input()) check = [False for _ in range(n)] orders = [0 for _ in range(n)] data = list(map(int, input().split())) result = [] def dfs(idx): if idx == n: result.append(cal_solution()) return for i in range(n): if not check[i]: orders[idx] = i check[i] = True dfs(idx + 1) check[i] = False def cal_solution(): sum = 0 for i in range(n - 1): sum += abs(data[orders[i]] - data[orders[i + 1..
DP 동적 계획법 개념 DP(Dynamic Programing)은 직역하면 동적인 프로그래밍이다. 여기서 프로그래밍은 코드를 작성하는 행위를 뜻하는 것이 아니라, 테이블을 이용한다는 뜻을 의미한다. + 테이블을 이용한다가 무슨 뜻일까? DP에서는 이전의 값을 저장하여, 한번 구한 값은 다시 구하지 않는다. 이때의 저장하는 배열을 테이블이라고 하는 것 같다. 필요한 배경지식 DP는 왜 등장한 것일까? DP는 이전에 구했던 값을 활용하여 효율성을 증가시키기 위해 만들어진 것이다. 이를 조금 다르게 생각해 보면, 이전에 구했던 값을 반복해 구하는 상황에서, 이러한 비효율적인 문제를 해결하기 위해 나온 것이라고 볼 수 있다. 흔히 DP는 트리를 그리는 것과 흡사하다고 한다. 왜 트리를 그리는 것과 흡사할까? 이를 좀 더 쉽게 이해하기..
[백준 / Python] 벽 부수고 이동하기_2206 정답 코드 from _collections import deque dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] n, m = map(int, input().split()) data = [list(map(int, input())) for _ in range(n)] visited = [[[-1, -1] for _ in range(m)] for _ in range(n)] def bfs(): q = deque() q.append((0, 0, 0)) visited[0][0][0] = 1 while q: pop_x, pop_y, flag = q.popleft() for i in range(4): nx, ny = pop_x + dx[i], pop_y + dy[i] if 0
[자료구조] List - 배열로 구현하기 "리스트를 배열로 구현한다"는 무슨 말일까? 리스트는 ADT(Abstract Data Type)이다. 즉, 리스트 자체는 인터페이스와 같은 추상적인 것이고 제시된 명세서에 따라 내부 구현은 각각 다를 수 있다. 이때 구현 과정을 배열로 하느냐, 링크드 리스트로 하느냐에 따라 내부적으로 다르게 구현된다. 리스트에서 명시한(구현해야 하는) 기능들이 있는데, 그 기능을 배열로 어떻게 구현하는지 설명하겠다. Add(index, data) 특정 구간에 삽입 - Big-O: O(N) 배열로 구현하였을 때, 특정 구간에 데이터를 삽입하는데 O(N)의 시간 복잡도를 가지게 된다. 특정 구간에 넣어줘야 할 때, 모든 요소를 한 칸씩 다 옮겨줘야 하는 경우가 최악의 경우 N이기 때문이다. remove(index) 특정 인..
[자료구조] Cache 자료구조(Data Structure)란? 사전적인 의미로는 자료(Data)의 집합을 의미하며, 각 원소들이 논리적으로 정의된 규칙에 의해 나열되며 자료에 대한 처리를 효율적으로 수행할 수 있도록 자료를 구분하여 표현한 것이다. 자료구조를 사용하는 목적은 자료를 더 효율적으로 저장하고, 관리하기 위해 사용한다. 지난 학기 OS 수업 시간에 메모리 구성과 동작 과정에 대해 간단하게만 언급해주셨던 기억이 있다. 그 당시에는 LRU라던지 레지스터 등과 같은 개념을 사전적 정의로만 들어서 제대로 와닿지가 않았다. 지금은 메모리를 단계별로 구성하여 설명하겠다. CPU가 메모리에 접근하는 방식 CPU가 메모리에 접근하는 방식은 그림과 같다. 1. Cache에 접근하고자 하는 데이터(주소)가 있는지 확인한다. 2. 캐..
[백준 / Python] 차이를 최대로_10819(미완성) 보호되어 있는 글입니다.
[백준 / Python] 연구소_14502 틀렸던 내 풀이 from _collections import deque from copy import deepcopy n, m = map(int, input().split()) data = [list(map(int, input().split())) for _ in range(n)] dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] result = [] # 바이러스 퍼뜨리기 def bfs(deep_copy): map = deepcopy(deep_copy) q = deque() virus = find_virus(map) visited = [[False for _ in range(m)] for _ in range(n)] for i in virus: x, y = i q.append((x, y)..

티스토리툴바