문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경우 해당 수를 쓴다. 정수가 "0"일 경우에 지울 수 있는 수가 있음을 보장할..

2022.04.22 - [C++/자료구조] - 스택(stack) - 2 배열을 이용한 스택 구현 스택에서 PUSH와 POP 연산은 탑에서 일어난다. 그림은 배열에서의 PUSH와 POP연산을 그림으로 표현한 것이다. 코드 구현 //array stack.h #define ARRAY_SIZE 100 typedef int element; //int형 자료형에 element라 별칭 붙임. class ArrayStack { public: ArrayStack(); ~ArrayStack(); void Push(element item); //item값을 스택에 삽입 int Pop(); //스택 탑의 데이터 값을 리턴함 bool IsEmpty(); //비어 있는지 확인 bool IsFull(); //꽉차 있는지 확인 pr..

2022.04.22 - [C++/자료구조] - 배열을 이용한 스택 구현 연결 리스트를 이용한 스택 구현 위에서는 스택을 배열을 이용하여 구해보았다. 스택은 아래와 같이 연결리스트를 이용하여도 구현할 수 있다. 이러한 스택을 linked stack이라고 한다. 장점: 크기가 제한되지 않는다 단점: 동적 메모리 할당이나 해제를 해야 하므로 삽입이나 삭제 시간이 좀 더 걸린다. 각각 파란색으로 표시된 할당된 공간을 노드라 한다. 노드엔 data 값과 다음 노드의 주소값을 가리키는 포인터가 들어 있다 그림은 linked stack의 PUSH와 POP연산을 그림으로 표현한 것이다. . PUSH POP 삽입 연산에서는 먼저 동적 메모리 할당으로 노드를 만들고 이 노드를 첫 번째 노드로 삽입한다. 삭제 연산에서는 t..

2022.04.18 - [C++/자료구조] - 스택(stack)-1 스택(stack)-1 스택(stack) 후입선출(LIFO: Last-In First-Out)한다. 다음처럼 스택에 A,B,C를 순서대로 입력했다가 하나를 삭제하면 맨 위에 놓여진 C가 삭제되고 다시 삽입하면 맨 위에 D가 놓여진다. 스택의 구조 스택 shine-learn.tistory.com 앞 내용 요약 스택 -> 후입선출(LIFO), 스택의 바닥부분을 bottom, 스택의 윗부분을 top이라 한다. 스택에 저장되는 것을 element라 한다. 스택의 연산 스택의 각 연산은 간단하게 구현할 수 있다. stack-empty stack push stack pop stack-empty > 스택이 비었다면 True, 비어있지 않다면 false..

2022.04.10 - [C++] - 예외처리 #include using namespace std; int fact(int ); int main(void) { int n; cin>>n; try { cout

정렬된 배열의 탐색에서 사용한다. 배열의 중앙아 있는 값을 조사하여 찾고자하는 값이 중앙값보다 큰지 작은지를 판단한다. 만약 크다면 찾고자하는 값은 중앙값보다 오른쪽에 있는 것이고, 작다면 중앙값보다 왼쪽에 있는 것이다. 예를 들어 배열{1,2,3,4,5} 가 있을 때, 찾고자하는 값이 2라면 중앙값 3보다 작으므로 왼쪽에 있다. 이렇게 탐색의 범위를 반으로 줄일수 잇고, 이러한 방법에 의해 매 단계에서 검색해야할 리스트의 크기를 반으로 줄인다. 다음은 이진탐색이 성공한 경우이다. 만약 다음과 같이 배열안에 찾고자하는 원소가 존재하지 않는다면 탐색은 실패한다. 아래는 이진탐색을 C++로 구현한 예이다. #include using namespace std; #define ARRAY_SIZE 10 int m..