ㅇㅅㅎ

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 비교 모델 : 비교 모델의 아이디어는 비교를 할 때 어떤 연산을 사용할지 제한하는 것입니다. 모든 입력 항목은 블랙박스입니다.(ADTs) → 블랙박스 : 정확히 무엇인지 모른다는 것을 의미 유일하게 가능한 연산은 비교입니다.(, ≥, =) 시간 비용은 단순히 비교한 횟수로 정의합니다. ✔ 의사 결정 나무(Decision tree) : 어떠한 비교 알고리즘에서도 비교할 수 있는 모든 경우의 수와 비교 결과 및 최종 결론으로 이루어진 트리로 표현할 수 있습니다. 특정한 값 n(문제의 크기)부터 시작하는 것입니다. 의사 결정 나무 알고리즘 내부 노드 이진 결정(비교 모델만 다룸) 단말 노드 찾는 답에 해당 루..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 복습: 이진 탐색 트리(BST) 루트가 있는 이진 트리 각 노드는 다음을 가짐 : [ 키, 왼쪽 포인터, 오른쪽 포인터, 부모 포인터 ] 노드의 높이 = 단말 노드까지의 가장 긴 하향 경로의 길이 ⭐ 노드의 높이는 자식 노드들 높이 중 가장 큰 값에 1을 더함 ⭐ 자식 노드가 없는 부모 노드는 자식 노드 부분 높이를 -1로 설정 각 노드는 자신의 높이를 저장((높이 대신 높이의 차를 저장할 수도 있음) ✔ 균형을 이루는 것의 중요성 이진 탐색 트리는 삽입, 삭제, 최솟값, 최댓값, 다음으로 큰 값 찾기, 다음으로 작은 값 찾기 등을 O(h) 안에 실행할 수 있습니다. 이때 h=트리의 높이(=루트의 높이)..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 활주로 예약 시스템 활주로가 매우 혼잡하고 단 하나뿐인 공항(보스턴 6→1) 향후 착륙을 위한 "예약" 비행기가 착륙하면 대기 중인 사건 집합에서 제거하기 각각의 착륙 요청에는 "요청 예약 시간" t가 명시되어 있음 t로부터 k분 전이나 k분 후에 다른 착륙 예약이 없다면, t를 집합에 추가함. k값은 변할 수 있음 → 그 외의 경우는 에러로 보고, 예약을 잡지 않음 ⁉️ 예시 R은 예약된 착륙 시간을 나타냄: R = (41, 46, 49, 56)과 k=3 착륙 시간 요청 : 44는 허용되지 않음(46∈R) 53 허용 20 허용되지 않음(이미 지난 시간) |R| = n 목표 : 본 시스템을 O(log n..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 우선순위 큐 요소들 집합 S를 구현하는 자료구조입니다. 각 요소들은 key와 관련이 있고 다음 작업들을 지원합니다. insert(S, x) : 요소 x를 집합 S에 삽입 max(S) : 최대 key인 S의 요소를 반환 extract_max(S) : 최대 key인 S의 요소를 반환하고 집합 S에서 x 제거 increase_key(S, x, k) : 요소 x의 key를 새로운 값 k로 증가(k가 현재 값만큼 크다고 가정) ✔ 힙 우선순위 큐의 구현 가능 완전 이진 트리로 시각화된 배열 최대 힙 특성은 노드의 key가 자식 값들의 key보다 크거나 같음(최소 힙도 마찬가지로 동일하게 정의) ⁉️ 트리로서의 힙..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 정렬 ⁉️ 정렬이란? 배열의 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 것입니다. ⁉️ 왜 정렬을 해야 할까? 대표적인 응용 사례 : 전화번호부 정리, 검색, mp3 파일 관리, 스프레드시트 등 정렬되면 쉬워지는 문제들 : 중간값 또는 가장 가까운 쌍 찾기, 이진탐색/통계적 이상치 확인 생소한 응용 사례 : 데이터 압축(정렬로 중복된 부분 검출), 컴퓨터 그래픽(앞에서 뒤로 화면 렌더링) ⁉️ 삽입 정렬 👀 삽입 정렬이란? 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬하는 방법입니다. ⏱ 시간 복잡도 : Θ(n^2) 👀 ..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 알고리즘이란? - 문제 해결을 위한 계산 과정 - 컴퓨터 프로그램의 수학적 추상화 ⭐ 계산 모델은 알고리즘이 할 수 있는 연산과 그 연산에 걸리는 비용(시간, 공간, ...)을 결정합니다. 각각의 연산의 비용을 계산하여 전부 더하면 알고리즘의 총 비용이 됩니다. 이번 강의에서는 2가지 계산 모델을 살펴봅니다. ⭐ 각 연산마다 시간 비용이 있는데 그것들을 모두 더하면 알고리즘의 실행 시간이 됩니다. ✔ 임의 접근 머신(Random Access Machine) - 거대한 배열로 만들어진 임의 접근 기억장치 - O(1) 레지스터(각 1개의 워드) - O(1) 시간 안에 할 수 있는 일 - 레지스터에 있는 워드..

BoostCourse의 "[MIT]파이썬을 이용한 알고리즘의 이해" 강의 내용을 정리한 글입니다. ✔ 극댓값이란? 주위의 모든 값들이 현재의 값보다 작은 값입니다. 즉, 주위의 모든 값보다 현재의 값이 큰 값입니다. 극댓값을 최댓값으로 생각할 수도 있지만, 극댓값이 항상 최댓값인 건 아니지만 최댓값은 항상 극댓값입니다. 이번 강의에서는 1차원과 2차원으로 나누어서 각 차원에서 극댓값을 구합니다. 그리고 그 과정에서 사용한 알고리즘과 사용한 알고리즘의 시간복잡도에 대해서 알아봅니다. 시간복잡도와 배열에 대해서 미리 알고 계시면 이해하기 편합니다. ✔ 1차원의 경우 위와 같은 알파벳 1차원의 배열이 존재한다고 할 때 b≥a이고 b≥c이면 2번 위치가 극댓값입니다. 혹은 i≥h이면 9번 위치가 극댓값입니다. ..

안녕하세요, 오랜만에 친구를 만나게 되어 친구가 추천한 브런치 카페 '리틀오스'에 다녀왔습니다. 이번 글은 '리틀오스'에서 먹어 본 음식에 대한 후기를 작성해보도록 하겠습니다. '리틀오스'는 금련산역 1번 출구에서 약 4분 정도 걸으면 쉽게 찾을 수 있는 곳에 위치해있습니다. 주중 점심시간에 방문을 했었는데 웨이팅 없이 들어갔습니다. 하지만 저희 일행을 마지막으로 웨이팅이 생겼기 때문에 테이블링으로 미리 예약하고 방문하시면 좋을 것 같습니다. '리틀오스'의 전체적으로 식물들을 많이 두었고 내부에 테이블 4개 야외 공간에도 테이블을 2개 더 배치해 둬서 공간 활용을 높였습니다. 저희는 내부에는 자리가 없어서 야외 테이블에 앉았습니다. * 위의 사진들은 전부 야외 사진들입니다. 건물의 내부는 사진 촬영을 하..

안녕하세요, 이번 글도 아무런 생각 없이 친구 따라갔다가 3가지 홍차를 경험 한 홍차 카페 '마리봉' 후기를 작성해보도록 하겠습니다. 이른 저녁 후 커피와 차를 좋아하는 친구의 추천으로 마리봉에 방문하게 되었습니다. 마리봉은 부산에서 유명한 홍차 카페라고 했는데 양산에도 새로 생겼다고 친구가 알려줬습니다. 주차장에서 건물을 바라보았을 때 건물 내부에서부터 흘러나오는 컨셉에 조금 당황스러웠습니다. 카페에 들어가자마자 가게 주인분께서 저희를 친절히 맞이해 주셨습니다. 이른 저녁 식사 후 방문한 거라 그런지 손님은 저희밖에 없었습니다. 내부는 유럽풍 엔틱 인테리어로 '여기가 정말 한국인가'라는 느낌이 올 때, 천장의 시스템 에어컨을 보고 '여기가 한국이구나'라며 정신을 차렸습니다. 저희는 1층 따로 분리된 공..

안녕하세요, 이번 글은 아무런 생각 없이 친구 따라갔다가 맛에 홀딱 반하고 온 '진부령황태구이' 의 황태구이 후기를 작성해보도록 하겠습니다.( 내돈내산이라기엔 친구가 산 밥이라... ) 오랜만에 만난 친구가 맛있는 밥을 사준다고 하여 11시 30분쯤 식당에 방문했습니다. 아무래도 자가용이 없다면 방문하기 불편한 위치에 있기 때문인지 주차장은 넓은 편이었습니다. 주중 조금 이른 점심시간이었지만, 식당 내에는 손님들이 좀 계셨고 예약석도 많았습니다. 만약 중요한 자리라면 미리 예약을 하고 가시는 것을 추천드립니다. 다른 분들께서는 주로 황태무침정식을 많이 드시는 것 같았지만, 저희는 친구 추천으로 황태구이와 밥을 주문하였습니다. 밥은 별도로 주문해야 하니 참고하시길 바랍니다. 음식의 경우 매우 정갈하게 상을..