Step-by-Step

큐(Queue) FIFO(First In First Out) 특성을 가진 자료구조 데이터가 들어오는 위치는 가장 뒤로 후단(Rear or Back)이라 하고, 데이터가 나가는 위치는 가장 앞인 전단(Front)이다 스택에서는 삽입, 삭제 모두 top을 통해서 이루어지는데, 큐에서는 front에서 삭제, rear에서 삽입을 담당한다 큐의 추상자료형(Abstract Data Type; ADT) - 입력 : 엔큐(Enqueue) - 출력 : 디큐(Dequeue) ※ 간혹 스택과 동일하게 Push,Pop을 쓰기도 하고, Push,Pull을 사용하기도 한다 큐의 종류 1. 선형 큐 - 1차원 배열을 정의한다 - 삽입, 삭제를 위한 변수인 front와 rear을 만든다 - front와 rear의 초기값은 -1이다 ..

순환(Recursion) 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 가장 대표적인 예시로 정수의 팩토리얼을 구현한 함수가 있다 int factorial(int n) { if(n

스택(Stack) LIFO(Last In First Out) 특성을 가진 자료구조 메모리에 들어오는 데이터 위치가 메모리 말단(Top Pointer)이고 쓰기 위해 내보내는 데이터 역시 메모리 말단을 거친다 스택의 추상자료형(Abstract Data Type; ADT) - 입력연산 : 푸시(Push) - 출력연산 : 팝(Pop) - 조회연산 : 피크(Peek) ※ 조회연산은 탑 포인터가 가리키는 데이터를 조회만 할 뿐 탑의 순번(인덱스)은 변화시키지 않는다 스택의 Push, Pop 과정 1. Push - 먼저 Top Pointer의 값을 증가 시킨 후, 증가시킨 Top의 위치에 데이터를 넣는다 2. Pop - 먼저 데이터를 꺼낼 Top의 위치를 다른 변수(인덱스)에 별도로 저장한 후, Top의 위치를 감..

데이터(data) 프로그램에서 데이터(data)는 처리의 대상이 되는 모든 것 데이터 타입(data type) 데이터의 집합과 데이터에 적용할 수 있는 연산의 집합 즉 데이터 타입 = 객체(Object) + 객체 간의 연산(Operation) 이 된다 ※ 예로 C언어에는 int라는 데이터 타입을 제공하는데, int 데이터 타입에서 데이터는 "정수의 집합"이고, 연산은 "정수 간 연산"을 의미한다 추상 데이터 타입(abstract data type; ADT) 새로운 데이터 타입을 추상적,수학적으로 정의한 것 자료 자체의 형태와 그 자료에 관계된 연산들을 "수학적으로만" 정의한 것 데이터 타입의 정의가 그 데이터 타입의 구현으로부터 분리된 데이터 타입 ※ 즉 추상 데이터 타입에서 데이터나 연산이 무엇(wha..

그동안 까먹었던 내용을 복습도 하고, 기본을 다질 겸책을 펼치게 되었다 공부한 내용들을 잊지 않게 블로그에 차근차근 정리하기로 했다! 자료구조(Data Structure) 프로그램에서 자료들을 정리하는 여러가지 구조들 프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초 이론 ※ 컴퓨터의 대부분 프로그램에서 자료(data)를 처리하고 있고, 자료들은 자료 구조(data structure)를 사용하여 표현되고 저장된다 알고리즘(Algorithm) 컴퓨터로 문제를 해결하기 위한 단계적인 절차나 방법 문제와 컴퓨터가 주어진 상태에서 문제를 해결하는 방법을 정밀하게 장치가 이해할 수 있는 언어로 기술한 것 좁은 의미로 자료구조 내에서 기본적인 연산을 하기 위한 ..

탐욕 알고리즘(Greedy Algorithm) 최적해를 구하는 데에 사용되는 근사적인 방법 여러 경우 중 하나를 결정해야 할 때마다 그때마다 최적의 방법을 선택하여 최종 해답에 도달하는 방법 매 순간마다 최적의 선택을 하더라도 최종적 해답이 최적이라는 보장은 없다 (각 순간의 지역적 선택이 최적일지는 몰라도 전역적으로 봤을때는 최적의 선택이 아닐 수 있다) 탐욕 알고리즘 적절한 사용 탐욕 알고리즘은 아래 두 경우에 사용할 때 좋은 해결방안이 된다 탐욕 선택 속성(Greedy Choice Property) : 매 순간의 탐욕적인 선택이 최종 답의 최적의 선택이 됨 최적 부분 구조(Optimal Substructure) : 부분 문제를 최적화하는 것이 전체를 최적화하는 것임 즉 탐욕 알고리즘을 사용할 때는 ..

동적계획법(Dynamic Programming : DP) 특정 범위까지의 값을 구하기 위해서 그것과 다른 범위까지의 값을 이용하여 효율적으로 값을 구하는 알고리즘 설계기법 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법 최적부분구조와 같은 문제에서 효과를 발휘함 ★ 최적 부분 구조(Optimal Substructure) 문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성 동적계획법 사용 동적 계획법을 적용하기 위한 예시를 가져왔다 여기서 조건은 f(a,b) = f(a-1,b) + f(a,b-1) (a,b>=1) f(0,0) = 1 자연수 n에 대하여 f(n,0)=f(0,n)=1 여기서 주목해야 하는 점은 f(1,1)이다 f(2,2)는 f(1,2)와 f(2,1)의 합으로 나타낼 수..

맹목적 탐색 이미 정해진 순서에 따라 상태 공간 그래프를 점차 형성해 가면서 해를 탐색하는 방법 대표적인 맹목적 탐색 : 너비우선탐색(BFS), 깊이우선탐색(DFS) 너비우선탐색 (BFS;Breadth First Search) 하나로 시작 정점을 방문한 후 시작 정점에 인접함 모든 정점들을 우선 방문하는 방법 갈림길에 연결되어 있는 모든 길을 한번씩 탐색한 뒤 다시 연결되어있는 모든 길을 탐색하는 방법 너비우선탐색은 트리나 그래프를 방문 또는 탐색하는 방법으로 순서는 다음과 같다 1. 루트에서 시작 2. 루트의 자식 노드들을 [1]에 저장 3. [1]에 저장된 노드들을 차례로 방문 후 각각 자식들을 [2]에 저장 4. [2]에 저장된 노드들을 차례로 방문 후 각각 자식들을 [3]에 저장 5. 위의 과정을..