티스토리

youngmin.log
검색하기

블로그 홈

youngmin.log

youngminieo1005.tistory.com/m

By. Be SW engineer

구독자
6
방명록 방문하기
공지 Hello 모두보기

주요 글 목록

  • 탐욕법(Greedy Method) 📢 탐욕법 탐욕법(Greedy Method) : 일반적인 알고리즘 설계 기법 가운데 하나 👉 구성(Configuration) : 다양한 선택, 모음, 또는 찾아야 할 값들 👉 목표(Objective) : 구성에 할당된 점수가 존재하며, 이를 최대화 또는 최소화해야 하는 상황 탐욕적 선택 속성(Greedy-Choice Property)을 가진 문제에 적용할 경우 가장 잘 맞는다. 👉 출발 구성으로부터 시작하여 지속적인 지역적 향상을 통해, 전체 최적해를 항상 찾을 수 있다. 예시 👉 잔돈 거스르기 👉 부분 배낭 문제 👉 최소신장트리 📢 잔돈 거스르기 문제 구성 👉 거슬야 할 금액 정보 👉 종류 여러 개의 동전들 목표 👉 동전 수를 최소화 탐욕해 👉 가능하 항상 제일 큰 동전으로 거슬러준다. 만약, 이 문제.. 공감수 0 댓글수 0 2020. 12. 15.
  • 최단경로(Shortest Path) 📢 최단경로 최단경로 문제(Shortest Path Problem) 👉가중그래프와 두 개의 정점 u와 v가 주어졌을 때, u와 v사이의 무게의 합이 최소인 경로를 구하는 문제 최단경로길이 : 간선들의 무게 합 응용분야 👉 인터넷 패킷 라우팅, 항공편 예약, 자동차 네비게이션 등등 📢 최단경로 속성 속성 1 👉 최단경로 부분경로(Subpath)역시 최단경로이다. 속성 2 👉 출발정점으로부터 다른 모든 정점에 이르는 최단경로들의 트리가 존재한다. = 단일점 최단경로(Single-Source Shortest Paths) 최단경로는 최소신장트리와 달리 👉 무방향뿐만 아니라 방향그래프에도 정의된다. 👉 그래프에 음의 무게를 가진 싸이클이 있거나, 무방향그래프에 음의 무게를 가진 간선이 있으면 부정한다. 👉 최단경.. 공감수 1 댓글수 0 2020. 12. 15.
  • 최소신장트리(Minimum Spanning Tree) 📢 가중그래프 가중그래프(Weighted Graph) : 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프 무게가 될 수 있는 것들은 거리,비용,시간 등 다양하다. 📢 최소신장트리 신장 부그래프(Spanning Subgraph) : 그래프 G의 모든 정점들을 포함하는 부그래프 신장트리(Spanning Tree) : (자유)트리인 신장 부그래프 최소신장트리(MST, Minimum Spanning Tree) : 가중그래프의 총 간선 무게가 최소인 신장트리 응용분야 👉 교통망, 통신망 등등 최소신장트리 속성 👉 1. 싸이클속성 👉 2. 분할 속성 이 두개의 속성은 알고리즘의 정확성 검증에 이용한다. 📢 싸이클 속성 싸이클 속성 👉 T를 가중그래프 G의 최소신장트리라 가정하자. 👉 e를 T에 존재하.. 공감수 1 댓글수 0 2020. 12. 15.
  • 동적프로그래밍(Dynamic Programming) 📢 동적프로그래밍 동적프로래밍(DP, Dynamic Programming) : 알고리즘 설계의 일반적 기법 중 하나 언뜻 보기에 많은 시간( 심지어 지수 시간 )이 소요될 것 같은 문제에 주로 적용한다. 적용의 조건은 : 👉 부문제 단순성(Simple Subproblems) : 부문제들이 j,k,l,m 등과 같은 몇 개의 변수로 정의 될 수 있는 경우 👉 부문제 최적성(Optimality Subproblems) : 전체 최적치가 최적의 부문제들에 의해 정의될 수 있는 경우 👉 부문제 중복성(Overlap Subproblems) : 부문제들이 독립적이 아니라 상호 겹쳐질 경우 ( 즉, 상향식으로 구축 ) 대표적 예시 👉 피보나치 수(Fibonacci progression)에서 N-번째 수 찾기 👉 그래프의.. 공감수 1 댓글수 0 2020. 12. 14.
  • 방향 그래프(Directed graph) 📢 방향그래프 방향그래프(Digraph) : 모든 간선이 방향간선인 그래프 📢 방향그래프 속성 모든 간선이 한 방향으로 진행하는 그래프 G = (V,E)에서 👉 간선(a,b)는 a -> b 로는 가지만, b -> a 로는 가지 않는다. 그래프 G가 단순하다면 ( 즉, 병렬간선이나, 루프가 없으면 ) 👉 M 공감수 2 댓글수 0 2020. 12. 14.
  • 그래프 순회(Graph Traversal) 📢 그래프순회 순회(Traversal) : 모든 정점과 간선을 검사함으로써 그래프를 탐험하는 체계적인 절차 주요전략 👉 깊이우선탐색(DFS, Depth First Search) 👉 너비우선탐색(BFS, Breadth First Search) 📢 깊이우선탐색(DFS) 깊이우선탐색(DFS, Depth First Search) : 그래프를 순회하기 위한 일반적 기법 중 하나. 그래프 G에 대한 DFS순회로 가능한 것들 👉 G의 모든 정점과 간선을 방문 👉 G가 연결그래프인지 결정 👉 G의 연결요소들을 계산 👉 G의 신장숲을 계산 N개의 정점과 M개의 간선을 가진 그래프에 대한 DFS는 O(N + M)시간 소요 DFS를 확장하면 해결 가능한 그래프 문제들 👉 두 개의 주어진 정점 사이의 경로를 찾아 보기 👉 그.. 공감수 1 댓글수 0 2020. 12. 14.
  • 그래프(Graph) 📢 그래프(Graph) 그래프(Graph) : (V,E)쌍, 여기서 V,E는 각각 👉 V : 정점(Vertex)이라 불리는 노드의 집합 👉 E : 간선(Edge)이라 불리는 정점쌍들의 집합 정점(V)과 간선(E)은 원소, 즉 정보를 저장한다. 📢 간선에 따른 그래프 유형 방향간선(Directed edgd) 👉 정점들의 순서쌍 (u,v) 👉 u : 시점(Origin) 👉 v : 종점(Destination) 방향그래프(Directed Graph) 👉 모든 간선이 방향간선인 그래프 무방향간선(Undirected edge) 👉 정점들의 무순쌍 (u,v) 무방향그래프(Undirected Graph) 👉 무방향간선으로 이루어진 그래프 그래프 응용분야 👉 교통망 : 고속도로망, 항공노선망 👉 컴퓨터 네트워크 : LA.. 공감수 2 댓글수 0 2020. 12. 13.
  • 해시테이블(Hash Table) 📢 해시테이블(Hash Table) (키-주소) 매핑에 의해 구현된 사전 ADT 👉 예 : 컴파일러의 심볼 테이블, 환경변수들의 레지스토리 해시테이블 = 버켓 배열 + 해시함수 👉 항목들의 키를 주소(즉, 배열첨자)로 매핑함으로서 1차원 배열에 사전 항목들을 저장한다. 성능 👉 탐색,삽입,삭제 : 최악의 경우 O(N), 그러나 기대시간 O(1) 📢 버켓배열(Bucket Array) 키가 유일한 정수며 [0...M-1] 범위에 잘 분포되어 있다면, 해시테이블에서의 탐색, 삽입, 삭제에 O(1) 소요 두 가지 중요한 결함 👉 O(N) 공간을 사용하므로, M이 N에 비해 매우 크면, 공간 낭비 👉 키들이 [0...M-1] 범위 내의 유일한 정수여야 하지만, 이는 종종 비현실적 설계 목표 👉 그러므로 해시테이블.. 공감수 1 댓글수 0 2020. 12. 13.
  • 이진탐색트리(Binary Search Tree) 📢 이진탐색트리(Binary Search Tree) 내부노드에 (키,원소)쌍을 저장하며 다음의 성질을 만족하는 이진트리 성질 트리노드 u,v,w가 있을때, u와 w가 각각 v의 왼쪽과 오른쪽 부트리에 존재할 때 Key(u) < Key(v) < Key(w) 성립 전제 : 적정이진트리로 구현 [DS] 이진 트리 - binary tree (개념 및 이진 트리의 종류) 트리 Tree 는 원소들을 계층적으로 저장하는 비선형 non-linear 자료구조입니다. * 위 그림의 나무를 뒤집어 둔 것과 비슷하게 생겼습니다. 최상의 원소 루트 root를 제외한 각각의 원소는 하나의 부 sean-ma.tistory.com 이진탐색트리를 중위순회(Inorder Traversal)하면 키가 증가하는 순서로 방문한다. [자료구조.. 공감수 1 댓글수 0 2020. 12. 12.
  • 사전(Dictionary) 📢 정의 사전은 탐색 가능한 형태의 (키,원소)쌍 항목들의 모음을 모델링 한 것이다. 사전에 관한 주요 작업 1. 탐색(Searching) 2. 삽입(Inserting) 3. 삭제(Deleting) 사전에는 두 종류의 사전 존재한다. 1. 무순사전 ADT (Ex. "가계부") 👉 "순서가 없다" 2. 순서사전 ADT (Ex. "출석부", "백과사전") 👉 "학번 or 자음순,모음순" 등의 정렬된 순서가 있다. 사전 응용에는 두 가지 1. 직접 응용 👉 "연락처 목록", "신용카드 사용승인", "인터넷주소 매핑" 2. 간접 응용 👉 "알고리즘 수행을 위한 보조 데이터구조", "다른 데이터구조를 구성하는 요소" 📢 탐색 비공식적 : 탐색(Search)은 데이터 집단으로부터 특정한 정보를 추출함을 말한다. 공.. 공감수 1 댓글수 0 2020. 12. 12.
  • 힙과 힙정렬 ( Heap & Heap Sort ) [ 목차 ] 힙이란 무엇인가 ? 힙을 이용한 우선순위 큐 구현 힙 구현과 성능 힙 정렬 제자리 힙 정렬 상향식 힙 생성 힙이란 무엇인가 ? 힙(Heap) : 내부노드에 키를 저장하며 다음 두 가지 속성을 만족하는 이진트리 힙 순서(Heap-order) : 루트를 제외한 모든 내부노드 v에 대해 Key(v) >= Key(parent(v)) => (최소힙 기준) Key(v) (최대힙 기준) 완전이진트리(Complete binary tree) : 힙의 높이가 h라고 하면 => i = 0, ... , h - 1에 대해 깊이 i인 노드가 2^i개 존재 => 깊이 h - 1에서, 내부노드들은 외부노드들의 왼쪽에 존재 힙의 마지막(Last Node) : 깊이 h - 1의 가장 오른쪽 내부노드 힙의 높이 정리 : n개.. 공감수 2 댓글수 0 2020. 9. 26.
  • 우선순위 큐(Priority queue) [ 목차 ] 우선순위 큐 ADT 우선순위 큐를 이용한 정렬 제자리 정렬 선택 정렬과 삽입 정렬 비교 우선순위 큐 ADT 우선순위 큐를 이용한 정렬 제자리 정렬 선택 정렬과 삽입 정렬 비교 우선순위 큐란 무엇일까 ? 우선순위 큐는 각 항목에 대해 ( 키, 원소 ) 쌍으로 저장되는 자료구조다. 일반적인 큐와 달리 들어오는 순서 (FIFO)가 아닌 일정한 키 값의 기준에따라서 큐 안에 데이터가 정렬되서 사용한다. 우선순위 큐 ADT 메쏘드 주요메쏘드 InsertItem(k,e) : 키 k인 원소 e를 큐에 삽입 element removeMin( ) : 큐로부터 최소 키를 가진 원소를 삭제해서 반환 ( removeMax( ) 로 하냐 removeMin( )으로 하냐에 따라 우선순위의 내부적인 정렬 상태가 내림차.. 공감수 1 댓글수 0 2020. 9. 24.
  • [ OT ] 들어가기전에.. " 알고리즘에 대한 기본적 이론정리 Section "코드는 C언어 중심으로 작성했음을 참고하길 바랍니다. 화이팅 !! Let's go M F !! Algorithm !! 공감수 0 댓글수 0 2020. 9. 24.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.