CS/Data Structure & Algorithm
[String] 1. 문자 찾기
문제 설명 한 개의 문자열을 입력받고, 특정 문자를 입력받아 해당 특정문자가 입력받은 문자열에 몇 개 존재하는지 알아내는 프로그램을 작성하세요. 대소문자를 구분하지 않습니다.문자열의 길이는 100을 넘지 않습니다. 입력 첫 줄에 문자열이 주어지고, 두 번째 줄에 문자가 주어진다. 문자열은 영어 알파벳으로만 구성되어 있습니다. 출력 첫 줄에 해당 문자의 개수를 출력한다. 예시 입력 1 Computercooler c 예시 출력 1 2 풀이 1. 문자열과 특정 문자를 받아옵니다. 2. 받아온 문자열을 소문자나 대문자로 변경합니다. 3. 문자열 첫번째부터 특정 문자와 한개씩 비교합니다. 똑같은 것이 있을 경우 answer 변수에 +1 합니다. 4. 최종 answer를 출력합니다. 배경지식 자바 String 클래..
List
List 리스트의 특징 ㅈㄷ 리스트 ADT 리스트 동작원리 배열을 이용한 List 구현 - ArrayList sequential representation 순차적으로 메모리 공간이 할당 배열이 꽉 차게 되면 더이상 늘릴 수 없다 연결node를 이용한 List 구현 - LinkedList Linked representation 여러개의 노드에 분산되어 저장, 랜덤주소 RAM이 다하지 않는 한 메모리가 가득 찰 일이 없다 1. 단순 연결 리스트 - Singly-Linked List 2. 원형 연결 리스트 - Circular-Linked List 3. 이중 연결 리스트 - Doubly-Linked List
deque
deque double-end queue deque의 구조 deque의 특징 전단과 후단에서 모두 삽입 삭제가 가능하다 데이터 구조에서는 좀 더 연산이 간단한 데이터구조를 채택하여 사용하는 것이 효율적 & 지향한다 deque의 용도 - 키보드 입력 버퍼 - screen scroll deque ADT "add와 delete가 양 쪽으로 있다" create(max_size) - 최대 크기가 max_size인 덱 생성 init(dq) - 덱 초기화 is_empty(dq) - if (size == 0) return TRUE; else return FALSE; is_full(dq) - if (size == max_size) return TRUE; else return FALSE; add_front(dq, e) -..
Queue
queue "매표소의 대기열" 큐의 구조 큐의 특징 FIFO (First-In First-Out)(선입선출) 큐의 용도 직접적인 응용 - 시뮬레이션의 대기열 - 통신에서의 데이터 패킷들의 모델링 - 프린터와 컴퓨터 사이의 버퍼링 간접적인 응용 - 프로그래머의 도구로써 많은 알고리즘에 사용 큐 ADT create(max_size) - 최대 크기가 max_size인 공백큐 생성 init(q) - 큐 초기화 is_empty(q) - if (size == 0) return TRUE; else return FALSE; is_full(q) - if (size == max_size) return TRUE; else return FALSE; enqueue(q, e) - if (is_full(q)) full로 인한 오류..
Stack
Stack "쌓아놓은 더미" 스택의 구조 스택의 특징 LIFO (Last-In First-Out)(후임선출) 가장 최근에 들어온 데이터가 가장 먼저 나간다 스택의 용도 입력과 역순의 출력이 필요한 경우 - 되돌리기 기능 - 함수호출에서 복귀주소 기억 - 괄호 검사 - 후위 표기식의 계산 - 미로 탐색 문제 해결 ... 스택 ADT 스택이 갖추어야 할 추상적 기능들 이것을 프로그래밍해서 실제로 구현하는 것과 다른 의미 create(size) is_full(s) is_empty(s) push(s, item) pop(s) peek(s) 배열을 이용한 스택의 구현 stack[], top 두개의 변수 사용 // 스택 비어있는지 확인 is_empty(s) if top = -1 then return TRUE else..
Recursion (<-> Iteration)
recursion "함수 호출 반복" // recursion 예제 #include void up_and_down(int);// prototype int main(void) { up_and_down(1);// 함수 호출 반복 return 0; } void up_and_down(int n) { printf("Level %d: n location %p\n", n, &n); // 1 if (n < 4) up_and_down(n+1); printf("LEVEL %d: n location %p\n", n, &n); // 2 } Level 1: n location 010FFA4C Level 2: n location 010FF974 Level 3: n location 010FF89C Level 4: n location..