[자료구조/Data structure]Binary Tree, 이진 트리 트리에 관하여 안녕하세요. Air8입니다. 오늘의 얘기는 Tree에 관하여입니다. 저는 회사에 맨 처음 입사해서 알고리즘을 짤 때 트리를 개념적으로만 알고 있었습니다. 뭐 대충 중심에서 뻗어져나가는 뭐 그런거겠지. 이런 생각을 가지고 있었는데, 어떻게 구현하는 지는 그저 구름 속에서 휘젓고 있었죠. 너무나 간단한 단어 때문에 누구한테 물어볼 필요도 없는 그런 것이 저한테는 트리였습니다. 자료구조 측면에서 본다면 트리는 조금 복잡합니다. 나름 규칙도 있구요. Hierarchical structure(계층 구조)로 표현하는 Abstract Data Type(추상 데이터 형식)인 트리를 알아보겠습니다. 여기서는 Preorder traversal, Inorder traversal, Postorder traver.. [자료구조/Data structure]Traversal, 순회 순회, Traversal 안녕하세요. Air8입니다. 오늘의 얘기는 순회에 관하여입니다. 한글로 순회라고 하면 사실 잘 모르겠습니다. 그냥 회전하는 것 같기도 하구요. 아니면 사실 여러분은 알고 저만 이상한 느낌을 받는 것일 수도 있겠죠. 영어로 보는 것이 조금 더 느낌이 옵니다. Traversal, 방문한다는 개념인데요. 트리에 사용되는 개념이지만 어렵지 않은 내용이니 바로 설명하죠. 순회를 이용한 깊이우선탐색과 너비우선탐색은 아래의 경로에서 설명하겠습니다. 트리 : https://tinyworldwithair.tistory.com/35 전위순회(preorder traversal) - VLR 자신 -> 왼쪽 -> 오른쪽 ( Visit -> Left -> Right ) 중위순회(inorder traver.. [알고리즘/Algorithm]Divide and conquer, 분할 정복 Divide and Conquer, 분할하고 정복 안녕하세요. Air8입니다. 오늘의 얘기는 분할정복입니다. 이공학도라면 많이 들어봤을 단어인데요. 대체적으로 재귀적인 문제를 해결할 때 사용하는 기법입니다. 분할 정복의 접근법은 분할하고 정복한 다음 결합하는 것이라고 할 수 있습니다. 어떤 큰 문제를 여러 개의 작은 문제로 분할하고, 작은 문제는 큰 문제랑 같은 성향을 지녔으나 스케일만 작아진 것입니다. 그 뒤에 작아진 문제를 해결하고 흩어진 작은 문제들을 다 합치는 것으로 볼 수 있습니다. 여기서 여러 정렬 알고리즘 중에 Merge sort를 예로 들겠습니다. 알고리즘 설명 [알고리즘 이름] Merge sort [속성] Big-O notation = O(n * logn) -> 평균 시간 복잡도 재귀, .. [알고리즘/Algorithm]C++ Stack Class, 스택 클래스 스택에 관하여 안녕하세요. Air8입니다. 오늘의 얘기는 Stack에 관하여입니다. Stack을 어디서 들어본 적이 있으신가요? 냉장고에 음료수를 일렬로 넣어두고 마실려고 할 때면 가장 마지막에 넣어놨던 애를 꺼내어 마십니다. 이런게 스택(Stack)입니다. 좀 더 나아가서 핸드폰으로 예를 들어보면 어플을 주구장창 아무렇게나 실행을 해봅니다. 가장 최종적으로 띄워진 화면은 제일 마지막에 실행시킨 어플리케이션이 보이겠죠? 소프트웨어 엔지니어분들에게 말씀드리면 프로그램에서 함수의 호출리스트도 콜스택(Call-Stack)이라고 부릅니다. 프로그램 흐름을 보면 어떤 함수가 호출되고 그 안에서 또 함수가 호출되고 호출되고 호출되고... 함수를 빠져 나올때에는 가장 마지막에 호출된 함수부터 먼저 빠져나갑니다. 그래.. [공사장 로맨스] 6화 - 용기를 주는 겁쟁이 상담사 매운 닭볶음탕 냄새가 가득한 적당한 가게는 제법 시끄러웠다. 자리에 앉아서 옆 사람의 얘기를 들을 수 있는 그런 조그만 가게에서 계란찜과 주먹밥 그리고 닭볶음탕에 치즈추가를 주문했다. 가게는 북적이고 여러 사람들의 이야기가 섞여있었지만 세아씨의 작은 말소리도 들을 수 있었다. 얼굴은 작은데 얼굴에 비해 큰 입, 세아씨가 말할때 실려오는 감정 또한 제대로 느낄 수 있었다. 지금까지 봐온 세아씨는 조근조근하고 침착하지만 오늘은 생각보다 말이 빨랐다. 어쩌면 세아씨는 자기 주변사람들보다 나같은 외지인을 만나서 마음이 편해지는 그런 미묘한 날이 아닐까 생각했다. "계란찜이랑 맥주 나왔는데 세아씨 고민 이제 얘기해줄래요?" "그럼요~ 짠 해요. 우리" 부딪힌 컵조차도 우리 만남에 두근거렸던 것인지 컵 안의 맥주는.. #1 시뮬레이션 구조(Simulation system) 한남동에서 신사역까지 차로 얼마나 걸릴까? 엄청 유명한 베이커리 카페에는 손님이 얼마나 올까? 떡볶이집에 들어와서 계산하고 나가기까지 사장님은 얼마를 팔았을까? 유로트럭2 시뮬레이터 안녕하세요. Air8입니다. 앞에 있는 세가지 질문과 비슷한 생각을 하신 적이 있으십니까? 그게 아니더라도 어떤 계산이 필요한 상상이나 호기심이 생겼던 적이 있으십니까? 그런 호기심 뒤에는 늘 생각해보자...혹은 계산해보자... 얼마쯤 나오겠다! 이렇게 말을 하곤 합니다. 물론 안할 수도 있구요. #2가 끝났을 때는 손으로 시뮬레이션 차트를 그릴 수 있을 정도가 될 겁니다. 시뮬레이션이란 무엇일까요? 상상하는 것처럼 가상의 상황을 만들어 미래를 연출해보는 것일까요? 공대출신이 아닌 혹은 전혀 관련없는 사람이 물어본다면 충분한.. [논문]Berkeley - Above the Clouds (2009) 번역(클라우드 시스템) 프로비저닝 https://ko.wikipedia.org/wiki/%ED%94%84%EB%A1%9C%EB%B9%84%EC%A0%80%EB%8B%9D SaaS https://terms.naver.com/entry.nhn?docId=3580686&cid=59088&categoryId=59096 multiplexing https://terms.naver.com/entry.nhn?docId=796402&cid=42347&categoryId=42347 Amazon EC2(Amazon Elastic Compute Cloud) https://ko.wikipedia.org/wiki/%EC%95%84%EB%A7%88%EC%A1%B4_%EC%9D%BC%EB%9E%98%EC%8A%A4%ED%8B%B1_%EC%BB%B4%ED%.. [알고리즘/Algorithm]Big O notation, 점근 표기법_하 안녕하세요. Air-8입니다. 상편에 이어서 성능분석에 따른 빅오 표기법을 바로 진행하겠습니다. 아래 그림은 순서대로 O(1), O(logn), O(n), O(nlogn), O(n^2)입니다. 참고로 logn의 밑은 크게 중요하지 않습니다. 여기 시간복잡도 5개가 흔히 나오는 경우입니다. n^2까지만해도 그럴 수 있다고 봅니다. 같은 알고리즘이라고 가정할 때 보여지는 시간 복잡도는 그래프만 봐도 확연히 차이가 납니다. 그럼 이제부터 다시 고쳐야 하는 수준의 시간복잡도를 알려드리겠습니다. 순서대로 O(n^3), O(n^k), O(2^n), O(n!)-팩토리얼형 입니다. n^3까지만 가급 고쳤으면 좋겠는 수준이고 n^k나 2^n은 뭔가 잘못됐음을 직감해야됩니다. 심지어 팩토리얼형까지 나온다면 연산수는 말할 .. 이전 1 2 3 4 다음
