개념
-
그래프 알고리즘프로그래밍 기초/알고리즘 2022. 1. 21. 13:33
동적 프로그래밍 그래프 기본 개념 현상이나 사물을 정점과 간선으로 표현하는 것을 말한다. 정점(Vertex) 대상이나 개체 간선(Edge) 대상이나 개체 간의 관계 그래프는 간선이 상호 통행이 가능한지, 일방통행만 가능한지에 따라 유향 그래프와 무향 그래프로 나뉜다. 유향 그래프 정해진 방향으로만 이동이 가능한 그래프, 화살표로 간선을 표현한다. 무향 그래프 쌍방으로 이동이 가능한 그래프, 실선으로 간선을 표현한다. 또, 각각의 정점이 가지는 관계의 정도를 간선에 가중치로 표현하기도 한다. 인접 행렬을 이용한 그래프의 표현 각 행, 열을 순서대로 정점을 나타내고 각각의 간선은 해당하는 행, 열의 위치에 값을 할당하는 방식으로 그래프를 표현하여 이해하기 쉽고 간선의 존재 여부를 곧바로 파악할 수 있다. 가..
-
동적 프로그래밍 개념프로그래밍 기초/알고리즘 2022. 1. 12. 10:45
동적 프로그래밍 동적 프로그래밍 개념 큰 문제의 해답에 작은 문제의 해답이 포함되는 알고리즘을 재귀적으로 처리할 때 나타나는 비효율을 제거하기 위한 프로그래밍 방식을 동적 프로그래밍이라고 한다. 가령 피보나치수열의 경우 다음과 같은 식으로 나타난다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 이를 재귀적으로 해결하기 위해서는 기존에 구했던 해답을 다시 구하는 등의 반복이 일어난다. 이러한 문제를 해결하기 위해 부분 결과를 저장하면서 해를 구하는 것이 동적 프로그래밍의 핵심이다. 가령 위에서 설명한 피보나치수열의 문제를 동적 프로그래밍을 적용해 해결한다면 다음과 같이 풀 수 있다. 피보나치수열 알고리즘 fib(n) { if (f[n] ≠ 0) then return f[n]; el..
-
자료구조 개념 정리프로그래밍 기초/자료구조 2020. 9. 27. 21:02
자료구조 개요 자료구조란? 데이터를 효율적으로 접근 및 사용이 가능하도록 하는 데이터의 조직, 저장, 관리 방법을 말한다. 자료 구조의 분류 선형 구조 자료 간 연결 관계가 1:1 관계인 구조 스택, 큐, 덱 배열과 연결 리스트가 포함되기도 한다. 비선형 구조 계층 구조 혹은 망 구조 트리, 그래프 자료구조의 표현 자료의 표현 방법 컴퓨터는 0과 1로 구성된 2 진수를 사용하며 n 개의 비트로 2ⁿ 개의 상태를 표현 가능하다. 1 개의 비트 → 2¹ = 2 개의 상태 표현 (0, 1) 2 개의 비트 → 2² = 4 개의 상태 표현 (00, 01, 10, 11) 3 개의 비트 → 2³ = 8 개의 상태 표현 (000, 001, 010, 011, 100, 101, 110, 111) º º º n 개의 비트 ..