분류 전체보기 (395) 썸네일형 리스트형 [BOJ] 백준 1021 회전하는 큐 (Swift) 문제 https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 Deque 자료구조를 사용해서 풀 수 있는 문제입니다. n이 최대 50이기 때문에, $O(n)$인 removeFirst, insert 메서드를 사용해서 구현할 수 있습니다. 편의성을 위해 1부터 n까지의 array를 담아주고, 뽑아내려고 하는 수의 위치를 입력받는데, 1부터 n까지 array에 담아주었기 때문에 위치가 아닌 값을 가지고 비교하여도 무방합니다. 모든 수를 뽑아낼 때 까.. [BOJ] 백준 10866 덱 (Swift) 문제 https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Deque 자료구조를 사용해서 풀 수 있습니다. Deque 자료구조를 구현한 후, 명령에 맞게 처리해주면 됩니다. Deque 자료구조에 대해 잘 모른다면, 이 포스팅을 참고하시면 도움이 될 것입니다. https://dev-mandos.tistory.com/195 [자료구조] Deque에 대해 알아보고 구현해보기 (Swift) Deque란? Deque 자료구조는 Queue.. [자료구조] Deque에 대해 알아보고 구현해보기 (Swift) Deque란? Deque 자료구조는 Queue의 특성과 Stack의 특성을 모두 갖는 자료구조 입니다. 왼쪽, 오른쪽 방향으로 삽입 삭제가 가능합니다. 왼쪽으로 삽입 오른쪽에서 삭제, 오른쪽으로 삽입 왼쪽에서 삭제 한다면 Queue 자료구조에 특성일 것이고 왼쪽으로 삽입 왼쪽에서 삭제, 오른쪽으로 삽입 오른쪽에서 삭제 한다면 Stack 자료구조의 특성일 것입니다. 시간 복잡도 삽입 : $O(1)$ 삭제 : $O(1)$ 검색 : $O(n)$ 구현 Deque을 어떻게 구현할 수 있을까요? 연결리스트를 사용하지 않고, Array 2개를 사용해서 구현해보았습니다. Queue를 구현할 때, index를 사용해서 구현한 것 처럼 요소를 가리킬 2개의 index를 두었습니다. 왼쪽이나 오른쪽으로 삽입하는 연산은 어떻.. [BOJ] 백준 1966 프린터 큐 (Swift) 문제 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 Queue 자료구조를 사용하여 풀 수 있습니다. 앞에 있는 문서를 삭제연산을 하고, Queue의 요소들 중 중요도가 가장 높은 문서라면 그대로 삭제해줍니다. 삭제를 해줄 때, 몇개가 삭제되었는지 수를 세주어서 몇 번째로 삭제되었는지 확인할 수 있습니다. Queue의 요소들 중 중요도가 더 높은 문서가 있다면, Queue에 다시 삽입시킨다면 자연스럽게 맨 뒤에 위치하게 됩니다. 중요도가 가장.. [BOJ] 백준 11866 요세푸스 문제 0 (Swift) 문제 https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 풀이 이 문제는 Queue를 사용해서 풀 수도 있고, index를 순회하면서 풀 수도 있습니다. Queue를 사용해서 풀이하면, K-1번 만큼 Queue에서 삭제한 요소를 Queue에 삽입시켜주고 K번째가 될 때, Queue에서 삭제연산을 해주면 K번째 요소를 제거할 수 있습니다. 이 동작을 queue가 빌 때 까지 반복해주면 됩니다. index로 접근은 어떻게 할까요? 초기값은 0번째 인덱스를 가리키고 있고, index에 k - 1을 더해준 위치의 요소를 제거해주면 됩니다... [BOJ] 백준 2164 카드 2 (Swift) 문제 https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 Queue 자료구조를 사용하여 풀이할 수 있습니다. 우선 제일 위에 있는 카드를 바닥에 버리는 행위를 Queue의 삭제 연산으로 볼 수 있습니다. 그렇다면 제일 위에 있는 카드를 맨 밑으로 옮기는 행위를 Queue에서 삭제한 요소를 Queue에 삽입하는 것으로 볼 수 있겠죠? Queue의 크기가 1이 될 때까지, 반복문을 실행해주고 Queue의 마지막 요소를 출력해주면 됩니다. 소스코드.. [BOJ] 백준 18258 큐 2 (Swift) 문제 https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 이 문제는 Queue 자료구조를 사용하면 쉽게 풀리는 것이 맞는데.. Swift에서는 입력과 출력이 느려서 다른분들의 도움을 받아서 풀었던 문제입니다. Queue 자료구조에 대해 모르신다면 이 글을 읽어보시면 도움이 되실 것입니다. https://dev-mandos.tistory.com/190 [자료구조] Queue에 대해 알아보고 구현해보기 (Swift) Qu.. [자료구조] Queue에 대해 알아보고 구현해보기 (Swift) Queue란? Queue 자료구조는 선입선출(First In First Out)FIFO의 특성을 갖는 자료구조 입니다. 즉, 먼저 들어온 것이 가장 먼저 나가는 구조입니다. 맛집에 먼저 줄을 섰던 사람이 먼저 들어가는 것과 동일합니다. 예를 들어 1, 2, 3이란 원소가 Queue에 들어온다면? Queue에 요소들이 이러한 식으로 들어와져 있을 것입니다. pop을 하게 된다면? 1이 가장 먼저 들어왔기 때문에 1이 먼저 나가겠죠? 시간 복잡도 삽입 : $O(1)$ 삭제 : $O(1)$ 검색 : $O(n)$ 구현 Queue를 어떻게 구현할 수 있을까요? Stack을 구현했던 것과 동일하게 Array을 사용해서 구현하려고 해요. 삽입 연산은 Swift의 Array의 append 메서드를 사용할 수 있겠죠? .. 이전 1 ··· 23 24 25 26 27 28 29 ··· 50 다음
