CS
[BaekJoon]백준 2493번 탑
[BaekJoon]백준 2493번 탑 문제: https://www.acmicpc.net/problem/2493 내코드 - 처음엔 정석대로 모든 입력값을 stack에 넣어서 top부터 차례대로 밑에것들이랑 비교하려고함. 그렇게 하면 더 복잡하단걸 깨달음. - stack과 pair를 이용함. stack에는 차례대로 입력을 받고, pair에는 입력값과 index값을 순서대로 저장함. - n개의 탑이 있을때 가장 왼쪽에 있는 것부터 차례대로 입력을 받음(ex. 69574) - 우선 첫번째 6이 들어왔을때 stack이 비어있는지 확인하고 비어있으니 0 출력, 출력후 (1, 6) pair로 stack에 쌓음. - 두번째 9가 들어왔을때 stack이 비어있는지 확인하고 안비어있으니 while문으로 들어가서 top의 ..
[Baekjoon]백준 2504번 괄호의 값
백준 2504번 괄호의 값 문제: https://www.acmicpc.net/problem/2504 내코드 - A(B+C) = A*B + A*C 를 활용 - 변수 mul에 곱해야 하는 값을 저장해두고 (가 추가되면 *2, [가 추가되면 *3을 해줌 - ), ]가 나오면 두가지로 나눠서 생각 - 앞에가 (,[이면 바로 숫자로 바꿔서 mul값을 곱해준후 pop, 그 후 위에서 곱해준 2, 3의 값을 나눠준후 다시 밑에서 () = 2, [] = 3 값을 곱해줘야하니 별다른 처리 안하고 sum += mul; - 앞에가 (,[이 아니면 error체크만 해준뒤 pop해준 후 mul값을 2,3으로 다시 나눠줌. - 만약 스택이 비어있으면 괄호가 닫힐수가 없으므로 error - input 값에서 i가 ), ]일때 i-..
[BaekJoon] 백준 10799번 쇠막대기
[BaekJoon] 백준 10799번 쇠막대기 문제: https://www.acmicpc.net/problem/10799 내코드 - '('가 들어오면 stack에 push해준다. - ')'가 들어오면 바로 앞이 '('인 경우 레이저 임으로 stack에 쌓인 값을 result에 더해주고 바로 앞이 ')'인 경우 막대기 이므로 result++ 해준다. #include #include using namespace std; int top = 0; int result = 0; int main(void) { ios::sync_with_stdio(false); cin.tie(0); string arr; cin >> arr; int n = arr.length(); for (int i = 0; i < n; i++) { ..
[BaekJoon]백준 9012번 괄호
[BaekJoon]백준 9012번 괄호 문제: https://www.acmicpc.net/problem/9012 내코드 -엄청 간단한문제였다. -stack을 이용해서 '('인경우 push해주고 ')'인 경우 pop을 해줘서 -pop을 해줘야하는데 top의 값이 -1이거나 -testCase가 끝났는데 stack안에 아직 값이 남아있어서 top이 -1이 아닌경우 -NO를 출력해줘야한다. #include #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(0); int testCase; cin >> testCase; while (testCase--) { int stack[100]; int top = -1; str..
[BaekJoon]백준 5430번 AC - C++, Python
[BaekJoon]백준 5430번 AC 문제: https://www.acmicpc.net/problem/5430 내코드 -처음에 문자열 파싱하는 부분이 어려웠다. -[1,2,3] 이렇게 주어졌을때 1, 2, 3을 deque에 넣어야했다. -헷갈렸던 부분은 숫자가 두자리 숫자가 주어질 수도 있었다는것. -','를 만나면 tmp를 deque에 push_back 시켜주고 tmp를 0으로 초기화 시켜주고, ','이 아닌경우 10의 자리수인경우 해당값을 tmp에 넣어주고, 1의 자리수인경우 (tmp에 들어있는 10의 자리수 숫자 * 10 + 1의 자리수 숫자)를 해줬다. -그외에는 크게 어려운 부분이 없었다. -R이 나왔을때는 숫자 배열이 뒤집어졌다는 표시로 bool 변수 back = true;를 시켜주고 출력할..
[BaekJoon]백준 1021번 회전하는 큐
[BaekJoon]백준 1021번 회전하는 큐 문제: https://www.acmicpc.net/problem/1021 내코드 -처음에 자료구조 선택할때 배열(자유로운 원소 삽입/삭제가 힘듬), stack, queue(양방향 삽입/삭제 불가) 등의 이유와 함께 자료구조에서 양방향 이동이 있는 문제라는 것을 알고 deque을 사용 -풀이의 기본틀 -> pop해야하는 원소의 위치를 구해서 -> 만약 left쪽으로 이동하는 경우 연산 횟수 & 만약 right쪽으로 이동하는 경우 연산 횟수를 구해서 더 작은 수를 선택한다 -> 만약 left쪽으로 이동하는 경우 front의 원소를 back에 push_back해주면서 pop_front해준다. 즉, 한칸씩 이동해준다. -> 이동이 완료되면 주어진 수를 pop_fro..
[BaekJoon] 백준 1874번 스택 수열
백준 1874번 스택 수열 문제: https://www.acmicpc.net/problem/1874 내코드 문제 풀이 (1-1) max값(현재 입력값중 최대값, 초기값은 0)이 입력값 보다 작으면 (max+1) ~ 입력값까지 push해준다. (1-2) 크거나 같은 경우 pop을 해줘야 하므로 스택의 top이 입력값과 같은지 체크한다. 같지 않을 경우 NO를 출력하며 프로그램 종료. (2) pop을 해준다. (3) max값이 입력값보다 작으면 max값을 입력값으로 초기화 해준다. 주의점 - endl 는 버퍼를 비우기 때문에 느림. 시간초과가 남. "\n"을 써주자. #include #include using namespace std; int stack[100000]; int top = 0; char * r..
[Algorithm] 덱 (Deque)
[Algorithm] 덱 (Deque) 덱 (Deque) -정의 Double-ended Queue의 약자로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조. -연산/함수 (1) push_front(item) : item을 덱의 앞에 넣는다. (2) push_back(item) : item을 덱의 뒤에 넣는다. (3) pop_front() : 덱의 가장 앞에 있는 item을 반환하며 삭제한다. (4) pop_back() : 덱의 가장 뒤에 있는 item을 반환하며 삭제한다. (5) front : 덱의 가장 앞에 있는 item을 반환한다. (6) back : 덱의 가장 뒤에 있는 item을 반환한다. -특징 (1) 스택의 특징과 큐의 특징 모두 가지고 있음 -시간복잡도 (1) 원소 추가: O(1) (2) 원..