CS45 그래프와 트리의 차이는? [ 그래프 (Graph) ] 2개 이상의 경로가 가능하다. 노드들 사이에 무방향 / 방향 에서 양방향 경로를 가질 수 있다. Self-Loop 뿐 아니라, Loop / Circuit 모두 가능하다. 루트 노드라는 개념이 없다. 부모-자식 관계라는 개념이 없다. 그래프 순회는 DFS나 BFS로 이루어진다. 그래프는 Cyclic 혹은 Acyclic 이다. 간선의 유무는 그래프에 따라 다르다. 그래프는 네트워크 모델이다. [ 트리 (tree) ] 트리는 그래프의 특별한 케이스이며, "최소 연결 트리" 라고도 불린다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다. Loop 나 Circuit이 없다. 당연히 Self-Loop 도 없다 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한 개의 부모 노드만.. 2022. 4. 4. Git과 Github에 대해서... [ Git ] 로컬에서 관리되는 버전 관리 시스템 (VCS : Version Control System) 소스코드 수정에 따른 버전을 관리해주는 시스템 [ Github ] 클라우드 방식으로 관리되는 버전 관리 시스템 자체 구축이 아닌 빌려 쓰는 클라우드 개념 오픈소스는 일정 부분 무료로 저장 가능, 아닐 경우 유료 사용 분산 버전 제어, 엑세스 제어, 소스코드 관리, 버그 추적, 기능 요청 및 작업관리 제공하는 플랫폼 깃을 사용하는 프로젝트를 지원하는 웹호스팅 서비스 위에 정리한 걸 풀어 설명하자면, 깃은 로컬에서 버전 관리 시스템을 운영하는 방식이고, 깃허브는 저장소를 깃허브에서 제공해주는 클라우드 서버를 이용한다는 차이입니다. 따라서, 다른 사람들과 협업을 하게 될 경우, 또는 오픈 소스를 공유하고 .. 2022. 4. 3. 백트래킹(Backtracking) 이란? 백트래킹이란? 재귀적으로 문제를 하나씩 풀어가되, 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 (유망[promising]하지 않은지) 판단하고 그러한 경우 해당 상태(노드)를 제외하고 다음 단계로 나아가는 방식이다. 백 트래킹은 현재 상태(노드)에서 다음 상태(노드)로 나아갈 수 있는 모든 경우를 찾되, 그 중 유망하지 않다면? 현재에서 더이상 나아기자 않고 이전의 상태(노드)로 돌아가 다음 상태(노드)를 검사합니다. 여기서 더 이상 탐색할 필요 없는 상태(노드)를 제외하는 것을 가지치기(pruning) 이라고 합니다. 백트래킹을 사용하는 알고리즘 중 하나는 대표적으로 DFS가 있습니다. DFS는 재귀를 통해 가능한 경로 중 유망한 경로만 찾아서 탐색을 수행한 뒤, 다시 돌아와 그 .. 2022. 4. 1. 산술 오버플로 산술 오버플로 란? 컴퓨터는 수학자들이 만든 기계들이며 수학에 따라 움직입니다만, 현실 세계에 존재하는 물건인지라 엄연한 제한이 있습니다. 그 중 가장 대표적인 제한이 바로 유한성입니다. 수학에는 어떤 변수 n이 있다고 하면 이 변수에 담을 수 있는 숫자에는 제한이 없습니다. 그러나 컴퓨터의 모든 변수에는 담을 수 있는 크기가 제한되어 있습니다. 따라서, 수학적/논리적으로는 완전히 정당한 알고리즘도 프로그램으로 구현했을 때, 예상과 다르게 동작하는 경우를 흔하게 볼수 있습니다. 이 문제를 일으키는 흔한 원인이 바로 산술 오버플로 (Arithmetic overflow) 입니다. 어떤 식의 계산 값이 반환되는 자료형의 표현 가능한 범위를 벗어나는 경우를 말합니다. 현대 많은 언어들에서는 메모리가 허락하는 한.. 2022. 3. 20. 점화식 이란? 알고리즘을 공부하다가 점화식이라는 키워드가 나와서 알아본 정보입니다. 점화식이란 ? 수열의 각 항 간에 관계를 (단순 나열이 아닌 규칙으로) 표현한 관계식을 의미합니다. 좀 더 쉽게 이야기하면? - 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것입니다. 다시 말해 재귀함수의 구조를 갖는 알고리즘만 점화식으로 표현할 수 있습니다. - 수열의 N 번째 항(일반항) 을, - 그 앞의 항들에 의해 규칙적(종속적)으로 표현한 관계식을 말합니다. 어떤 점화식 표현이있을까 ? 점화식 특징은 ? 등식 또는 관계식 형태를 갖고있습니다. (단, 문제 제시 때는 초기값 또는 경계값이 반드시 필요합니다) 점화식 자체는, 간접적이고 부분적인 정보만 주어, 따라서 일반항을 구할 필요 있습니다. 점화식의 점근.. 2022. 3. 16. 다이나믹 프로그래밍(Dynamic Programming) 이란? 동적계획법 (Dynamic Programming) 이란? 최적화 문제를 위해 고안된 기법으로 복잡한 문제보다 간단한 여러 개의 부분 문제로 나누어 해결합니다. 중요한 점은 한 번 계산된 부분 문제의 답을 저장해 두어 나중에 같은 부분 문제의 답을 원할 시, 반복되는 연산 없이 바로 저장해 둔 걸 꺼내 쓸 수 있도록 하는 것이 핵심입니다. 주로 중복되는 부분 문제(Overlapping Subproblem)와 최적 부분 구조 (Optimal Substructure)를 가지고 문제들을 풀 때 사용됩니다. 또한, 동적 계획법을 설계할 때는 가장 중요한 것이 현재 문제의 상태와 문제와 부분 문제 간의 관계 또는 전이를 파악하는 것입니다. 문제들 간의 관계 또는 전이를 정확하게 파악한다면 알고리즘의 정당성을 얻을 .. 2022. 3. 16. 정렬 알고리즘 비교 In-Place ? 입력리스트 내부에서 정렬이 이뤄지는 경우를 가리킵니다. 반대는 정렬 도중에 별도 저장공간을 필요로 하는 경우입니다. Stable ? Stable이란 같은 값의 위치가 정렬 과정에서 뒤바뀌지 않는 것을 뜻합니다. 버블 정렬 선택 정렬 삽입 정렬 셸 정렬 합병 정렬 퀵 정렬 힙 정렬 2022. 3. 13. 힙 정렬 (Heap Sort) 이란? 힙 정렬이란? 자료구조 힙(heap)을 구성하여 정렬하는 방법이다. 힙이란? 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이며 최댓값, 최솟값을 쉽게 추출할 수 있는 자료구조 이다. 이진트리란? 컴퓨터 안에서 데이터를 표현할 때 데이터를 각(Node)에 담은 뒤 노드를 두 개씩 이어 붙이는 구조이다. 최대 힙트리나 최소 힙트리를 구성해서 정렬하는 방법이다. 내림차순 -> 최대 힙(부모노드가 자식 노드보다 큰 힙)으로 구성 오름차순 -> 최소 힙(자식노드가 부모노드보다 큰 힙)으로 구성 1. 정렬해야할 N 개의 요소들로 최대힙(완전 이진트리 형태)를 만든다. *최대힙이니, 내림차순 기준 2. 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다. 3. 삭제되는 요소들(최대값.. 2022. 3. 13. 이전 1 2 3 4 5 6 다음
