넘치게 채우기

"이미 알고있는 답은 또 구하지 않는다" 사실 전혀 다이나믹하지 않고, 프로그래밍이라고 하기에도 애매하다. 벨만이라는 수학자가 펀딩을 잘 받기 위해서, 눈에 띄는 이름을 지은 것이다. 이광근 교수님의 저서 "컴퓨터과학이 여는 세계"에서는 '기억하며 풀기'라는 이름이 쓰였다. 하나의 큰 문제를 작은 문제로 나누어서, 그 결과를 얻고, 큰 문제의 답을 구하는 방식이다. "분할 정복법"과도 유사하다. 다이나믹 프로그래밍에는 두 가지 방법이 있다: 종류 메모이제이션 타뷸레이션 과정 하향식(Top down) 상향식(Bottom up) 구현 재귀 함수 반복문 장점 직관적이다 시간을 더 아낄 수도 있다 단점 재귀함수의 호출이 잦아 느려질 수 있다. DP테이블을 잘 채워야 한다. 기타 Lazy - Evaluation ..

https://leetcode.com/problems/add-digits/description/ Add Digits - LeetCode Can you solve this real interview question? Add Digits - Given an integer num, repeatedly add all its digits until the result has only one digit, and return it. Example 1: Input: num = 38 Output: 2 Explanation: The process is 38 --> 3 + 8 --> 11 11 --> leetcode.com 난이도 : Easy 문제 Given an integer num, repeatedly add all i..

https://leetcode.com/problems/roman-to-integer/ Roman to Integer - LeetCode Can you solve this real interview question? Roman to Integer - Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, 2 is written as II in Roman numeral, just tw leetcode.com 난이도 : Easy 문제 Roman numerals are represented by seven d..

https://www.acmicpc.net/problem/2638 2638번: 치즈첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로www.acmicpc.net문제 유형 : BFS solved.ac 난이도 : GOLD III 문제(자세한 내용은 위 링크(문제 본문) 참조) N * M의 모눈종이 위에 아주 얇은 치즈가 표시되어있다. N은 세로 격자의 수이고, M은 가로 격자의 수이다. 이 치즈는 냉동 보관을 해야만 하는데 실내온도에 내어놓으면 공기와 접촉하여 천천히 녹는다. 그런데 이러한 모눈종이 모양의 치즈에서 각 치즈 격자의 4변 중에서 최소 ..

정렬은 데이터들을 주어진 조건에 맞게 순차적으로 나열하는 것이다. 1. 버블 정렬(Bubble Sort) 한 번 순회할 때마다 마지막 하나가 정렬 된다. 거품이 올라오는 것 처럼 보여서 버블 정렬이라고 한다. 두 수를 비교하여, 조건에 맞으면 자리를 바꾼다. O(N^2)의 시간복잡도를 가진다. def bubble_sort(arr): for i in range(len(arr)): for j in range(len(arr)): if arr[i] < arr[j]: arr[i], arr[j] = arr[j], arr[i] 2. 선택 정렬(Selection Sort) 테이블에서 가장 작은 노드를 찾아서 맨 앞으로 위치를 바꾼다. 맨 앞에 놓인 노드 뒤부터 다시 똑같은 과정을 반복한다.(가장 작은 노드를 0번째 인..

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제 유형 : DFS / 트리 solved.ac 난이도 : Gold V 문제 트리에서 리프 노드란, 자식의 개수가 0인 노드를 말한다. 트리가 주어졌을 때, 노드 하나를 지울 것이다. 그 때, 남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성하시오. 노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거된다. 입력 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나..

BFS BFS(Breadth First Search)는 너비 우선 탐색으로, 가까운 노드부터 탐색하는 알고리즘이다. BFS에서는 큐 자료구조를 이용하여 구현한다. 인접한 노드들 중 방문하지 않은 노드를 큐에 추가하면 가까운 노드부터 탐색하는 것이다. 동작 방식은 다음과 같다: 1. 탐색 시작 노드를 큐에 넣고, 방문처리한다. 2. 큐에서 노드를 꺼내 큐의 인접 노드들 중 방문하지 않은 모든 노드들을 큐에 삽입하고, 순서대로 방문처리한다. 3. 2번의 과정을 계속해서 반복한다. 노드 '1'부터 시작해서 '1'을 큐에 넣고 방문처리한다. 노드 '1'을 큐에서 꺼내고, '1'의 인접 노드들 중 방문하지 않은 노드들을 모두 큐에 넣고 방문처리한다. 노드 '2'를 큐에서 꺼내고, 2에 인접한 노드들 중 방문하지 ..

DFS DFS는 Depth-Fisrst Search. 깊이 우선 탐색이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 사용하고, 최대한 깊숙히 노드를 방문하고, 끝에 도달하면 다시 돌아가서 다른 경로를 탐색한다. DFS 는 다음의 동작과정이 있다: 1. 탐색 시작 노드를 스택에 삽입하고, 노드를 방문처리한다. 2. 스택 맨 위에 있는 노드에서 방문하지 않은 인접 노드가 있으면, 그 인접 노드를 스택에 넣고, 방문처리한다. 방문하지 않은 인접 노드가 없으면, 스택에서 최상단 노드를 꺼낸다. 3. 2번을 계속 방문한다.(스택이 빌 때까지) DFS의 과정 1부터 탐색을 시작한다. 1을 스택에 넣고, 방문처리를 한다. '1'에서 방문하지 않은 인접 노드 '2', '3', '4'가 ..

재귀 함수란 자기 자신을 다시 호출하는 함수를 의미한다. 자기 자신을 계속해서 호출하다가, 일정한 조건이 만족되면 함수를 반환하여 결과를 도출한다. 컴퓨터 내에서 재귀 함수는 스택 자료구조와 동일하다. 함수를 계속 호출했을 때, 마지막으로 호출된 함수가 먼저 종료되어야 첫 함수가 종료된다. 아래는 재귀 함수의 대표적인 예시인 팩토리얼이다. def factorial(n): if n == 0 or n == 1: return 1 else: return n * factorial(n-1) 재귀 함수의 장점은 수학의 점화식을 표현한 코드여서 매우 간결한 표현이 가능하단 것이다. 단, 끝없이 재귀 함수가 반복되지 않도록 함수를 끝낼 수 있도록 조건을 만들어놓아야 한다.

그래프 그래프는 객체로 나타내는 정점(vertex)와 객체를 연결하는 간선(edge)의 집합으로 구성된다. G = (V, E) (V = 정점의 집합, E = 간선의 집합) 그래프의 종류 무방향 그래프 두 정점을 연결하는 간선에 방향이 없는 그래프이다. 정점 V1에서 정점 V2로 잇는 것을 표현하는 간선으로 (V1, V2)로 표현한다. (V2, V1)로 표현해도 같은 간선이다. 방향 그래프 두 정점을 연결하는 간선에 방향이 있는 그래프이다. 정점 V1에서 정점 V2로 잇는 것을 표현하는 간선으로 로 표현한다. 이랑은 다른 간선이다. 완전 그래프 각 정점에서 다른 모든 정점을 연결한 그래프이다. 최대로 많은 간선 수를 가지고 있다. 무방향 완전 그래프에서는 정점이 n개일 때, n(n+1)/2개의 간선을 가진..