본문 바로가기

개발

 (99)
DP 동적 계획법 개념 DP(Dynamic Programing)은 직역하면 동적인 프로그래밍이다. 여기서 프로그래밍은 코드를 작성하는 행위를 뜻하는 것이 아니라, 테이블을 이용한다는 뜻을 의미한다. + 테이블을 이용한다가 무슨 뜻일까? DP에서는 이전의 값을 저장하여, 한번 구한 값은 다시 구하지 않는다. 이때의 저장하는 배열을 테이블이라고 하는 것 같다. 필요한 배경지식 DP는 왜 등장한 것일까? DP는 이전에 구했던 값을 활용하여 효율성을 증가시키기 위해 만들어진 것이다. 이를 조금 다르게 생각해 보면, 이전에 구했던 값을 반복해 구하는 상황에서, 이러한 비효율적인 문제를 해결하기 위해 나온 것이라고 볼 수 있다. 흔히 DP는 트리를 그리는 것과 흡사하다고 한다. 왜 트리를 그리는 것과 흡사할까? 이를 좀 더 쉽게 이해하기..
[자료구조] 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] 연구소_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)..
[Spring] 빈 생명주기, 빈 스코프 Bean 생명주기란? 스프링 컨테이너는 Bean을 주입하는 것 이외에 생성과 소멸과 같은 생명 주기를 관리한다. 빈 생명주기 스프링 빈은 객체 생성 후, 의존관계 주입이 다 끝난 후에 필요한 데이터를 사용할 수 있는 준비가 완료된다. -> 여기서 사용할 수 있는 준비라는 것은 빈이 생성되는 것을 말하는 건가? 따라서 초기화 작업은 의존관계 주입이 모두 완료되고 난 다음에야 호출한다. 의존관계 주입이 완료되면, 스프링 빈에게 콜백 메소드를 통해서 초기화 시점을 알려주는 다양한 기능을 제공한다. 또한 스프링 컨테이너가 종료되기 직전에 소멸 콜백을 준다. 스프링 빈의 이벤트 라이프사이클 스프링 컨테이너 생성-> 스프링 빈 생성 -> 의존관계 주입 -> 초기화 콜백 -> 사용 -> 소멸 전 콜백 -> 스프링 종..
[ 백준 / Python ] 피보나치의 수 DP를 사용하여 푼 풀이 def solved(num): dp = [0 for _ in range(46)] dp[0] = 0 dp[1] = 1 for i in range(2, num+1): dp[i] = dp[i-1] + dp[i-2] return dp[num] print(solved(int(input()))) 재귀로 풀기 위해 시도한 코드들 틀린 코드 - 시간 초과 def recursive(num): if num == 0: return 0 if num == 1: return 1 return recursive(num - 1) + recursive(num - 2) n = int(input()) print(recursive(n)) 시간 초과가 난 이유가 뭘까? 위 코드는 그림을 보면 알 수 있듯이, 같은 작업..
[알고리즘] 시간 복잡도 Big-O 시간 복잡도란? 입력데이터가 n개 있을 떄, 최악의 경우의 연산 횟수를 n의 함수로 나타낸 것. 왜 입력데이터가 n개일 때인가? 알고리즘 A, B가 있을 때 두 가지 상황을 가정하자. 1. 입력 데이터가 다른 상황 A는 3초가 소요되는 알고리즘이고, B는 7초가 소요되는 알고리즘이다. 하지만 그렇다고 A가 더 빠른 알고리즘이라고 할 수 없다. 두 알고리즘에 대한 입력 값이 서로 다를 수 있기 때문이다. 2. 입력 데이터가 같아도 상황에 따라 다를 수 있다. 예를 들어, 10개의 데이터에 한해서는 A가 B보다 빠를 수 있지만, 10000개의 데이터에 한해서는 B가 더 빠를 수 있다. 결론: 그렇기 때문에 입력 데이터가 n개 일때, 최악의 경우의 연산 횟수를 n의 함수로 나타낸 것이 시간 복잡도 Big-O로..
[ 삼성 기출 / Python ] 청소년 상어 처음 틀린 풀이 from copy import deepcopy dx = [(0, 0), (-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)] shark = int(1e9) def solved(): fish_pos = [[0, 0] for _ in range(17)] data = [[[0, 0] for _ in range(4)] for _ in range(4)] for i in range(4): value = list(map(int, input().split())) cnt = 0 for j in range(0, 7, 2): fish_pos[value[j]][0], fish_pos[value[j]][1] = i, cnt data[i][c..

티스토리툴바