재귀 호출 1. 재귀호출이란? 호출된 함수가 호출하는 함수와 동일한 함수 1) 개념 - 재귀함수를 구현하기 위해 탈출 조건(종료 조건)을 제대로 명시해줘야한다. - 최초에 시작하는 초기항이 있어야한다. 이를 base case이라고 한다. - 우리 목표에 도달할 때까지 식을 만들어서 적용하는 과정이 필요하다. 이를 재귀식 혹은 점화식을 잘 만들어야한다. - factorial에서의 정의는 0!는 1로 가정한다. 하지만 이를 모두 체크하는 것이 아닌 number가 1이 될 때 1을 리턴하도록 해서 이를 표현할 수도 있다. - 자기 자신을 우항 혹은 좌항에 놔두는 것을 재귀식이라고 한다 - 언젠가 n은 0이 되는 때가 등장하는데 이를 '점화식의 해 혹은 재귀식의 해'라고 한다. 2) 함수가 호출될 때 - 호출 ..

Unsorted list 구현 C++을 통해서 Unsorted list를 구현했다. 특히 ItemType, Unsorted list, Application을 세 파트로 나누어 코드를 구현했다. Unsorted list는 각 요소로서 ItemType을 포함하고 있고, Application에서 Unsorted list를 객체로 사용했다. 또한 각각의 파트는 헤더와 cpp 파일을 구분해 각각 구현했다. 해당 실습에서의 특징적인 점은 Unsorted list를 Linked list가 아닌 Array list로 구현했다. 이에 따라 데이터 삽입, 삭제하는 방법이 다르니 이를 고려하여 코드를 확인하면 좋을 것 같다. 1. ItemType 1) ItemType h #ifndef _ITEMTYPE_H #define _..

Linked Structured 1. Linked Structure을 활용한 Stack 1) ADT의 장점 내부적으로 사용하는 자료의 유형을 변경할 수 있다. - ADT의 장점은 사용된 구현 유형을 변경할 수 있다는 것이다. 2) (동적) 배열 구현 시 발생할 수 있는 문제점 자료구조의 최대 크기가 정해져있다. - Stack의 (동적) 배열 구현에는 단점이 존재한다. Stack의 최대 크기는 매개변수로 생성자에 전달한다. 이에 따라 배열의 크기를 초과하는 데이터를 삽입해야할 때는 문제가 발생할 수 있다. 따라서 데이터의 입력 예측이 어려운 경우나 예측을 벗어난 데이터가 입력된 경우에는 배열이나 동적배열을 사용할 때는 문제가 발생할 수 있다. 3) (동적) 배열 구현 시 문제 해결 링크드 리스트를 통해 사..

Stack and queue 1. Stack이란? 1) Stack이란? 항목의 제거 및 추가가 Stack의 상단에서만 발생할 수 있는 정렬된 동족 항목의 그룹 - 같은 데이터 타입의 자료구조만 모아서 사용한다. - Stack은 LIFO (Last In Fisrt Out) 구조이다. cf) 메모리 상에서의 Stack: 지역변수를 저장하는 공간 cf) Call Stack: 함수를 호출할 때 추적하는 것을 의미하는데 함수가 호출될 때 스택 구조로 쌓이기 때문에 이를 Call Stack이라고 한다. 2) 멤버 함수 구현 시 주의 사항 - 요소를 pop할 때는 실질적으로 요소를 삭제할 필요가 없이 top의 위치만 조정하면 된다. 메모리 상에는 남아있지만 이를 사용할 수는 없다. - pop 메소드는 마지막 데이터를..

ADTs Unsorted List and Sorted List 자료구조 멤버변수와 멤버함수로 나눠서 내부적으로 특정한 연산을 통해 어떤 특성을 유지할 수 있도록 하는 것 1. 추상화 자료형 1) ADT 개념 - 구현과의 의존성이 없이 데이터의 특징을 정의하는것이다. - 슈도코드와 같이 문법적인 제한이 없이 흐름도를 통해 표현할 수 있다. - 데이터의 특징: 영역과 연산 2) 데이터의 세가지 레벨 응용 레벨 -> 논리 레벨 -> 구현 레벨 (1) 응용 레벨: 실생활에서 사용할 수 있는 자료의 레벨, 정보가 모여있는 곳 (2) 논리 레벨: 자료의 범위와 연산의 추상적인 관점 (3) 구현 레벨: 자료를 저장하기 위한 구조의 표현명세 및 연산을 위한 코딩 3) ADT 연산자 - 객체를 표현하기 위한 방법론이기에..

Data design and Implementation 1. 데이터 디자인 1) 자료의 추상화 - 자료의 구현에서 자료 형식의 논리적인 특징을 분리하는 방법 - Logical properties: 흐름도가 만들어져있고, 흐름도를 코드와 유사한 형태로 표현 - Implementation: 실제 코드를 구현하는 부분 2) 자료의 캡슐화 - 의사코드로 작성이 되어있는 부분을 문법적으로 채워넣는 것 - 논리 레벨에서 데이터를 사용하는 것으로부터 데이터의 표현을 분리하는 행위 - 코드 작성은 사람이 사용하는 언어와 가까운 형태로 기술을 하면 내부적으로는 컴퓨터가 다룰 수 있는 언어로 바뀌게 된다. 따라서 코드를 작성하는 우리는 컴퓨터가 어떤 식으로 저장되어있는지를 모두 알 필요는 없다. 이는 캡슐화덕분이다. - ..