코딩테스트7 우선순위 큐를 이용한 문제 풀이 - 절댓값 힙 구하기 * Do it 코딩테스트를 참고하였습니다. 해당 문제는 배열의 값들 중 가장 절대값이 작은 값을 출력하고, 해당 값을 제거합니다. 해당 절대값이 여러 개일 경우에는 그 중에서 가장 작은 값을 출력하는 문제입니다. 해당 문제는 반복해서 가장 작은 절대값, 그 중에서도 가장 작은 값을 출력하고 제거하는 방식을 가지고 있습니다. 그렇기 때문에 입력 배열에 대한 정렬이 우선적으로 필요하며, 0이 입력될 때마다 앞에서부터 차례로 제거해나가며 출력한다. 이를 구현하기 위해서 우선순위 큐라는 자료구조를 이용하고자 한다. 우선 순위 큐는 일반적인 큐와 다르게 정렬 기준에 따라서 큐 안에 들어있는 값들을 정렬한다는 특징이 있다. 그렇기 때문에 해당 문제에서 주어진 조건에 맞게 정렬을 하며 값을 넣고 빼며 원하는 값들을 .. 2023. 2. 9. 스택을 이용한 문제 풀이 - 오큰수 * Do it 코딩테스트를 참고하였습니다. - 백준 온라인 저지 17298번 문제 해당 문제는 수열 A[i]의 오른쪽에 있는 수 중에서 A[i]보다 큰 수를 찾고, 가장 큰 수 중에서 가장 왼쪽에 있는 값을 찾는 문제입니다. (없는 경우 -1을 출력한다) 해당 문제를 풀기 위해서는 스택을 이용하여야 합니다. 스택에 0번부터 인덱스를 넣고, A[S.top()]의 값이 A[i]의 값보다 작다면 A[i]의 값은S.top()인덱스의 오큰수가 됩니다. 반대로 크다면 오큰수가 아니게 되므로 i를 스택에 Push하여 스택안에 있는 값들에 대한 오큰수를 찾습니다. 마지막까지 스택안에 남아있는 값들은 오큰수가 존재하지 않으므로 해당 인덱스에 대한 출력은 -1을 하면 되는 것입니다. 그럼 코드로 바로 알아보도록 하겠습니다.. 2023. 2. 8. 큐를 이용한 문제 풀이 - 카드 게임 * Do it 코딩테스트를 참고하였습니다. 큐는 FIFO( First - In - First - Out), 선입 선출의 특징을 지닌 선형 자료구조입니다. 해당 문제에서는 이러한 큐의 특성을 이용하여 문제를 보다 쉽게 풀이합니다. 맨 위의 카드는 버리고 두 번째 카드는 뽑아서 맨 뒤로 넣습니다. 이 과정을 큐로 나타낸다면 Pop, Pop (> N; deque deque; for (int i = 0; i < N; i++) { deque.push_back(i + 1); } while (deque.size() != 1) { deque.pop_front(); int temp = deque.front(); deque.pop_front(); deque.push_back(temp); } cout 2023. 2. 8. 스택으로 수열 만들기 * Do it 코딩테스트를 참고하였습니다. - 백준 온라인 저지 1874번 스택은 LIFO (Last - In - First - Out)의 형태를 가진 선형 자료구조입니다. 이 문제는 문제 그대로 스택을 이용하여 수열을 만들어내는 문제입니다. 1부터 시작하는 자연수를 스택에 값을 넣고, 빼내어 입력으로 주어지는 수열들을 출력하는 문제입니다. 우선 문제를 풀기 위해서 스택에 Push/Pop을 하는 조건을 만들어야 할 것입니다. 우선 스택안에 출력해야하는 숫자가 들어있어야 하므로 (수열 값) > top()인 동안에는 스택에 Push를 해주며 +를 출력할 것입니다. 그러다 값이 top()이 되는 순간 Pop을 해주며 -를 해주면 될 것입니다. 수열 값 < top() 인 경우는 pop을 해도 입력값으로 들어온 .. 2023. 2. 8. 이전 1 2 다음