내 맴

문제 ) https://www.acmicpc.net/problem/5430 5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. www.acmicpc.net [ 풀이 ] AC연산에 대한 알고리즘을 설명하기 전에 이 문제는 입력과 출력의 형식이 정해져있기 때문에 입력과 출력 방식에도 신경을..

문제 ) https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net [ 풀이 ] 문제 이해를 하는 것이 제일 우선! 문제 이해를 위해 Algorithm의 Flow를 작성해보았다. 예제 2번에 대한 flow이다 뽑아내려는 원소의 위치가 queue의 중간위치보다 ✔ 왼쪽에 위치하면 왼쪽으로 원소들을 이동시키는것이 더 편리할 것이고 → Leftmove Function ✔ 오른쪽..

문제 ) https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net [ 풀이 ] ✔ Deque에 대한 문제! Array의 양쪽에서 입출력이 모두 가능한 자료구조 저번에 풀었던 큐 문제를 참조해서 코딩하였다. (코드가 겹침) https://luz0911.tistory.com/108?category=765467 [ BAEKJOON ] No. 18258 큐2 문제 ) https://www.acmicpc.net..

문제 ) https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 www.acmicpc.net [ 풀이 ] list의 M번째 숫자가 몇번째로 출력되는지 알아내야함으로, M번째 숫자의 위치를 알려주는 check라는 list..

문제 ) https://www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net [ 풀이 ] 1. (k-1)번째 까지의 수는 queue에다가 append해준다 2. k번째 수는 pop해서 queue에서 없애주고 result 에 넣어주는 것을 3. queue안의 원소가 하나 남을 때 까지 반복 4. queue안의 원소가 하나일때 마지막 하나 남은 원소도 result에 넣어준다 Ex ) (7 , 3) 요세푸스 순열의 경우 → queue= [ 1, 2, 3, 4, 5, 6, 7 ] 순서 제거되는 수 queue result 1) 3 [ 4, 5, 6, 7, ..

- Fractional Knapsack n개의 물건과 1개의 배낭이 있다 물건 i의 무게는 W(i), 이익은 P(i), 배낭용량은 M까지 가능하다 물건들을 배낭에 섞어서 넣되, 무게가 M을 넘지 않으면서 이윤이 최대가 되도록 물건을 담는 방법? (물건을 잘라서 담을 수 있다) 예시 ) 이익, 무게 등 무엇을 기준으로 잡고 greedy algorithm을 수행할지에 따라 결과가 다르다. 그러나 Fractional Knapsack 문제에서는 물건의 무게당 이익이 큰것을 기준으로 잡고 Algorithm을 짜면 항상 최적의 이익을 얻을 수 있다. 단, 단위 무게 당 이익이 큰 순서대로 정렬이 되어있어야만 하며, 정렬이 되어있다면 Time complexity는 O(n)이 된다 그러므로 최대 이익은 31.5가 된다..

문제 ) https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net [ 풀이 ] ✔ Queue을 사용해서 문제를 풀어준다 : FIFO ( First In First Out ) 를 따르는 자료 구조 ..

문제 ) https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net [ 풀이 ] ✔ Queue을 사용해서 문제를 풀어준다 : FIFO ( First In First Out ) 를 따르는 자료 구조 먼저 집어넣은 data가 먼저 나온다. 저번에 풀었던 스택 문제를 참조해서 코딩하였다. (코드가 겹침) https://luz0911.tistory.com/101?category=765467 [ BAEK..