큐

[프로그래머스 Lv.3] 가장 먼 노드 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/49189 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이3단계 치고 BFS를 사용하는 문제이기 때문에, 풀이 방법이 익숙해 쉽게 풀 수 있었던 것 같다. BFS처럼 큐를 사용해 그래프를 순회하면서 시작 정점(1번 정점)에서부터의 거리를 계산하고, 이 중 거리가 가장 먼 정점들의 수를 세는 방식으로 간단하게 풀이할 수 있다.from collections import defaultdict, dequedef solution(n, edges): ..

[프로그래머스 Lv.2] 기능개발 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/42586 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr풀이이 문제 유형이 스택/큐 문제라고 지정되어 있긴 하지만, 스택이나 큐를 사용하지 않고 풀이하였다. 문제 풀이 아이디어는 아래와 같다.우선 ceil 내장 함수를 사용해 완료되기까지 걸리는 날짜를 새로운 배열 rests에 저장한다.rests 배열을 순회하며, 현재 인덱스의 이전까지의 최대값(max_time)보다 큰 값이 나타날 때까지의 누적값(cnt)를 키워간다.max_time은 아직까지 ..

(CS) 단일 연결 리스트 vs 원형 연결 리스트, Stack으로 Queue 구현, 원형 큐 구현

단일 연결 리스트 vs 원형 연결 리스트 단일 연결 리스트와 원형 연결 리스트는 연결 리스트의 일종으로, 각 노드는 데이터와 다음 노드를 가리키는 포인터로 이루어져 있다. 데이터를 노드에 저장하고 노드들을 링크로 연결하여 데이터를 관리하는 자료구조이다. 하지만 다음과 같은 차이점이 있다. 단일 연결 리스트(Singly Linked List) 원형 연결 리스트(Circular Linked List) 리스트의 끝은 NULL로 표시 리스트의 순회는 단방향으로만 가능 리스트의 끝은 NULL이 아닌, 첫 번째 노드를 가리키는 포인터로 표시 마지막 노드의 다음 노드는 첫 번째 노드가 되어 원형적인 형태 리스트의 순회는 양방향으로 가능 다음 노드만을 가리키는 포인터만으로 구현되기 때문에 구현이 간단하고 메모리를 적게..

(C++) 백준 10845번 - 큐

문제 링크 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 이전에 Python을 사용해서 풀어보았던 문제이기에 어려움 없이 풀 수 있었다. STL Queue를 사용하여 풀어서 실버 4문제치곤 정말 쉬운 문제라고 할 수 있다. #include #include using namespace std; queue Q; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >..

(Python) 백준 1966번 - 프린터 큐

문제 링크 : https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 풀이 큐와 이차 배열을 사용하여 문제 풀이를 진행했다. 중요도와 문서 번호를 동시에 큐에 담아서 진행하는 것이 풀이의 핵심이라고 볼 수 있겠다. 이차 배열이 아니라 딕셔너리를 사용하여서 풀이하는 것도 가능할거 같다. import sys from collections import deque for _ in range(int(sys.stdin.readline())): n, m = map(i..

(Python) 백준 10845번 - 큐

문제 링크 : https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 Queue의 다양한 메서드들을 구현하는 문제이다. 파이썬의 deque와 sys.stdin.readline()을 통해 시간제한 안에서 여유롭게 통과할 수 있다. 실버 4 문제라기엔 파이썬 코더에겐 상당히 쉬운 문제라고 할 수 있다. import sys # sys.stdin.readline()을 사용해 더 빠르게 입력 받기 가능 from collections imp..

(Python) 백준 2164번 - 카드 2

문제 링크 : https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 처음에는 단순히 list를 사용하여 풀이를 진행하였으나, 시간제한이 2초로 매우 짧아서 log(N)으로 삽입과 삭제를 진행하는 list로는 시간 초과가 발생할 수밖에 없었다. 그래서 상수 시간으로 조회, 삽입, 삭제가 가능한 deque를 사용하여 풀이를 진행하였다. import sys from collections import deque # 1부터 n까지의 카드들을 deque를..