자료구조2 2강 자료구조 1 - 연습 이번 강의는 지금까지 배운 자료구조의 연습문제를 풀어보는 시간을 갖도록 한다. 주로 스택을 다루는 문제를 풀어본다고 한다. 이 문제는 단어 뒤집기 문제와 비슷하지만 다른 점은 태그가 있다는 점이다. 태그 안에 있는 단어는 뒤집지 않고 밖에 있는 단어만 뒤집어준다. 그래서 단어 뒤집기 문제에서 태그 판단만 추가를 해주고 나머지는 거의 동일하게 구현하면 된다. 이 문제의 Worst case는 모든 단어가 스택에 추가되는 경우이기 때문에 시간 복잡도는 문자열의 길이가 N이라고 할 때, O(N)이 된다. 조금 헷갈리긴 했는데 출력, tag가 true면 뒤집지말고 그대로 출력, 아니면 공백이 아닌 경우에는 스택에 단어 넣어두고 공백이면 스택 출력. 이렇게 하면 된다! 1 2 3 4 5 6 7 8 9 10 11 1.. 2020. 8. 16. 2강 자료구조 1 - 스택 자료구조 1 강의에서는 크게 스택, 큐, 덱에 대해 배우는데 스택을 주로 다루고 큐와 덱은 그래프(BFS)에서 자세하게 다룬다고 한다. 스택(Stack)이란 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조이다. LIFO(Last in First Out)라고도 부른다. 그래서 나중에 들어간 데이터가 제일 먼저 나올 수 있다. 위의 그림처럼 스택은 한쪽 끝에서만 자료를 넣고 뺄 수 있는 자료구조로 마지막으로 넣은 것이 가장 먼저 나오기 때문에 LIFO라고 한다. 따라서 만약 데이터를 저장하고 가운데에 저장한 데이터를 pop해야 하는 연산이 필요하다면 이는 스택을 사용하면 안되는 알고리즘이다. 다음은 스택 연산이 종류이다. - push : 스택에 자료를 넣는 연산 - pop : 스택에서 자료를 빼는 연산 - .. 2020. 8. 9. 이전 1 다음
