내 맴

문제 ) 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)이 된다 그러므로 최대 이익은..

문제 ) 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..

문제 ) https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이뤄야 한다. 모든 왼쪽 대괄호("[")는 오른쪽 대괄 www.acmicpc.net [ 풀이 ] ✔ Stack을 사용해서 문제를 풀어준다 1 ) 문장 전체를 for문을 통해 한글자씩 확인 한다 2 ) ✔ 문..

문제 ) https://www.acmicpc.net/problem/9012 9012번: 괄호 문제 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 부른다. 한 쌍의 괄호 기호로 된 “( )” 문자열은 기본 VPS 이라고 부른다. 만일 x 가 VPS 라면 이것을 하나의 괄호에 넣은 새로운 문자열 “(x)”도 VPS 가 된다. 그리고 두 VPS x 와 y를 접합(conc www.acmicpc.net [ 풀이 ] ✔ stack을 사용해서 문제를 풀어주기 또한 , ' ( ' 는 -1이라고 하고 , ' ) ' 는 1이라고 설정하고 문..

[ 문제 ] https://www.acmicpc.net/problem/10773 10773번: 제로 문제 나코더 기장 재민이는 동아리 회식을 준비하기 위해서 장부를 관리하는 중이다. 재현이는 재민이를 도와서 돈을 관리하는 중인데, 애석하게도 항상 정신없는 재현이는 돈을 실수로 잘못 부르는 사고를 치기 일쑤였다. 재현이는 잘못된 수를 부를 때마다 0을 외쳐서, 가장 최근에 재민이가 쓴 수를 지우게 시킨다. 재민이는 이렇게 모든 수를 받아 적은 후 그 수의 합을 알고 싶어 한다. 재민이를 도와주자! 입력 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ www.acmicpc.net [ 풀이 ] 입력된 숫자가 0인 경우 가장 최근 값을 빼와야하기 때문에 stack을 사용하여 문제를 해결하였다. 입력받은 숫자..