(7/28) 3일차 - 자료구조(1) 문제

어제와 같이 문제를 풀었습니다. 총 7문제였습니다.

https://bas.ioikorea.cc/problems/list

2022 여름학교 처음반

 

1. 메모장     X

방법자체는 간단합니다. push, pop과 비슷한 명령을 수행하는 메모장을 만드는 것이고 이중연결리스트를 응용하면 됩니다. 다만 아직 오류가 나는 부분을 찾지 못해 해결중입니다.

 

2. 스택     O

스택을 STL을 사용하지 않고 구현하는 문제입니다. 연결리스트를 이용해도 괜찮지만 그냥 배열하나 잡아서 top값 변화시켜주면서 top값을 이동시키면서 push, pop을 해주는 방식으로 풀었습니다.

 

3. 올바른 괄호열    O

정해는 스택을 이용합니다. 여는 괄호라면 소괄호와 대괄호를 구분하여 스택에 push해주고 닫는괄호가 들어왔을 때 스택이 비어있거나 여는 괄호와 닫는 괄호가 맞지 않는다면 틀린 괄호열입니다. 

 

4. 큐    O

2번과 비슷하게 큐를 STL을 사용하지 않고 구현하는 문제입니다. 연결리스트를 사용해도 되고 저처럼 front와 back을 잡고 이동시키면서 push, pop 명령을 수행해주면 됩니다.

 

5. 하노이의 탑     O

하노이의 탑에서 n개의 고리를 A -> B로 옮겨주기 위해서는

     1) n-1개의 고리를 A -> C로 옮긴다

     2) 가장 큰 1개의 고리를 A -> B로 옮긴다

     3) C에 있는 n-1개의 고리를 다시 C -> B로 옮긴다

를 재귀적으로 처리해주면 됩니다.

 

6. 부분 배열 최솟값    O

T개의 테스트케이스에 대해 n의 크기를 가진 배열이 주어지고 k 길이의 부분배열에 대해 최솟값을 모두 출력해야 하는 인터렉티브 문제입니다. deque(덱)을 이용하여 배열을 순차적으로 확인하면서 A[i]에 대해 덱에 존재하는 A[i]보다 큰 원소를 모두 pop_back 해주고 k 길이의 부분배열에 대해 front 에 있는 값이 배열의 최솟값입니다. 다만 순차탐색하면서 k길이의 부분배열보다 더 앞에 있는 원소가 front에 존재한다면 pop_front로 제거해주어야 합니다.

 

7. 집 짓기    X

아직 해결하지 못함. 작성중