Tong's Blog

동적 계획법이란 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. - 위키피디아 (https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95) - 그럼 동적 계획법은 어떤 경우에 사용하게될까요? Dynamic Programming은 작은 문제들로 나눈 뒤 합쳐서 결과를 얻는다는 점에서 분할 정복과 비슷한 방식이지만 분할 정복에서는 중복될 수 있는 부분을 Dynamic Program..

안녕하세요. 오랜만에 알고리즘 문제 포스트를 하게 되었습니다. 프로젝트를 시작한 이후로 알고리즘을 소홀히 하면서 감이 자꾸 떨어져서 다시 알고리즘도 틈틈히 해보려고 합니다. 문제는 블라인드에서 추천하는 문제들부터 차근차근 풀어보려고 합니다. 아 그리고 이번 포스트부터 Swift와 C++ 두가지 버전으로 풀어보겠습니다. 오늘의 문제는 Two Sum이고 LeetCode의 첫번째 문제입니다. (링크: https://leetcode.com/problems/two-sum/) 1. Int형 배열에서 2개의 숫자의 합이 target(Int) 되는 배열의 index를 return 하기 우선 가장 쉽게 생각해 볼 수 있는 방법은 Brute Force, 간단히 말해 모든 경우의 수를 탐색하는 방법으로 작성해보겠습니다. B..

더보기 그래프의 정의 그래프 G(V, E)는 어떤 자료나 개념을 개념을 표현하는 정점(vertex)들의 집합 V와 이들을 연결하는 간선(edge)들의 잡합 E로 구성된 자료구조이다. 정의만 보면 어렵게 느껴질 수 있지만 그래프라는 건 결과 하나 혹은 여러 개의 오브젝트(물체)와 그들간의 연결 상태를 나타내는 자료구조라고 생각하시면 됩니다. 더보기 그래프의 종류 무방향 그래프(undirected graph) : 간선이 양쪽 모두를 향해 연결되어 있는 그래프 방향 그래프(directed graph) : 간선에 방향이라는 속성이 존재하는 그래프 가중치 그래프(weighted graph) : 간선에 가중치라고 불리는 value가 존재하는 그래프 이 밖에도 여러가지 그래프가 있지만 가장 대체로 사용하는 그래프는 ..

오늘은 Greedy Algorithm(탐욕 알고리즘)에 대해서 알아보겠습니다. 탐욕 알고리즘은 Dynamic Programming과 마찬가지로 가장 최적화를 하기 위해서 만들어진 알고리즘입니다. 이 알고리즘을 탐욕 알고리즘이라고 부르는 이유는 탐욕 알고리즘의 기본 원칙이 더보기 각 단계에서 가장 최적의 답만을 선택한다. 이기 때문입니다. 미래를 생각하는 것이 아니라 지금 현재 단계만을 가지고 답을 도출하기 때문에 마치 욕심쟁이 같다고 생각되어 탐욕 알고리즘이라는 이름을 얻게 되었습니다. 그렇다면 일반적으로 탐욕 알고리즘을 사용하는 경우는 언제일까요? 탐욕 알고리즘은 최적화를 하기 위해 고안된 알고리즘이지만 다이나믹 프로그래밍과 다르게 모든 경우에서 최적의 답을 구해주진 않습니다. 위에서 언급했듯이 현재 ..

문제의 링크는 https://leetcode.com/problems/sort-colors/ 이다. Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library's sort function for th..

우선 문제의 링크는 https://leetcode.com/problems/reverse-integer/ 이다. 단순히 주어진 숫자를 거꾸로 뒤집는 문제인데 처음에 int를 초과하는 input이 주어져서 여러번 틀렸다. 첫번째 시도로는 단순히 각자리수를 추출하여 배열로 만들고 다시 자리수를 늘려가며 곱해주는 방식을 취했다. 결과적으로 속도는 0ms로 빠른 편이였지만 코드의 가독성과 불필요한 부분을 생각하면 좋지 못한 코드였다. class Solution { public: int reverse(int x) { long result = 0; int temp = x; vector intVec; while(temp / 10 != 0){ intVec.push_back(temp%10); temp /= 10; } in..