Computer Science/Data Structure
-
04. 스택의 응용 - 괄호 검사 문제 알고리즘Computer Science/Data Structure 2021. 4. 10. 11:29
4.4 스택의 응용 괄호 검사 문제 프로그램에서 사용되는 괄호에는 [, ], {, }, (, ) 등이 있다. 스택을 이용하여 올바르게 사용되었는지 스택을 활용하여 구현해보자 조건 왼쪽 괄호의 개수와 오른쪽 괄호의 개수가 동일해야한다. 같은 종류의 괄호에서 왼쪽 괄호는 항상 먼저 나와야한다. 서로 다른 종류의 왼쪽 괄호와 오른쪽 괄호 쌍은 교차하면 안된다. 알고리즘 문자열을 차례대로 조사한다 왼쪽 괄호를 만나면 스택에 넣고, 오른쪽 괄호를 만나면 스택에서 가장 최근의 왼쪽 괄호를 꺼내어 맞는 지 확인한다. 이 떄, 스택이 비어있으면 조건1, 조건2 위배 괄호의 짝이맞지않으면 조건3 위배 마지막 괄호까지 조사를 마친 후 스택에 괄호가 남아있다면 조건 1에 위배 구현 #include #include #defi..
-
04. 스택Computer Science/Data Structure 2021. 4. 10. 04:01
4.1 스택이란? 스택 데이터를 차곡 차곡 쌓아올린 형태로 데이터를 추상화하여 자료구조로 정의한 것 연탄을 쌓아올린 모습, 뷔페 접시가 차곡차곡 쌓아올린 모습 과 비슷하다. 특징 같은 구조와 같은 크기의 데이터를 정해진 방향으로만 쌓을 수 있다. top으로 정한 한 곳만 접근 가능하다 후입선출(LIFO) 의 동작구조를 갖는다 : 가장 마지막에 삽입된 데이터가 가장 먼저 삭제 된다 예제 - 시스템 스택을 이용한 함수호출 : 함수는 실행이 끝나면 자신을 호출한 함수로 되돌아 가야하는데, 이때 스택을 사용한다. → 복귀할 주소를 기억하는 데 사용 🤷♀️ 왜 일까요? 함수는 호출된 역순으로 돌아가야 하기 때문! void func2() { return; } void func1() { func2(); } int ..
-
03. 배열, 구조체, 포인터Computer Science/Data Structure 2021. 4. 5. 02:21
3.1 배열 개념 동일한 타입의 데이터를 한 번에 여러개 만들 때 사용하는 자료형 인덱스(index) 번호를 사용하여 여러개 만들 때 사용하는 자료형 특징 연속적인 메모리 할당이 가능하다. index 번호를 이용하여 쉽게 접근 할 수 있다. 1차원 배열 선언 자료형 배열이름[배열 요소의 개수]; int list[3]; 초기화 방법 int list[3] = { 1, 2, 3 }; 2차원 배열 선언 자료형 배열이름[행 요소의 개수][열 요소의 개수]; int list[3][5]; 좌표라고 생각하면 이해하기 편하다. 예를 들면 list[0][0] > (0, 0) , list[2][3] > (2, 3) 3.2 구조체(Struct) 개념 타입이 다른 데이터를 묶는 방법 배열과의 차이점 : 배열은 타입이 같은 데이..
-
02. 순환Computer Science/Data Structure 2021. 3. 24. 01:25
- 학습목표 순환의 개념을 이해한다 순환 알고리즘의 구조를 이해한다 순환 호출 시 주의사항을 이해한다 순환 호출 응용력을 배양한다 2.1 순환의 소개 순환? - 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 기법 순환 알고리즘의 구조 - 순환 호출 하는 부분 - 순환 호출을 멈추는 부분 을 포함한다. 만일, 순환 호출을 멈추는 부분이 없다면, 무한정 호출하게 되어 서버가 다운될 수 있으므로 주의하여야한다. 순환과 반복 순환 recursion: 순환 호출을 이용 - 순환적인 문제에서 유리하다. - 함수 호출의 오버헤드가 있다. -> 순환 호출 시에는 호출이 일어날 때마다 호출하는 함수의 상태를 기억해야하기 때문에 여분의 기억장소가 필요하다. -> 비효율적인 경우가 많음 반복 iteratio..
-
01. 자료구조와 알고리즘Computer Science/Data Structure 2021. 3. 21. 14:02
- 학습목표 자료구조와 알고리즘의 개념을 이해한다 추상 자료형 도입의 필요를 이해한다 시간 복잡도의 개념을 이해한다 빅오 표기법에 의한 알고리즘 분석 기법을 이해한다 자료구조 표기법을 이해한다 1.1 자료구조와 알고리즘 자료구조란? - 사람들이 사물을 정리하여 저장하는 것과 마찬가지로 프로그램에서도 자료들을 정리하여 보관하는 여러 가지 구조들이 있다. 이러한 구조들을 자료구조라 한다. - 예를 들면, 해야할 일들을 중요도에 따른 내용들을 컴퓨터가 이해하려면 순차적으로 진행하는 List를 사용해야한다. 일상생활 자료구조 그릇, 연탄 스택 마트 계산대의 줄 큐 버킷 리스트 리스트 영어 사전 사전 지도 그래프 컴퓨터의 디렉토리 구조 트리 알고리즘이란? - 컴퓨터로 문제를 풀기 위한 단계적인 절차 - 특정한 일..