전체 글

https://www.acmicpc.net/problem/9465 문제상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다.상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다.모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시..

01 다이나믹 프로그래밍**Dynamic Programming**이란?큰 문제를 작은 문제들로 나누어 해결한 후, 그 결과를 저장하여 중복 계산을 줄이는 최적화 기법(알고리즘)이다.분할정복(Divied and Conquer)도 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다.다이나믹 프로그래밍과 분할 정복의 차이는 큰 문제를 작은 문제로 나눴을 때, 중복이 가능한지 불가능한지이다.DP는 작은 문제의 중복이 된다.분할정복은 작은 문제의 중복이 안된다.10을 나눌 때 분할 정복이라면 5/5, 6/4, 7/3, 3/7과 같이 중복이 되지 않게 나눈다.10을 나눌 때 다이나믹 프로그래밍이라면 5,5,3,과 같이 중복이 되게 나눈다.다이나믹 프로그래밍이란 이름 자체엔 아무런 의미가 없다. 02 다이나믹 프로그래밍..

자료 구조 중 이진트리를 순회하는 방법은 세가지 방법이 있다. 자세한 내용은 아래의 포스터를 확인해보면 된다.2024.05.09 - [Algorithm] - [Algorithm] 이진 트리(Binary Tree)와 트리 순회(Tree Traversal) [Algorithm] 이진 트리(Binary Tree)와 트리 순회(Tree Traversal)예시는 모두 Javascript를 이용하여 구현하였다. 트리 & 그래프우선 그래프 탐색을 하기 위해서는 그래프에 대해 알아야한다. 트리와 그래프는 가장 대표적인 그래프형 자료구조이다. Tree는 서로sootech-story.tistory.com 전위 순회 (Pre-order)중위 순회 (In-order)후위 순회 (Post-order)이러한 순회 방법은 트리 내..

예시는 모두 Javascript를 이용하여 구현하였다. 트리 & 그래프우선 그래프 탐색을 하기 위해서는 그래프에 대해 알아야한다. 트리와 그래프는 가장 대표적인 그래프형 자료구조이다. Tree는 서로 연결된 Node의 계층형 자료구조로써, root와 부모-자식 관계의 subtree로 구성되어있다.두 개의 노드 사이에 1개의 경로만을 가지며 사이클이 존재하지 않은 방향 그래프이다. 따라서 '최소 연결 트리'라고 부르기도 한다.트리 순회에는 전위순회, 중위순회, 후휘순회 3가지가 존재한다.그래프(G)는 정점(vertex)들의 집합 V와 이들을 연결한 간선(edge)들의 집합 E로 구성된 자료구조이다. 이를 통해 연결된 노드 간의 관계를 표현할 수 있는 자료구조이다. \트리그래프정의단일 루트 노드로 연결된 노..