다형성(Polymorphism)이란? 다형성(Polymorphism)은 OOP(Object Oriented Programming)의 개념을 설명할 때 추상화(Abstaction)과 더불어 가장 중요하게 등장하는 용어이다. 다형성은 여러 개의 서로 다른 객체가 동일한 기능을 서로 다른 방법으로 처리 할 수 있는 기능을 의미한다. 예를 들어 칼, 대포, 총 등의 무기들은 공통적으로 '공격'이라는 동일한 기능을 다르게 수행할 수 있다. 따라서 무기 객체에서 attack() 함수를 실질적으로 구현할 필요없이 추상 클래스(Abstract Class)로 구현하면 효과적으로 설계를 할 수 있다. 오버라이딩 문제 자식 클래스에서 멤버 함수를 재정의하여 사용하는 것은 일반적으로 잘 동작하나 포인터 변수로 객체에 접근할 ..

재귀(Recusion) 알고리즘이란? 재귀 함수는 자기 자신을 참조하는 함수입니다. 원래의 문제를 동일한 유형의 하위 문제로 나누고 하위문제를 해결한 다음 결과와 결합합니다. 이러한 알고리즘을 분할 정복법이라합니다. 또 하위 결과를 저장하여 조회하는 알고리즘이 추가되면 동적 프로그래밍이라고 부릅니다. 이러한 재귀함수는 다음과 같은 구조를 가져야 합니다. Base Case : 재귀함수의 종료 조건으로 더 이상 문제를 쪼갤수 없을 때, 자기자신을 호출하지 않고 답이 나올 때 Recusion Case : 복잡한 입력을 더 간단한 입력으로 분류하여 자기자신을 호출 재귀의 활용 예시 1. 계수(factorial) 구하기 다음은 factorial 함수는 n!을 구합니다. int factorial(int n) { /..

반복 알고리즘이란? 반복적인 방법으로 문제를 해결하는 알고리즘이다. 반복 알고리즘으로 어떠한 문제를 해결할 수 있는지 증명할 때는 루프 변성과 루프 불변성을 이용한다. 루프 변성이란 반복문을 수행하면서 변하는 성질을 의미하며, 루프 불변성이란 변하지 않는 성질을 의미한다. 예를 들어, start에서 end까지 숫자의 합계를 구하는 문제는 다음과 같은 알고리즘을 갖는다. sum:=0 반복(index:=start -> end) sum := sum + index 반환 sum 위 알고리즘에서 index는 반복문이 실행 될 때마다 start에서 end까지 값이 순차적으로 증가한다. 이처럼 반복문을 수행할 때마다 변하는 성질을 루프 변성이라고 한다. 반대로 sum은 반복문이 몇 번 수행되더라도 start에서 ind..

그래프(Graph) 란? 그래프란 비선형(non-linear) 자료구조이며, 노드(Node)와 엣지(Edge)로 구성되어있다. 노드(Node) : 노드는 꼭짓점(vertex)로 표현됩니다. 엣지(Edge) : 엣지는 두 노드를 연결하는 선(line)으로 표현됩니다. 위 그래프를 V(vertex) = {0, 1, 2, 3, 4}, E(edges) = {01, 12, 23, 34, 04, 14, 13}으로 표현할 수 있습니다. 그래프는 많은 일상 생활의 문제점을 해결하기 위해 사용됩니다. (네트워크의 표현 등) 그래프의 표현 그래프를 인접 행렬(Adjacency Matrix) 또는 인접 리스트(Adjacency List)로 표현 할 수 있습니다. 인접 행렬 인접행렬은 2차원 배열(v x v)로 표현될 수 있..

트리(Tree) 란? 비선형 구조는 선형구조와는 다르게 데이터가 계층적(혹은 망)으로 구성되어있습니다. 선형구조와 비선형구조의 차이점은 구성형태뿐만 아니라 용도에서도 차이점이 있습니다. 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져있습니다. 그렇다면 트리는 무엇을 표현하기 위한 자료구조일까요? 컴퓨터의 디렉토리(directiory) 구조가 트리의 대표적인 예가 될 수 있습니다. 어떠한 프로그램, 사진, 영상 등을 찾을 때 우리는 폴더에서 폴더로 들어가면서 찾곤 합니다. 이렇게 계층적인 구조를 갖는 것이 트리라 할 수 있습니다. 또 다른 예로는 조직도, 족보 등이 있습니다. 관련 용어 Root Node : 트리 구조에서 최상위에 존재하는 A와 같은 노드 No..

배열(Array)이란? 배열은 거의 모든 프로그래밍 언어에서 기본적으로 제공되는 자료형으로 많은 고급 자료구조들에서 사용된다. 배열은 주로 여러 개의 동일한 자료형의 데이터를 한꺼번에 만들 때 사용된다. 배열의 가장 기본적인 특징은 '인덱스, 요소' 쌍의 집합이라는 것이다. 즉, 인덱스가 주어지면 해당하는 요소가 대응되는 자료구조이다. 배열에서는 모든 요소가 동일한 자료형이며 인덱스를 사용하여 직접 접근 할 수 있다. 배열의 추상 자료형 (객체) '인덱스, 요소' 쌍의 집합 (연산) create(n) : n개의 요소를 가진 배열을 생성한다. retrieve(i) : 배열의 i번째 요소를 반환한다. store(i, item) : 배열의 i번째 위치에 item을 저장한다. 배열과 메모리 함수의 파라미터로서의..