자료구조48 [알고리즘] Knapsack Problem Knapsack 알고리즘 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 터질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 위와 같은 문제를 해결하는대 사용되는 알고리즘을 대표적으로 Knapsack 알고리즘 이라고 부른다. 이러한 Knapsack 문제는 동적프로그래밍(DP)의 대표적인 문제로, 대부분의 알고리즘 서적에서 확인해볼수 있는 대표 유형이라 할 수 있다. 알고리즘의 분석 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 어떤 문제를 DP로 풀기 .. Algorithm/PS 알고리즘 정리 2022. 1. 20. [알고리즘] 조합 알고리즘 조합 알고리즘 같은 경우 자주 사용한다는 글로 정리해두는 것 도 좋을것 같아 글을 작성해본다. 조합이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 간단하게 0, 1, 2, 3, 4, 5 가 있다고 해보자. 이중 숫자 4개를 순서에 상관없이 선택하는 경우는 몇가지가 있는지를 파악하는 것 이다. 순서가 상관없으니, (0, 1, 2, 3) 과 (0, 1, 3, 2)는 같은 경우이다. 이는 DFS를 활용하여 구하면 된다. 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 tree를 그려보면서 생각해 보자. 빨간 선만 따라서 DFS를 진행하면 (0, 1, 2, 3) 이라는 하나의 조합이 나온다. 그다음은 0, 1, 2, 4 또 그다.. Algorithm/PS 알고리즘 정리 2022. 1. 20. [서평] 윤성우의 열혈 자료구조 저의 돈으로 직접사서 직접 완독해본후 써보는 후기입니다. 따라서 장점은 장점대로 칭찬할것이며, 단점은 단점대로 언급할 것 입니다. 윤성우의 열혈 자료구조 저자 : 윤성우 출판 : 오렌지미디어 발매 : 2012.01.18. 2020/8/1 ~ 2020/12/7 (학교 수업과 병행하여 전반적인 자료구조론에 이 책으로 대해 독학하였습니다.) 1) 책의 표지 2) 단원별 구성 3) 읽은소감 우선 저의 글의 앞부분만 보는 분들을 위해 먼저 간단히 3가지에 대해 답해보겠습니다. Q 자료구조를 공부하기 전에 필요한 C언어 수준/ 지식은? => 최소한 C언어 문법은 다 알고있으셔야 합니다. C를 모른다면 코드를 전혀 이해하실수 없을 것 입니다. C언어 기초책이 아닌 C언어 라는 도구를 사용한 자료구조에 관한 책 입니다.. Life/Book Record 2022. 1. 20. [알고리즘] Union Find 알고리즘 : 경로 압축 기존에도 Union Find 알고리즘을 사용하기는 했지만, 경로 압축을 하고있지 않아 시간이 조금더 걸리는 문제가 있었다. 간단하게 경로압축을 할 수 있는 방법을 배워 글을 써본다. Union & Find " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 기본적인 Union Find 알고리즘의 구성은 다음과 같다. int Find(int num){ if(parent[num] == num) return num; return Find(parent[num]); } void Union(int a, int b){ a = Find(a); b = Find(b); if(a != b) parent[a] = b; } 맨 처음 parent 배열에서 각각은 자기 자신의 번호를 갖고 시작한다. 1.. Algorithm/PS 알고리즘 정리 2022. 1. 20. [알고리즘] Red-Black Tree : 레드 블랙 트리 스스로 공부해 본 후, 다시 정리하는 내용의 글 입니다. 틀린부분과 실수가 있다면 지적해주시면 감사하겠습니다. 레드 블랙 트리 또한 binary-search tree(이진탐색트리) 의 일종이다. 기존의 이진탐색트리 같은경우 input이 이미 정렬되있다면 높이가 n이 되버리고, 따라서 시간복잡도 또한 O(n)에 도달하게 된다. 하지만 레드 블랙 트리의 경우 특정 조건을 지키면서 균형잡힌 이진트리가 되기때문에 Search, Insert, Delete 연산을 최악의 경우에도 O(logN) 시간안에 가능하도록 해준다. 이번 포스트의 순서는 다음과 같다. 1) NIL node 의 설명 2) Red-Black tree의 정의 3) Red-Black tree의 높이 4) Left and Right rotation 5.. Algorithm/PS 알고리즘 정리 2022. 1. 19. [백준][C++] 17135번: 캐슬 디펜스 <176> 직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다. 17135번: 캐슬 디펜스 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다. www.acmicpc.net 생각의 흐름 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 구현 문제는 생각의 순서를 정하는것이 중요하다. 어떤 순서로 진행되어야 할까? 1. 3명의 궁수를 N+1 번지에 배치한다. 2. 원본 map을 복사한 copyMap 만들기(궁수 배치의 case 마다 한번씩 복사해주어야 한다) 3. 왼쪽 궁수부터 BFS 탐색을 진행하면서, 가장 가까운 적을 공격표.. Algorithm/백준 2022. 1. 19. 뇌를 자극하는 C++ STL : 11장. 컨테이너 어댑터 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 11장. 컨테이너 어댑터 컨테이너 어댑터는 다른 컨테이너의 인터페이스를 변경한 컨테이너 이다. STL에는 stack, queue, priority_queue 3가지 컨테이너 어댑터가 있다. stack " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 stack 어댑터를 적용시킬 컨테이너는 empty(), push_back(), pop_back(), back(), size() 인터페이스를 지원해야한다. 따라서 이러한 인터페이스를 제공하는 vector, deque, list는 어댑터를 적용시켜 stack으로 사용할 수 있다. 다음 코드를 통하여 확인해 보자, #include .. CS/C++ 2022. 1. 18. 뇌를 자극하는 C++ STL : 10장. 반복자 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 10장. 반복자 반복자는 컨테이너의 원소를 순회하고 접근하는 일반화된 방법을 제공한다. 반복자의 종류 " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 - 입력 반복자: 전방향 읽기(istream) - 출력 반복자: 전방향 쓰기(ostream) - 순방향 반복자: 전방향 읽기, 쓰기 - 양방향 반복자: 양방향 읽기, 쓰기 - 임의 접근 반복자: 랜덤 읽기, 쓰기 X::iterator와 X::const_iterator " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 아 처음볼때 X가 뭐지?? 이런생각이 들 수 있는데 컨테이너를 표시한거다. v.. CS/C++ 2022. 1. 18. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 14장, 탐색 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 14장 탐색 탐색은 하나 이상의 field로 구성된 record의 집합에서 원하는 레코드를 찾아내는 작업이다. 보통 이런 레코드의 집합을 table이라고 부른다. 레코드들은 각각 고유한 키값을 갖는데, 이를 탐색키(search key) 라고 부른다. 자료 검색은 테이블에서 해당 탐색키를 찾는 것 이다. C++로 쉽게 풀어쓴 자료구조 (14장, 탐색) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 키와 값을 가진 요소 (key, value)의 집합 연산: - create(key, value): 주어진 key와 value를 각각 키와 값으로 갖는 레코드를 생성. .. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 12장, 가중치 그래프 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 이번 12장 책 코드에 중간중간 오류코드들이 보인다... 이해를 조금 방해하는 수준이다. 1) 12장. 가중치 그래프(Weighted Graph) 가중치 그래프는 이전에 만들었던 AdjMatGraph class를 상속하여 사용한다. 이전에 사용했던 인접행렬에서는 간선이 있으면 1 없으면 0을 행렬에 저장했지만, 이번에는 가중치값을 행렬에 저장하였다. 일정 범위를 두고 그 범위 안의 값이면 간선이 있고, 이를 벗어나는경우는 간선이 없다고 여긴다. WGraph.h #pragma once #include "AdjMatGraph.h" const int inf = 100; class WGraph : public Ad.. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 11장, 그래프 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 1) 11장. 그래프(Graph) Graph의 ADT " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 데이터: 정점의 집합과 간선의 집합 연산: - creat(): 그래프를 생성한다. - isEmpty(): 그래프가 비어있는지 확인한다. - insertVertex(v): 그래프에 정점 v를 삽입한다. - insertEdge(u, v): 그래프에 간선 (u, v)를 삽입한다. - deleteVertex(v): 그래프의 정점 v를 삭제한다. - deleteDdge(u, v): 그래프의 간선(u, v)를 삭제한다. - adjacent(v): 정점 v에 인접한 모든 정점의 집합을 반.. CS/Data Structure (2021-1) 2022. 1. 15. [자료구조] C++로 쉽게 풀어쓴 자료구조 : 10장, 힙 내돈내고 내가 공부한것을 올리며, 중요한 단원은 저 자신도 곱씹어 볼겸 가겹게 포스팅 하겠습니다. 10장. 힙(Heap) " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 큰(or작은) 이진트리 를 말한다. A가 B의 부모 노드라고 가정하면, key(A) >= key(B) 인경우가 최대 힙이 되며, key(A) HTML 삽입 미리보기할 수 없는 소스 insert(key) heapSize HTML 삽입 미리보기할 수 없는 소스 void heapSort(int a[], int n) { MaxHeap h; for (int i = 0; i = 0.. CS/Data Structure (2021-1) 2022. 1. 15. 이전 1 2 3 4 다음
