전체 글
-
Double-Ended QueueDS 2020. 7. 20. 21:14
Deque? 큐는 분명히 한 쪽에만 데이터를 삽입할 수 있다. 괜히 FIFO란 말이 있겠는가. 여기서 확장해서, 양쪽으로 데이터의 삽입과 삭제를 할 수 있게 한 것이 Double-Ended Queue, 줄여서 Deque, a.k.a 'Deck', 덱이다. 덱의 필수요소 Add First e: 덱의 맨 앞에 원소 e 삽입. Add Last e: 덱의 맨 뒤에 원소 e 삽입. Delete First: 덱 맨 앞의 원소 뽑아서 return하고 삭제. 덱이 비어 있으면 에러 return. Delete Last: 덱 맨 뒤의 원소 뽑아서 return하고 삭제. 덱이 비어 있으면 에러 return. First: 덱 맨 앞의 원소를 return. 비어 있으면 error 리턴. Last: 덱 맨 뒤의 원소를 retur..
-
StackDS 2020. 7. 19. 23:37
스택이란? 스택은 자료 구조형의 일종으로, LIFO 형식을 따르는 구조이다. LIFO? 큐와는 반대로, 스택을 설명할 때 가장 많이 쓰는 말 중 하나는 'LIFO'다. LIFO란, Last In First Out이란 뜻이다. 영어 표기법대로, '나중에 들어간 놈이 먼저 나온다'는 뜻이다. 즉 가장 늦게 입력된 원소가 가장 먼저 출력된다는 것을 의미한다. 스택의 필수요소들 스택도 큐와 같이 자료 구조이다. 따라서 자료들을 넣고 뺄 수 있어야 하며, 스택의 상태도 조사할 수 있어야 한다. Push e: 스택의 가장 앞에 원소 e를 삽입한다. Pop: 스택의 가장 앞에 있는 원소를 빼서 return한다. 스택이 비어 있으면 에러를 return한다. Top: 스택의 가장 앞에 있는 원소의 값을 return한다...
-
QueueDS 2020. 7. 19. 02:13
FIFO? 큐를 설명할 때 가장 많이 쓰는 말 중 하나는 'FIFO'다. FIFO란, First In First Out이란 뜻이다. 영어 표기법대로, '먼저 들어간 놈이 먼저 나온다'는 뜻이다. 즉 가장 먼저 입력된 원소가 가장 먼저 출력된다는 것을 의미한다. 큐의 필수요소들 큐는 자료 구조이다. 따라서 자료들을 넣고 뺄 수 있어야 하며, 큐의 상태도 조사할 수 있어야 한다. Enqueue e: 큐에 원소 e를 넣는다. Dequeue: 현재 큐의 가장 앞에 있는 원소를 빼서 return한다. 만약 큐가 비었다면, 오류가 발생한다. First: 현재 큐의 가장 앞의 원소가 뭔지 알려주기만 한다. 빼지 않는다. Empty: 큐에 원소가 하나도 없으면 True, 하나라도 있으면 False를 return한다. ..
-
[Python 3] 백준 2252-줄 세우기BOJ/Topological Sort 2020. 3. 4. 00:04
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다. 학생들의 번호는 1번부터 N번이다. www.acmicpc.net 위상 정렬 위상 정렬은 DAG(Directed Acylic Graph, 사이클이 없는 유향그래프)에서만 성립한다. 정점들을 방향성에 맞게(화살표의 역순이 없도록)정렬한다. 다른 정렬과 다르게 위상정렬은 답이 한 가지가 아닐 수도 있다. 방향성만 만족한다면 어떠한 형태가 나와도 가능하다. 그래프에서 진입 차수(특정 정점을 가리키..
-
[Python 3] 백준 1786-찾기BOJ/KMP 2020. 2. 17. 19:34
https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다. www.acmicpc.net KMP를 그대로 이용하는 문제. KMP 알고리즘 Knuth-Morris-Pratt 알고리즘의 줄임말이다. 입력으로 전체 문자열과 찾고 싶은 문자열을 받는다. 뇌를 비우고 문자열을 확인한다면, 첫 번째 문자부터 끝까지 다 뒤져 보면서 맞는 것을 찾을 수 있겠지만, 전체 문자열의 길이=N, 찾고 싶은 문자열의 길이=M이라 하면 O(NM)이다. 못 써먹는다. 다..
-
[Python 3] 백준 14502-연구소BOJ/BFS 2020. 2. 10. 23:55
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다. 일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. www.acmicpc.net 벽을 세우는 경우의 수는 4만 가지를 넘지 않는다. 따라서 모든 경우에 대해 다 계산해 봐도 OK. 따라서, 벽 3개를 세운 이후, 바이러..
-
[Python 3] 백준 11403-경로 찾기BOJ/BFS 2020. 2. 10. 23:47
https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 우선적으로, 방문했음을 체크하는 2차원 배열 하나를 만든다. 그 이후, 모든 노드로부터 BFS를 실행하면서, 노드 하나를 방문할 때마다 배열에서 그 노드의 위치를 의미하는 위치의 값을 1로 수정한다. 모든 노드에 대해 BFS를 실행하면 결국 모든 노드를 다 방문하게 된다. (deque 쓰면 속도 절감이 가능하다) import sys from collections import deque INF=10**9 N=int(sys.stdin.read..
-
[Python 3] 백준 1644-소수의 연속합BOJ/Sieve of Eratosthenes 2020. 2. 4. 00:11
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 www.acmicpc.net 투 포인터 알고리즘 자연수 배열의 부분합이 원하는 값이 되는 경우의 수를 구하는 알고리즘. 포인터 2개를 만들어 놓고, 조건에 따라 ..