본문 바로가기
728x90

algorithm

[백준알고리즘] 1021번: 회전하는 큐 -Python [백준알고리즘] 1021번: 회전하는 큐 -Python https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다. www.acmicpc.net 저번에는 덱을 c언어로 직접 구현해봤기 때문에 이번에는 그냥 Python으로 풀어봤다. Python에서 제공하는 collections 모듈의 deque을 이용하면 2, 3번 기능인 rotate기능까지 제공하기 때문에 쉽게 문제를 풀 수 있다. 왼쪽 값을 오른쪽.. 더보기
[백준알고리즘] 10866번: 덱 -C [백준알고리즘] 10866번: 덱 -C https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘쨰 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다. www.acmicpc.net 이번 문제는 덱을 직접 구현하는 문제이다. 그래서 문제를 보기 전에는 그냥 파이썬이나 자바로 풀 생각을 해봤는데 오랜만에 링크드 리스트를 만들어 볼 겸 C로 작성을 했다. 일단 링크드리스트를 만들기 위해서 구조체를 만들어 주어야 한다. 구조체 멤버로 data와 링크를 걸 노드들을 가리킬 next, previ.. 더보기
[백준알고리즘] 1966번: 프린터 큐 -Python [백준알고리즘] 1966번: 프린터 큐 -Python https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 문제 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다. 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 www.acmicpc.net 이전에 푼 2164번 문제처럼 큐의 문제를 덱을 사용해서 풀 것이다. 여기서는 P.. 더보기
[백준알고리즘] 11866번: 조세퍼스 문제 0 -Java [백준알고리즘] 11866번: 조세퍼스 문제 0 -Java https://www.acmicpc.net/problem/11866 11866번: 조세퍼스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 큐, 덱에 있는 문제이고, 큐를 이용한 문제라고 나와있는데 굳이 큐를 사용해야 되나? 싶은 문제였다. 여기서 큐의 특징 FIFO가 나타날만한 부분은 일치하는 값을 차례대로 뽑아서 큐에 넣은 후에 마지막에 한 번에 쭉 출력해 내는 것이다. 굳이 사용하고자 한다면, 둥글게 앉은 다음에 예에서 3번째 사람마다 빠진다고 했을 때를 예를 들어보면 다음과 같이 이용이 가능하다. 앉아있는 상태 제외된 상태 ... ... poll 해준 .. 더보기
[백준알고리즘] 2164번: 카드2 -Python [백준알고리즘] 2164번: 카드2 -Python https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 한 장 남을 때까지 반복하게 된다. 우선, 제일 위에 있는 카드를 바닥에 버린다. 그 다음, 제일 위에 있는 카드를 제일 아래에 있는 카드 밑으로 옮긴다. 예를 들어 N=4인 경우를 생각해 보자. 카드는 제일 위에서부터 1234 의 순서로 놓여있다. 1을 버리 www.acmicpc.net 큐를 이용한 문제를 푸는 것이다. 파이썬으로 큐 모듈이 있던 것 같아서 찾던 와중에 쓰기.. 더보기
[백준알고리즘] 17298번: 오큰수 -Python [백준알고리즘] 17298번: 오큰수 -Java https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 오큰수는 오른쪽에서 각 리스트의 요소마다 가장 먼저 나타나는 자신보다 큰 수를 출력하도록 하는 문제이다. 이 값을 구하기 위해서 이중 for문을 돌리면 범위가 넓기때문에 시간초과가 발생한다. 그렇기 때문에 stack을 이용해서 풀어줘야 된다. 그럼 stack에 push하고 pop하는 기준을 알아보자. 먼저 pop을 보면, stack에 element가 존재해야하고 .. 더보기
[백준알고리즘] 1874번: 스택 수열 -Java [백준알고리즘] 1874번: 스택 수열 -Java https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 처음에 문제를 이해하는 데 이상했었다. 문제를 설명하자면 1부터 n까지의 수를 차례대로 stack에 push 하거나 pop 해서 주어진 수열을 만들 수 있는가를 물어보는 문제이다. 이에 대해서 문제를 풀기 위해서는 stack에 push할 때의 조건과 pop 시킬 때의.. 더보기
[백준알고리즘] 4949번: 균형잡힌 세상 -Java [백준알고리즘] 4949번: 균형잡힌 세상 -Java https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 문제 세계는 균형이 잘 잡혀있어야 한다. 양과 음, 빛과 어둠 그리고 왼쪽 괄호와 오른쪽 괄호처럼 말이다. 정민이의 임무는 어떤 문자열이 주어졌을 때, 괄호들의 균형이 잘 맞춰져 있는지 판단하는 프로그램을 짜는 것이다. 문자열에 포함되는 괄호는 소괄호("()") 와 대괄호("[]")로 2종류이고, 문자열이 균형을 이루는 조건은 아래와 같다. 모든 왼쪽 소괄호("(")는 오른쪽 소괄호(")")와만 짝을 이룰 수 있다. 모든 왼쪽 대괄호("[")는 오른쪽 대 www.acmicpc.net Stack문제이지만 문제의 조건들만 잘 맞춰준다면 어렵지 않은 문제이다. 일단.. 더보기
728x90

티스토리툴바