본문 바로가기

전체 글

 (132)
아띠제 발로나 쇼콜라 크런치 대존맛 국내 프랜차이즈 카페에서 파는 케익 중 내 기준 1위 케익 추천.. 바로바로 발로나 쇼콜라 크런치 홀은 41,000원 조각은 7,500원이다. 가격이 굉장히 사악한데 엄청 맛있다. 고급진 초코무스+초코 소스에 초코 쉬폰은 촉촉하고 크런치가 콕콕콕 꽤 풍성하게 박혀있어 씹히는 맛이 예술이다.✨ 눈깜짝하면 절반이 사라져있음. 커피나 우유랑 먹으면 대존맛.. 자허토르테랑 착각하면 안됨. 누구든 이 글을 봤다면 꼭 드셔보세요✨💫🧚‍♀️
decision problem 과 optimization problem 의 관계 (feat. np) optimization problem 에 대해 배우는 최적화 수업과 decision problem 의 다양한 구분들 (p, np)에 대해 배우는 알고리즘 수업을 동시에 듣다가 optimization 문제를 decision problem 으로 바꿀 수 있다는 사실을 알게되었다. 예를들어 traveling salesperson problem (TSP) 문제를 최적화 문제로 말한다면 우리는 모든 도시를 방문하는 최소 경로를 구하고 싶다고 할 수 있다. 이걸 decision problem 으로 바꾸면 어떨까? 참고로 decision problem 은 YES/NO로 답을 내릴 수 있는 문제를 의미한다. 모든 도시를 방문하면서 최대 k거리를 갖는 경로가 있을까? 로 바꿀 수 있다. 만약 decision proble..
Duality 변환 공식 암기하지말고 이해하기 Duality 변환 공식 선형계획법에서 Duality 에 대해 배우다보면 아래와 같은 dual 변환 공식을 종종 접한다. 다음과 같이 규칙 기반으로 표를 외우는 방법도 있다. 한쪽 문제의 equality constraints는 다른쪽 문제의 free variables 과 대응된다. minimize 문제의 constrainst 와 그의 dual 인 maximize 문제의 variables 의 부호는 같다. minimize 문제의 variables 과 그의 dual 인 maximize 문제의 contraints 부호는 다르다. 하지만 왜 꼭 이렇게 되어야만 하는것인지 규칙에 숨겨진 원리를 당위적으로 이해하고 싶은 사람이라면 아래 예제를 살펴보자. 다음 LP 예제를 살펴보자 min⁡x1+3x2\min x_1+..
Lagrange Multiplier 로 유도해보는 dual 공식을 써보지 않고 Lagrange Multiplier Method 에 대한 선행 지식만 가지고 있다고 가정한 채 dual 을 유도해볼 것이다. 과정을 한번 따라 써보면 dual에 대해 다른 관점으로 이해할 수 있을 것이다. 아래는 LP minimization 문제의 standard form 이다. min⁡c′x\min c'xminc′x s.t. Ax=bAx = bAx=b x≥0x \geq 0x≥0 이러한 LP 문제를 보면 가장 먼저 궁금해져야하는 것이 각 벡터와 행렬의 차원이다. c, x 는 n 차원의 벡터이며 A는 m x n 행렬, b는 m 차원의 벡터이다. c와 x 벡터를 내적해주기 위해 그냥 c 벡터가 아니라 c′c'c′를 사용한다. 참고로 c′c'c′는 c벡터를 transpose 한 cTc^Tc..
simplex method와 cycling 극복법 Simplex method 는 유한한 시간 안에 끝날까? 수학식으로 증명하는 것 말고 수식은 최대한 줄이고 말로 풀어 직관적으로 설명해보려한다. 이 글은 기본적으로 simplex method가 무엇인지 알고 있어야 이해할 수 있다. Simplex method는 유한한 시간 안에 해를 구해내는 것을 보장할까? 결론부터 말하자면 그렇다. non-degeneracy 를 가정했을 때 non-degeneracy 를 가정하면 쉽다. Simple method는 항상 Basic feasible solution (BFS) 이 감소하는 방향으로만 움직이니 같은 basis 로 돌아올 수가 없다. 우리는 유한한 basis 를 가지고 있으니 유한한 시간 안에 알고리즘이 끝난다. degeneracy 가 있을 때- cycling ..
[선형대수] 그림으로 알아보는 Basic feasible solution 사전 지식active 하다는 것? 만일 어떤 벡터가 제약식의 equality 를 만족하면 그 제약식은 active 혹은 binding 되었다고 한다. 직관적으로 크거나 같다/ 작거나 같다 등의 조건이 있을때 그 조건에 딱 걸쳐있는 벡터를 상상하면 쉽다. Basic solution 이란? 어떤 벡터가 basic solution 이 될 조건은? (차원이 n 이라고 하자)(1) active contraints 중 선형 독립이 n개 존재해야 함. (n은 차원의 수)(2) equality contrains 은 무조건 active 해야함.첫번째 조건은 직관적으로 이해가 된다. solution을 어떤 한 점이라고 생각한다면 2차원의 공간에서 한 점을 특정하기위해서는 2개의 선분이 필요할테고 3차원의 공간에서 한 점을..
[python] 내 코드의 연산시간을 확인하고 싶을때 import time start = time.time() #write your code end = time.time() print('total computation time: ' + str(end - start)) 내가 짠 코드의 시간 효율이 어느정도 되는지를 알기 위해서 time 라이브러리를 사용한다. 종종 너무 오랜 시간 코드가 돌아가는 경우 이것을 효율적으로 만들기위해 여러개의 코드 블록으로 나누어 각 블록의 연산시간을 체크해봐야하는데 위의 코드로 간단하게 가능하다.
파리크라상 커피 월간 구독제 요즘 코로나때매 카페에서 공부는 못하고 테이크아웃을 해오느라 싸고 맛있는 커피 테이크아웃 전문점을 선호하게 되었다. 근데 집주변에 없어서 매번 엄청 걸어야했다. 그러던 중 집에서 가까운 파리크라상에 기가 막힌게 생겼다!커피 월간 혜택권!✨ 6만원을 내면 커피를 한달 내내 마실 수 있다. 모든 커피종류 이용 가능이라 내가 좋아하는 바닐라라떼 (5000원)로 맨날 먹는다 치면 최대 60% 할인이다 ॱଳ͘ 구독제 서비스가 이제 요식업종에도 도입된게 흥미롭다. 근데 아직 시행된지 얼마 안됐는지 좀 엉성한 부분들은 있다. 일단 이렇게 실물 쿠폰으로 발행한것도 좀 엉성하고 (잃어버리면 어쩔건데!) 타인에게 양도가 불가능하다고는 하는데 본인 확인 절차도 딱히 없다. 무엇보다 저기에 분명히 구매한 날부터 사용가능하다고..

티스토리툴바