개발32 [백준 2493][C++] 탑 이 문제에서 배운 것들 정리 시간복잡도 계산 내 코드의 경우 N 개의 입력에 대해서 O(N^2)인 것은 맞는 것 같다. (빅 오 표기법의 경우 최악의 경우를 따지므로) 하지만 실제로 이런 케이스는 N개의 입력 각각이 모두 N^2번의 연산을 하는것이 아니기 때문에 테스트 케이스를 통과하는 것이 아닐까 싶다. 모든 입력이 N^2번의 연산을 하지 않는 이유는 스택에서 삭제하는 연산 때문에 검사해야할 스택 크기 자체가 줄어들기 떄문이다. 알고보니 O(N)짜리 코드였다. 스택에 넣고, 삭제하는 연산을 N번 만큼 하기 때문!! 유의할 점은 이중 반복문이라고 해서 N^2이라고 생각하면 안된다는점. 참고 링크 : https://www.acmicpc.net/board/view/9807 글 읽기 - 탑 문제 - 시간복잡도.. 2020. 1. 23. [백준 10799][C++] 쇠막대기 굳이 스택을 이용하지 않고 문자열만 다루어서 풀 수도 있는 문제였다. 여는 괄호는 일단 스택에 넣어준다. 그리고 닫는 괄호를 기준으로 생각해 보면, ( ) 처럼 연달아서 여는 괄호, 닫는 괄호가 나올 경우 레이저를 뜻하고, ) ) 처럼 닫는 괄호들이 이어진다면 이는 막대기의 끝 부분을 의미한다. 레이저의 경우는 현재 스택의 크기만큼의 조각이 생기고 (18번째 줄) , 막대기의 끝 부분일 경우 해당 막대기의 끝 부분, 즉 1개의 조각이 더 생긴다. (20번째 줄) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include #include #include using namespace std; int main() { stack pipes; .. 2020. 1. 23. 이전 1 ··· 3 4 5 6 다음
