노는 게 제일 좋아

어렵지 않지만 생각을 잘해야 하는 문제 220227에 다시 풀어보니 생각이 안나는 어려운 문제.. 거의 일년만에 다시 푸네.. ㅋㅋㅋㅋㅋ 값이 확정되는 때가 언제더라 생각하고 있었다. www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 괄호가 나왔으니 스택에 쌓아가면서 할 것이란 것은 예상을 했다. 하지만 또 문제였던 것이 괄호를 닫을 때 이것이 멀리 있는 괄호가 닫히는 것인지 가까이 있는 괄호가 닫히는 것인지 구분을 하지 못한다는 큰 맹점이 생긴다. EX) ..

2022.02.25 다시 풀어보았다. 21년 4월에 풀고 거의 1년만이다. 문제다. www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 물론 살펴보면서 규칙을 찾는 것은 많이 어렵지는 않았다. 스택에 쌓아가면서 생기는 쇠막대기의 개수를 테스트 케이스와 비교해보면서 규칙을 찾았다. 여기서 중요한 것은 스택만 이용하면 안된다. 스택만 이용하면 ()를 처리하는지 멀리떨어져있다가 삭제되어서 ()가 되어서 삭제되는지 알 수 없다. 때문에 나는 다른 방법을 이용했다. 문자열 자체를 ..

물론 생각은 한 번에 났으나 구현이 20분은 걸렸다. www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 처음 문제보면서.. ?? 어떤 자료구조를 쓸까.. 만약 shift를 하면 앞 뒤 둘다에서 삭제 삽입이 일어나는구나. -> Deque를 쓰자. Double ended queue 왼쪽으로 미는 거랑 오른쪽으로 미는 거랑 구분을 해야겠다. **덱을 복사해서 쓰고 이동횟수가 적은 쪽을 다시 원본으로 복사해서 쓰자. -> 다른 방법이 바로 생각안나서 N도 적어서 ..

22.03.01 다시 풀어봄 모든 문제를 기록하긴 좀 그렇고 내가 이해가 한 번에 안된 것들을 다시 이해시키고자 한다. www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제를 보자. 탑을 하나씩 세운다고 생각하자. 탑을 세울 때, 내 왼쪽에 수신할 탑이 없으면 0 수신할 탑이 있으면 해당 수신 탑의 index를 출력하면 되겠다. 5개의 탑 높이를 입력받는다. 6 9 5 7 4 순서대로 탑을 세우자. 위의 방법으로 해결하기 위해서는 왼쪽에 있는 탑들에 대한 ..

이번엔 스택을 알아보자 스택은 First In Last Out으로 삽입과 삭제 연산이 동일한 장소에서 일어나는 자료구조다. 역시 삽입, 삭제 연산에 있어서 상수 시간복잡도를 가진다. FILO구조는 다시 말하면 LIFO구조다. 마지막에 들어온 것이 먼저 나온다는 이야기다. 데이터를 역으로 추적할 때와 같은 상황에 사용한다. 연결리스트와 유사한 자료구조라고도 한다. (연결리스트로 스택 구현가능) 스택 같은 경우에는 중위-후위 변환 재귀함수와 같은 함수 호출 구현 **웹브라우저의 뒤로가기 (페이지기록) 문서 어플리케이션,에디터의 Ctrl + z , undo 기능등과 같은 곳에 쓰인다. 스택은 배열, 동적배열(Vector), 연결리스트로 구현이 가능하다. push(), pop()이 같은 장소에서 일어나고 que..