코딩테스트11 기수 정렬을 이용한 문제 풀이 - 수 정렬하기 * Do it 코딩테스트 책을 참고하였습니다. - 백준 온라인 저지 10989번 문제 해당 문제는 10000보다 작거나 같은 자연수들의 배열을 오름차순으로 정렬하는 문제이다. 줄의 개수가 광범위하기 때문에 단순하게 정렬을 하기 위해서 sort() 메소드를 사용하거나 효율이 좋지 않은 정렬법을 사용하게 되면 시간 초과로 인해서 제한시간안에 값을 구해내지 못하게 된다. 그렇기 때문에 해당 문제를 풀기 위해서는 값들을 어떤 정렬을 이용하여야 효율적으로 풀 수 있는지 알아내는 것이 중요하다. 문제에서 주어지는 수들은 앞서 말한 것과 같이, 10000보다 작거나 같은 자연수들이다. 그렇기 때문에 1부터 10000까지 각 숫자가 몇개 있었는가? 라는 아이디어를 통해서 풀 수 있다. 해당 개념이 바로 기수 정렬이다... 2023. 2. 20. 우선순위 큐를 이용한 문제 풀이 - 절댓값 힙 구하기 * 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. 이전 1 2 3 다음