본문 바로가기
반응형

프로그래밍/Algorithm110

동적 계획법(Dynamic Programming, DP) 동적 계획법이란? 동적 계획법(DP, 다이내믹 프로그래밍)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다. 큰 문제를 작은 문제로 쪼개서 그 답을 저장해 두고 재활용한다가 핵심이다. 동적 계획법 사용 이유 일반적인 재귀(Native Recursion) 방식 또한 DP와 매우 유사하다. 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 피보나치수열은 아래와 같다. 1, 1, 2, 3, 5, 6, 13, 21, 34, 55, 89, 144... 피.. 2023. 9. 1.
[프로그래머스 Programmers] 거스름돈 문제 설명 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다. 1원을 5개 사용해서 거슬러 준다. 1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다. 1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다. 5원을 1개 사용해서 거슬러 준다. 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세.. 2023. 9. 1.
깊이 우선 탐색(Depth-first search, DFS) 깊이 우선 탐색이란? 분류 : 검색 알고리즘 자료 구조 : 그래프(Graph) 깊이 우선 탐색(Depth-first search, DFS)은 맹목적 탐색방법의 하나로 탐색트리의 하나로 탐색트리의 최근에 첨가된 노드를 선택하고, 이 노드에 적용 가능한 동작자 중 하나를 적용하여 트리에 다음 수준(level)의 한 개의 자식노드를 첨가하며, 첨가된 자식 노드가 목표 도일 때까지 앞의 자식 노드의 첨가 과정을 반복해 가는 방식이다. 의사 코드(Pseudo Code) DFS(G, u) u.visited = true for each v ∈ G.Adj[u] if v.visited == false DFS(G,v) init() { For each u ∈ G u.visited = false For each u ∈ G D.. 2023. 8. 30.
스택(Stack) 자료구조 스택(Stack)이란? 스택은 데이터를 후입선출(First-In Last-Out) 방식으로 저장하는 자료구조이다. 데이터를 제한적으로 접근 할 수 있는 구조이며, 한쪽 긑에서만 자료를 넣거나 뺄 수 있는 구조이다. 스택은 콜 스택(Call stack)이라 하여 컴퓨터 프로그램의 서브루틴에 대한 정보를 저장하는 자료구조로써 널리 활용된다. 컴파일러가 출력하는 에러도 스택처럼 맨 마지막 에러가 가장 먼저 출력되는 순서를 보인다. 또한 스택은 메모리 영역에서 LIFO 형태로 할당하고 접근하는 구조인 아키텍처 레벨의 하드웨어 스택의 이름으로도 널리 사용된다. 이외에도 꽉 찬 스택에 요소가 넘쳐서 에러가 발생하는 것을 스택 버퍼 오버플로(Stack Buffer Overflow)라고 부른다. 프로그래밍 관련 질의응.. 2023. 8. 30.
너비 우선 탐색(Breadth-first search, BFS) 너비 우선 탐색이란? 분류 : 검색 알고리즘 자료 구조 : 그래프(Graph) 너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 ㅇ낳은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. 의사 코드(Pseudo Code) def breadth_first_search(problem): # a FIFO open_set open_set = Queue() # an empty set to maintain visited nodes closed_set = set() # a dictionary to maintain meta information .. 2023. 8. 30.
그래프(Graph) 자료구조 그래프(Graph)란 무엇인가? 정점(Vertex)과 그 정점을 연결하는 간선(Edge)을 하나로 모아 놓은 자료구조. 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조 G = (V, E) ex. 지도, 지하철 노선도, 전기 회로의 소자들, 도로 등 그래프의 종류 무방향 그래프(Undirected graph) 두 정점을 연결하는 간선에 방향이 없는 그래프, 두 정점의 양 방향으로 이동 가능 방향 그래프(Directed graph) 두 정점을 연결하는 간선에 방향이 있는 그래프. 특정 방향으로만 이동 가능 가중 그래프(Weighted graph) 정점을 연결하는 간선에 가중치(Weight)가 있는 그래프. 네트워크(Network) 라고도 함 완전 그래프(Complete graph) 그래프의 모든 정.. 2023. 8. 29.

티스토리툴바