incastle의 콩나물

greedy 알고리즘을 사용하면 좋은 경우 1. 최적 부분 구조 (Optimal Substructure) - 부분 문제를 최적화하는 것이 곧 전체를 최적화하는 것이다. 2. 탐욕적 선택 속성 (Greedy Choice property) - 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택 가장 대표적인 문제 최대한 적은 동전을 사용해서 돈 거슬러 주기. 단 동전은 500, 100, 50, 10원만 있다고 가정한다. 작은 동전으로 큰 동전을 만들 수 없으면 문제는 달라짐 why? - 100원, 70원, 10원짜리 동전이 있다고 가정 - 140원을 거슬러 준다. - greedy하게 선택하면 100원 1개, 10원 4개를 선택 - 하지만 70원 2개를 선택하는 게 가장 최적임 def min_c..

[백준 알고리즘] 2750번 정말 많은 정렬 알고리즘이 존재하고, 이번에 공부한 것은 퀵 정렬 1. list를 input으로 하면 맨 끝의 값을 pivot으로 선언 2. pivot을 기준으로 작으면 왼쪽, 크면 오른쪽으로 쌓기 (단 왼쪽 블럭과 오른쪽 블록이 정렬된 것은 아님) 3. 왼쪽 블록의 가장 오른쪽 값을 새로운 pivot으로 선언 4. 반복하기 2번 항목 상세 2번을 위해서 요소의 위치를 바꿔주는 함수, 반복하는 함수 partition함수 선언 # 두 요소의 위치를 바꿔주는 함수 def swap_elements(my_list, index1, index2): # 코드를 작성하세요. index_value1 = my_list[index1] index_value2 = my_list[index2] my_..

데이터 마이닝 위치 데이터(위도, 경도)를 활용해서 분석 중 찾은 라이브러리 shapely. 폴라곤 내부의 점을 분석하는 용도로 사용해보자. 미션 1. polygon을 형성 2. 특정 좌표가 polygon 영역 안에 있으면 True 밖에 있으면 False # 필요한 라이브러리 설치 !pip3 install --upgrade setuptools !pip3 install shapely from shapely.geometry import Point, Polygon # 경희대 공대 위치를 폴리곤으로 형성 engineer = [(37.245452, 127.079964), (37.247041, 127.079842), (37.247912, 127.081486),(37.245588, 127.081612)] engine..

[백준 알고리즘] 14719번 - 빗물의 총량 계산하는 문제. brute force를 사용. 언어는 python [문제] -2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다. 비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까? [조건] 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다. 따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다. [풀이] 핵심 : 더 큰 건물들 사이에 끼어 있으면 빗물이 담긴다. 현재 인덱스의 왼쪽에서 가장 높은 건..