본문 바로가기

분류 전체보기252

[백준][Python 파이썬] 1927번 최소 힙 문제의 원래 의도는 최소 힙(min heap)을 구현하는 것이나, 문제를 푼 방법을 설명하는 코테 등이 아니라면 파이썬에 구현되어 있는 heapq 라이브러리를 쓰면 쉽게 풀 수 있다. heap으로 사용하기 위해서 heap이라는 리스트 변수를 선언했다. heap에 원소를 넣기 위해서는 heapq.heappush(heap변수, 추가할 원소) 를 사용한다. 반대로 heap에서 가장 작은 원소를 빼기 위해서는 heapq.heappop(heap변수)를 사용한다. heapq 라이브러리는 최소 힙으로 구현되어 있지만, 최대 힙으로도 사용할 수 있다. 앞서 heappush 연산을 할 때 추가할 원소의 값을 음수로 넣어주면 양수로는 가장 큰 원소가 가장 작은 원소로 간주되어 맨 마지막에 나오게 된다. import hea.. 2023. 11. 30.
[백준][Python 파이썬] 1966번 프린터 큐 몇 번째로 출력되는지 알아야 할 원소의 초기 인덱스인 M을 사용해서 해당 원소가 현재 몇 번째 인덱스에 있는지를 관찰하였다. M의 경우 매 시행마다 앞으로 한 칸씩 당겨지므로 1씩 값을 제거하면서 그 값을 배열의 길이로 나눈 나머지를 사용하였다. 그래야 M의 값이 원소의 인덱스 범위를 벗어나지 않고 정확히 원소의 위치를 가리킬 수 있다. 또한 cnt 변수를 사용해서 원소를 Q에서 제거하고 출력할 때마다 cnt 값을 1씩 증가시켰다. 매 시행마다 Q(데크)에서 맨 앞의 원소를 뺀 뒤, 해당 원소의 뒤에 있는 원소들 중에서 해당 원소보다 큰 원소가 없으면 해당 원소를 제거했다. 만약 해당 원소보다 큰 원소가 뒤에 있었다면, popleft()로 제거했던 맨 앞의 원소를 다시 append()를 사용해서 배열의 .. 2023. 11. 28.
[백준][Python 파이썬] 1874번 스택 수열 상태 변화를 체크할 변수들을 몇 개 선언하고, 실제로 스택에 수를 넣었다가 빼는 작업을 하면 되는 문제다. 1. queue 변수에는 스택에서 출력해야 하는 변수들을 차례대로 입력받아 넣었다. 2. stack 변수는 실제 스택 역할을 하는 변수이다. 3. maxNum 변수는 스택에 들어갔었던 가장 큰 숫자 값을 저장하는 변수이다. 스택에 push를 할 때는 모든 원소를 오름차순으로 넣어야 하기 때문에 이 값이 필요했다. 4. ops 변수는 스택에서 어떤 연산이 수행되었는지 그 값들을 모으기 위한 리스트 변수이다. queue 변수는 데크 자료형으로 선언해서, 맨 앞에서 원소를 뺄 때도 O(1) 시간에 제거할 수 있도록 했다. 만약 현재 stack에서 출력되어야 하는 원소(queue의 맨 앞에서 빼낸 원소)가.. 2023. 11. 28.
[백준][Python 파이썬] 1764번 듣보잡 파이썬의 딕셔너리 자료구조형은 해시 테이블(hash table)으로 구현되어 있는데, hash table의 경우 일반적인 리스트보다 내부 원소에 더 빠르게 접근할 수 있다. 따라서 never_listen 변수를 리스트로 선언하지 않고 딕셔너리로 선언해서 M번의 루프를 돌 때 해당 이름이 never_listen 내부에 있는 값인지 더 빨리 확인할 수 있도록 하였다. import sys from collections import defaultdict input = sys.stdin.readline N, M = map(int, input().split()) never_listen = defaultdict(lambda: False) never_listen_and_see = [] for _ in range(N):.. 2023. 11. 24.
[백준][Python 파이썬] 11723번 집합 import sys input = sys.stdin.readline N = int(input()) S = set() for _ in range(N): command = input().strip() if command == "all": S = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20} elif command == "empty": S = set() else: cmd, elem = command.split() elem = int(elem) if cmd == "add": S.add(elem) elif cmd == "remove": if elem in S: S.remove(elem) elif cmd == "check": if e.. 2023. 11. 24.
[백준] 1012번 유기농 배추 (Python 파이썬) 배추밭과 심어진 배추 위치 정보를 배열에 저장한 뒤, 배열을 BFS로 탐색하면 된다. BFS나 DFS로 탐색하면 한 위치에서 출발해서 갈 수 있는 모든 점을 탐색할 수 있기 때문에 인접한 배추를 모두 한 번에 구할 수 있다. 다른 문제에서는 이미 탐색한 지점을 구분하기 위해 visited라는 배열을 선언하기도 하지만, 여기서는 이를 구분하기 위해 이미 탐색한 배열 값을 1에서 0으로 바꿔 주었다. import sys from collections import deque input = sys.stdin.readline dx = [0, 0, -1, 1] dy = [-1, 1, 0, 0] def bfs(start_x, start_y): queue = deque([[start_x, start_y]]) arr[s.. 2023. 11. 24.

티스토리툴바