본문 바로가기

Python

 (25)
[Python/Java] 백준 9012번. 괄호 https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 설명: 문자열이 주어졌을 때 주어진 괄호 문자열이 VPS 인지 아닌지를 판단하는 문제이다. 만약 () 으로 계속 맞아떨어진다면 True 이고 )(이거나 (만 있다던가 하면 NO이다. 풀이: flag 설정한다. 디폴트 값은 True 받아온 문자열 split()으로 문자를 확인하여 "("면 스택에 넣는다. 문자가 ")"이면 스택을 확인한다 가장 마지막에 들어간 문자..
[Python] 백준 1795번. 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 문제: 주어진 문자를 가지고 L자리 비밀번호를 조합하여 비밀번호를 풀려고 한다. 주의 할 점은 비밀번호 조합에는 최소 하나의 모음과, 최소 두개의 자음을 포함하고 있어야 한다. 문자가 4개 만들어지면 반환하도록 한다. 입력받은 문자열은 정렬이 되어야 한다. 출력결과를 보면 문자가 오름차순으로 정렬이 된 것으로 보인다. 결국 첫번째 자리 < 두번째 자리 < 세번째 자리 < 네번째 자리순으로 정렬되어야 한..
BFS(너비 우선 탐색) 스택을 이용하는 DFS와 달리 BFS는 반복 구조를 구현할 때 큐를 사용한다. 재귀로 구현 불가 큐를 이용하는 반복구현만 가능하다. graph = { 'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'G', 'H', 'I'], 'D': ['B', 'E', 'F'], 'E': ['D'], 'F': ['D'], 'G': ['C'], 'H': ['C'], 'I': ['C', 'J'], 'J': ['I'] } BFS 구현(큐 2개 사용) visited = deque() need_visited = deque() need_visited.append(list(graph.keys())[0]) 첫번째 키 값인 'A'를 먼저 방문이 필요한 큐에 넣어준다. while need_visited:..
[Python] 백준 17219. 비밀번호 찾기 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제가 직관적이라고 생각한다. 웹사이트에 맞는 비밀번호를 찾는 것이다. dict을 이용하면 쉽게 풀릴 문제라고 생각해서 dict으로 한 번 풀어본다. * 딕셔너리를 만들때 컬렉션에 나와있는 defaultdict 함수를 사용해보겠다. pwbook = collections.defaultdict(str) * 웹사이트와 비밀번호를 입력을 받을때 딕셔너리에 없다면 값을 추가해..
[Python] 백준 1966번. 프린터 큐 https://www.acmicpc.net/problem/1966 1966번: 프린터 큐 여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 여러 개의 문서가 쌓인다면 Queue 자료구조에 www.acmicpc.net 문제 설명: 우선순위가 가장 높은 순서인 게시물이 가장 앞에 있으면 꺼내준다. 이때 카운터를 해줘야 한다. 만약 우선순위가 높지 않은데 가장 앞에 있다면 뒤로 보내준다. 내가 찾아야 할 우선순위가 나오면 카운터를 증가해주고 꺼내준다. 처음 헤맨것은 왜 이렇게 입력을 받는거지? 가장 처음 몇 개의 case인지 알았고 1 0 -> 한장의 카드가 있고 0번째에 놓여있는지를 나타내고 있다. 그 이후로 이해가..
[LeetCode] Design Circular Queue(원형 큐 디자인) https://leetcode.com/problems/design-circular-queue/description/ Design Circular Queue - LeetCode Can you solve this real interview question? Design Circular Queue - Design your implementation of the circular queue. The circular queue is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle, and the leetcode.com int Front() : 맨 앞 항목을 가져옵니다. 대기..
[LeetCode] Implement Stack using Queues(큐를 이용한 스택구현) https://leetcode.com/problems/implement-stack-using-queues/description/ Implement Stack using Queues - LeetCode Can you solve this real interview question? Implement Stack using Queues - Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty). Implement the leetcode.com void push(int x)..
[Python]Deque Deque * 앞과 뒤에서 데이터를 처리할 수 있는 양방향 자료형 * stack(스택)처럼 써도 되고 queue(큐)처럼 써도 된다. * from colections import deque 추가해서 사용하면 된다. Deque 시간복잡도에 관해 Python 리스트와 Deque의 차이 * List 시간 복잡도 Average Case Amortized Worst Case Copy O(n) O(n) Append[1] O(1) O(1) Pop last O(1) O(1) Pop intermediate[2] O(n) O(n) Insert O(n) O(n) Get Item O(1) O(1) Set Item O(1) O(1) Delete Item O(n) O(n) Iteration O(n) O(n) Get Slice O..

티스토리툴바