본문 바로가기

전체 글

[NetworkFlow] 네트워크 유량과 포드 풀커슨 알고리즘 이번 글에서는 네트워크 유량 문제 (네트워크 플로우)와 포드 풀커슨 알고리즘에 대해 알아보자. 네트워크 유량 문제 (Network Flow Problem) 원래의 그래프는 간선을 거리, 비용으로 생각했다면, 유량 네트워크 (Flow Network)에서는 단방향 그래프에서 간선의 가중치를 최대로 흐를 수 있는 용량(capacity)과 실제로 흐르는 유량(flow)으로 생각한다. 이게 무슨 말이냐 하면 A에서 B로 가중치가 10이 존재한다면, A에서 B로 흐를 수 있는 최대 물의 양이 10이라고 해석할 수 있다. (실제로 물이 얼마나 흐르는지는 우리가 얼마나 흘려보내냐에 따라 다르다.) 이제 유량 네트워크가 뭔지 대충 느낌을 알았는데, 그래서 네트워크 유량이 뭐냐? 하면 네트워크 유량은 이 유량 네트워크에서.. 더보기
동적 프로그래밍(Dynamic Programming)의 개념 DP 문제를 풀다가 DP에 대한 이해가 부족한 것 같아서 글로 정리해본다. Dynamic Programming 동적 프로그래밍이란 큰 문제를 작은 문제로 분할하여 문제를 푸는 방법이다. 이 용어는 리처드 벨만이 처음 사용했는데, 이름에 큰 의미는 없다. 그냥 멋있어서 사용했다. 아무튼간에 이 방법을 사용하는 이유는, 큰 문제가 작은 문제를 포함하는 구조를 갖고 있을 때, 작은 문제를 알면 큰 문제의 정답을 빠르게 구할 수 있다는 점이다. 위의 코드를 한 번 읽어보자. 1 = 1 2 = 2 + 1 3 = 3 + 2 + 1 ... 100 = 100 + 99 + 98 + ... + 3 + 2 + 1 이런 식으로 구하는데, 잘 보면 3 = 3 + 2 + 1을 구할 때, 여기서 2 + 1은 sum(2)와 동일하므.. 더보기
DP 문제가 잘 안 풀린다. 요즘 DP 문제가 고민인데, DP문제 카테고리의 문제를 봐도 왜 DP인지 잘 모르겠고 (왜 부분 문제가 겹치는지 잘 이해가 되지 않고), 계속 전에 풀었던 문제랑 비슷비슷한 문제만 풀린다. 생각해보니 알고리즘 강의 중에서 DP 강의가 길어서 중간에 하차를 했다. 내일부터는 강의 정주행으로 가자! 더보기
[백준] 9251번 LCS (Longest Common Subsequence) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제를 풀기 전에 알아야 할 개념 : Dynamic Programming LCS란? LCS란 두 문자열 str1과 str2가 있다고 할 때, 공통된(Common) 부분 수열(Substring) 중, 가장 긴 것(Longest)을 의미한다. 여기서 Subsequence의 개념을 명확히 할 필요가 있는데, 원래 문자열의 글자를 몇 개 선택해서 원래 문자.. 더보기
[딥러닝 노트 1.] 딥러닝이란 무엇인가? 학습 목표 :- 인공지능, 머신러닝, 딥러닝의 관계를 파악할 수 있다.- 딥러닝의 장단점, 활용 분야를 안다. 1.1 인공지능, 머신러닝, 딥러닝 인공지능, 머신러닝, 딥러닝 모두 근 3년간 (주관적인 생각이다.) 핫한 키워드다. 특히 딥마인드의 알파고가 이세돌 9단을 이겼다는 것을 기점으로 국내에도 인공지능 열풍이 불기 시작했다고 생각한다. 그런데 이 세 단어에 관심 있는 사람은 많지만 정확하게 아는 사람은 별로 못 본것 같다. 차이가 뭘까? 하나씩 살펴보자. 그림 1-1은 구글에 인공지능의 정의를 검색한 결과이다.인공지능은 아주 포괄적인 의미로, 머신러닝 딥러닝 할 것 없이 사람이 기계를 이용해 지능을 만들면 다 인공지능이다.(지능의 정의가 좀 애매하긴 하지만 여기선 논외로 한다.) 머신 러닝(Mac.. 더보기
인공지능 참고 링크 딥러닝 로드맵 : https://tensorflow.blog/tag/deep-learning-pepers-reading-roadmap/ 머신러닝 공부 블로그 : - http://pythonkim.tistory.com/8?category=573319 MNIST Database : - http://yann.lecun.com/exdb/mnist/ CNN(합성곱 신경망, Convolutional Neural Network)을 잘 설명한 링크 : https://t-robotics.blogspot.com/2016/05/convolutional-neural-network_31.html#.W6BoaOgza01 tf.nn.max_pool 함수의 ksize 파라미터 설명 :- https://deephaja.blogspot.. 더보기
운영체제 연습문제 : 4. 메모리 관리 다음 문제는 '리눅스 커널 내부구조(백승재, 최종무)' 책의 연습문제 풀이입니다.(제가 푼거라 틀릴 수도 있고, 풀지 못한 문제도 있습니다.) 1. heap을 사용하는 프로그램을 작성해보자. stack을 사용하는 프로그램도 작성해보자. 어려울 경우 3장의 그림 3.2를 참고하라. heap : #include int main(void) { int *numArray = (int*) malloc(sizeof(int) * 10);free(numArray);return 0; } stack : int main(void) { int i = 10; // 지역변수의 값은 스택에 저장되므로 스택에 10을 저장하게 된다. return 0;} 2. 함수가 호출될 때는 스택에 어떤 값을 저장할까? 이때 스택에 저장되는 값을 변.. 더보기
사람다운 인공지능을 만들기 위해 해결해야 할 질문들 보호되어 있는 글입니다. 더보기