분류 전체보기 (49) 썸네일형 리스트형 6. Queue Queue 뒤에서 대기열에 추가하고 앞에서 대기열에서 제거가 발생하는 자료구조입니다. FIFO (First-in-First Out) 목록이라고도합니다. 추가는 대기열의 뒤쪽에만 할 수 있으며 제거는 앞쪽에서만 할 수 있습니다. Array implementation of a queue 큐에 항목을 저장하기 위해 q[] 배열을 사용합니다. enqueue(): q[tail]에 새로운 항목을 추가합니다. dequeue(): q[head]에 있는 항목을 제거합니다. Update head and tail modulo the capacity. Add resizing array. 큐의 문제점 배열의 특성상 큐의 용량(Capacity) 이미 정해져 있으므로, 배열로 구현한 큐의 삽입(Enqueue)과 삭제(Dequeue.. 5. Stack Stack 입출구가 동일하여 가장 나중에 들어온 데이터가 가장 빨리 나가는 자료구조입니다. LIFO(Last-in-First-Out) 목록이라고도 합니다. 구현 (배열) N개의 항목을 스택에 저장하기 위해 배열 s[ ]을 사용합니다. push(): s[N]에 새로운 항목을 추가합니다. pop(): remove item from s[N-1]에 있던 항목을 제거 합니다. Defect. capacity이상으로 항목의 개수가 들어오면 스택 오버플로우가 일어납니다. => resize로 해결 기능 Stack CreateStack (maxStackSize) bool IsFull (Stack stack) bool IsEmpty (Stack stack) void Push (Stack stack, item) void Po.. 4. Linked List Linked List Singled Linked List 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가리킵니다. Example) 단어 정렬 단어들이 임의의 순서로 주어졌을 때 단일 연결 리스트를 사용하여 알파벳 순으로 단어를 배열하고 싶습니다. 단어 목록은 다음과 같습니다. HAT, CAT, EAT, WAT, BAT, FAT, VAT 알파벳순 정렬을 할 때 Link의 숫자는 다음 data의 숫자입니다. data[4] = bat; link[4] = 1; data[link[4]] = data[1] = cat; link[1] = 2; ... 위와 같이 단일 연결 리스트란 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조입.. 3. Recursion Recusion 재귀: 자기 자신을 호출하는 함수 자신의 복사본을 호출하여 더 작은 문제를 풀게함으로써 문제를 해결합니다. 이를 재귀 단계라고 하는데, 재귀 단계는 더 많은 수의 재귀 단계를 만들 수 있습니다. 매 단계보다 함수는 원본 문제보다 조금 더 단순한 문제를 가지고 자기 자신을 호출합니다. 재귀를 사용하여 문제를 해결할 때 아이디어는 큰 문제를 더 작고 유사한 문제로 만듭니다. 결국이 프로세스가 반복되고 문제의 크기가 각 단계에서 감소하면 매우 작고 해결하기 쉬운 문제에 도달합니다. void recursiveFunction (int num) { printf("%d\n", num); if (num < 4) recursiveFunction(num+1); } n = 0 일때 결과 구성 base cas.. 1. 기초수학 1. logarithms $ X = a^b, \ \ b = log_aX \\$ $ log \ ab = log \ a + log \ b \\$ $ log \ \frac a b = log \ a - log \ b \\$ $ log \ a^b = b \ log \ a \\$ $ log_an = \frac {log_bn} {log_ba} = \frac {log \ n} {log \ a} \\ $ $ log_aa = 1, for \ all \ a > 0 \\ $ $ log_a1 = 0, for \ all \ a > 0 \\$ 2.summation 2-1. Arithmatic sum $ \sum_{i=1}^n i = 1 + 2 + 3 ... + i \\ $ $ \sum_{i=1}^n i = \frac {n(n+1).. 2579. 계단 오르기 문제 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다. 예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다. 계단 오르는 데는 다음과 같은 규칙이 있다. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 따라서 첫 번째 계단을 .. 잠 4:23 무릇 지킬만한 것 보다 내 마음을 지키라. 생명의 근원이 이에서 남이니라 Dynamic Programming Dynamic Programming 다이나믹 프로그래밍은 특정 알고리즘이 아닌 디자인 패러다임입니다. 우리가 알고 있는 이러한 디자인 패러다임은 분할 정복, 백트레킹 등이 있습니다. 최적화 문제: optimal value를 찾는 솔루션, 최대화 최소화 문제 우리는 최적의 선택을 모른다. 따라서 우리는 미리 계산한 하위 문제의 비용을 기반으로 하위 문제를 모두 시도한다. 우리가 내리는 선택에 따라 해결해야 할 하위 문제가 결정된다. 최적화 예시 최단거리 문제: 포항에서 서울까지가는 길은 많습니다. 최단 경로, 가장 경치 좋은 경로, 가장 빠른 경로를 계산하려고합니다. 잡 스케줄링: 여러 프로세서에서 작업 세트를 예약하는 방법에는 여러 가지가 있습니다. 프로세서의 다양한 기능과 작업의 다양한 리소스 요구 사.. 이전 1 2 3 4 5 6 7 다음