Software 썸네일형 리스트형 [자료구조/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)이라고 부릅니다. 프로그램 흐름을 보면 어떤 함수가 호출되고 그 안에서 또 함수가 호출되고 호출되고 호출되고... 함수를 빠져 나올때에는 가장 마지막에 호출된 함수부터 먼저 빠져나갑니다. 그래.. [논문]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은 뭔가 잘못됐음을 직감해야됩니다. 심지어 팩토리얼형까지 나온다면 연산수는 말할 .. [알고리즘/Algorithm]Big O notation, 점근 표기법_상 안녕하세요. Air-8입니다. 소프트웨어 엔지니어로 살아가는, 살아가고 싶은 사람들에게는 알고리즘이 필수가 아닐 수도 있습니다. 그렇지만 알고 있으면 반드시 체계잡힌 소프트웨어 설계가 됩니다. 그래서 소프트웨어 카테고리에서 제일 먼저 글을 써야겠다는 생각이 들었습니다. 본 블로그의 목적은 한 이론에 대한 단편집입니다. 그러나 소프트웨어 카테고리는 메모에 가깝습니다. 글 하나하나 백과사전처럼 아 그거 뭐더라?할때 꺼내보는 느낌으로 글을 쓸 생각입니다. 정정합니다. 다른 카테고리와 같아요. 대수학의 아버지, 콰리즈마라는 위대한 수학자가 있습니다. 콰리즈마가 처음으로 알고리즘(Algorism, Algoritmi)를 말했습니다. 알고리즘은 인도 수학이다. 아라비아 숫자를 이용한 산술이다. 이렇게 얘기했죠. 시간.. 이전 1 다음
