본문 바로가기
반응형

전체 글340

[기술의역사] 파이썬(Python) 파이썬(Python) "인생은 너무짧다. 그래서 파이썬이 필요하다."파이썬은 짧은 코드에서 나오는 효율성 뿐만아니라 들여쓰기로 만들어지는 자동 정렬,어떤 분야든 가리지 않고 닥치는대로 사용할 수있는 범용성 등 많은 무기를 가지고 있다.이 때문인지는 몰라도 2017년 6월 기준 프로그래밍 점유율 수준은 당당하게 4위를 차지하고 있다. (파이썬의 창시자 - 귀도 반 로썸) 파이썬이 최근에 주목받고 있다고 생각할지 모르겠지만 발표시기는 1991년,웹 서비스가 일반인들에게 널리 상용화되기 전에 나온 언어이다.언어를 만든이는 귀도 반 로썸(Guido van Rossom)으로 1989년 크리스마스 주에 연구실이 닫혀있어 심심한 김에 만들었다고 한다.리누스나 귀도 둘다 심심한 김에 걸작을 만들었다는데 있어서, 위대한.. 2017. 6. 9.
[알고리즘] 동적 계획법(Dynamic Programming) - 5 동적 계획법(Dynamic Programming) - 5 이번 시간에는 Longest Common Subsequence를 알아보자Longest Common Subsequence는 줄여서 LCS라고 부르는데, 약어로 부르는것은 그만큼 유명하다는 뜻이다.입력으로 2개의 문자열이 주어지며, bcdb는 문자열 의 subsequence이다.또한 는 문자열 와 의 common subsequence(공통 부분 문자열)이다. 우리가 고려해야할 부분은 LCS인데, 입력으로 2개의 문자열이 주어졌을때, common subsequence중에서 가장 긴것을 찾으면 된다.예를 들어, 는 와 의 LCS가 되는 것이다. 그렇다면 위의 그림에서 x라는 문자열과 y라는 문자열이 입력으로 주어진 문자열이며,z가 우리가 원하는 최적해라고.. 2017. 6. 9.
[알고리즘] 동적 계획법(Dynamic Programming) - 4 동적 계획법(Dynamic Programming) - 4 이번에는 동적 계획법 알고리즘에서 가장 유명한 알고리즘인 Matrix chain multiple을 알아보자이것은 말그대로 두 행렬을 곱하는 알고리즘이다.위의 코드는 pxq인 A 행렬과 qxr인 B 행렬의 곱하기 이다.3개의 반복문으로 돌아가며 곱셈 연산의 횟수는 pqr번이고 결과값은 C에 저장된다. 그러나 우리가 지금 하려는 것은 Matrix chain이다. ABCD의 행렬을 차례로 곱해야 하는 것이다.행렬은 결합 법칙이 성립하므로 계산 순서에 따라서 곱셉 연산의 횟수가 달라진다.그럼 n개의 행렬을 곱할 때 최적의 순서는 무엇일까 이 문제를 동적 계획법으로 접근할때 어떻게 풀어야 하는지를 생각해보면,subproblem으로 나눠서 optimal su.. 2017. 6. 9.
[알고리즘] 동적 계획법(Dynamic Programming) - 3 동적 계획법(Dynamic Programming) - 3 동적 계획법이라는 것은 순환식과 뗄레야 뗄수 없는 관계이다. 다시 말해 순환식을 효과적으로 푸는 테크닉이라고 할 수 있다.따라서 동적 계획법은 다음과 같은 특징을 가지고 있다. 1. 일반적으로 최적화문제 혹은 카운팅 문제에 적용된다.2. 주어진 문제에 대한 순환식을 정의한다.3. 순환식으로 Memoization 또는 Bottom up 으로 푼다. 동적계획법은 subproblem을 풀어서 원래 문제를 푸는 방식이다. 그런 의미에서 분할 정복법과 공통점이 있다.분할 정복법에서는 분할된 문제들이 서로 disjoint하지만 동적계획법에서는 그렇지 않다.즉 서로 overlapping하는 subproblem들을 해결함으로써 원래의 문제를 해결하는 것이다. 분.. 2017. 6. 9.
[책] 멋진 신세계(Brave New World) 멋진 신세계(Brave New World) 원시 시대부터 4차 산업 혁명까지, 인류는 종족 보전과 발전을 위해 부단히 노력해 왔다. 인류의 기원에서 부터 제 1차 산업혁명까지, 다시 1차 산업혁명에서 현재까지를 비교해 보았을 때, 후자의 인구 변화가 더욱 급증한 것은 과학과 의료기술의 발전에 따른 따른 안정화와 수명 연장으로 인한 결과 라고 할 수 있다. 이처럼 과학의 발전은 시대가 흘러감에 따라 가속도가 점점 빨라지고 있다. 이러한 문명 발전의 시대 속에서 우리가 꿈꾸던 투명인간이나 복제 인간, 순간 이동 등의 기술은 더 이상 공상 과학 영화에서만 다루어지는 내용이 아닐수도 있다. 물론, 과학이 어떤 방향으로 발전하느냐에 따라 우리가 우려하는 핵전쟁 등의 디스토피아적 시나리오로 발전할수도 있는 것이고,.. 2017. 6. 9.
[알고리즘] 동적 계획법(Dynamic Programming) - 2 동적 계획법(Dynamic Programming) - 2 지난 시간에 이어서 기본적인 동적 계획법의 예를 알아보자위의 그림은 정수들이 저장된 nXn의 좌상단에서 우 하단 까지 이동하는 문제이다.단 이때, 오른쪽이나 하단으로만 이동이 가능하다.또한 이렇게 이동하면서 지나간 모든 셀들에 저장된 값들의 합이 최소가 되도록 해야한다. 사실 이 문제는 그래프의 다익스트라 알고리즘으로 얼마든지 풀수 있지만 여기에서는 동적 계획법으로 풀어보도록하자앞선 포스팅에서는 이항계수와 피보나치를 구하는 문제를 보았는데, 거기에서는 순환식 자체가 주어졌다.그러나 실제로, 대부분의 경우에는 주어진 순환식을 푼다기 보다는 문제가 주어졌을 때, 문제를 풀기위한순환식을 세우고 이것을 계산하는 과정 전체를 동적 계획법이라고 한다.다시말해.. 2017. 6. 9.
[알고리즘] 동적 계획법(Dynamic Programming) - 1 동적 계획법(Dynamic Programming) 우리가 전에 피보나치 수를 계산하기 위해 재귀 함수를 사용했었다.이는 같은 연산이 반복되기 때문이다. 그러나 이 함수의 진행 과정을 살펴보면 중복이 심하다는 것을 알수 있다. 위의 그림에서 보면 fib(2)가 여러번 반복되며 오버헤드가 증가함으로 결국 비효율적인 코드가 된다. 따라서 이러한 중복을 제거 하기 위해서 메모이제이션(Memoization)이라는 테크닉을 사용한다.이는 사전에는 나오지 않는 프로그래밍 테크닉이며, 계산된 값을 버리지 말고 저장한다는 뜻이다예를 들어 위의 그림에서 계산이 된 fib(2) 값을 저장해 놓고 있다가, 필요한 경우 계산없이 호출하게 된다.이렇게 저장되는 배열을 '캐시'라고 하며, 중간에 저장하는 걸 '캐싱한다'라고 부른다.. 2017. 6. 6.
[알고리즘] 최단경로(Shortest Path Problem) - 2 최단경로(Shortest Path Problem) - 2 위의 그림은 Bellman-ford 알고리즘의 예이다.첫번째 라운드에서 모든 엣지들에 대해서 relax 한다.relax연산이 끝나면 초기 시작점과 인접한 엣지들의 ∂값이 세팅된다.이렇게 순차작으로 relax 연산을 실행한다.위 그림은 한가지 실행 가능한 예이며, 어떠한 엣지를 선택하느냐에 따라서 다른 순서를 가진다. 이 Bellman-ford는 시간 복잡도에서 그리 좋은 알고리즘은 아니다.위의 그림은 왜 Bellman-ford의 시간 복잡도가 비효율적인지 알려준다.Bellman-ford 의 최악의 상황이 표현되었고, d[v]가 한번 갱신될때 마다 우측의 노드들의 값이 바뀐다.이는 불필요한 계산이 증가한다는 것이고, 그에따른 오버 헤드도 증가한다. .. 2017. 6. 3.
[Backjoon] 11653번 문제 - 소인수분해 정수 N이 주어졌을 때, 소인수분해하는 프로그램을 작성하시오. 풀이 우선 2개의 반복문을 사용한다.외부에 while은 입력 받은 수가 나눗셈 연산을 거듭하면서 마지막에 1로 수렴하는 것을 판단한다.for는 나눠지는 수를 찾기 위해 i가 2부터 증가하며 만약 입력 받은 값이 i로 나눠진다면 나눈후 i값을 출력한다. 123456789101112131415161718192021import java.util.Scanner; /** * Created by homr on 2017. 6. 3.. */public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int num = sc.nextInt(); wh.. 2017. 6. 3.
반응형

티스토리툴바