본문 바로가기

전체 글95

[python 구름] 폭탄 구현하기 📜 접근 방법 인접하는 좌표 즉, 상하좌우를 계산하는 배열을 만든다 (dx, dy) 리스트로 현재 주어진 땅덩어리?를 만든다 ground 주어지는 값이 k 만큼이므로 k번 반복한다. 입력 받은 x, y에 대해 ground[x][y] 위치에 + 1 해준다. 상하좌우를 확인하여 유효할 경우 +1을 해준다. ground에 주어진 숫자들을 더한다. ❌ 실패 코드 x와 y에 -1씩 해주는 것을 처음에 하지 않았다. ✅ 정답 코드 # from pprint import pprint import sys input = sys.stdin.readline # 상하좌우 dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] n, k = map(int, input().split()) ground = [([0] * .. 2023. 5. 11.
[python 구름] 0커플 📜 접근 방법 짝수인 n이 주어지며, n만큼 숫자가 들어오는데 짝이 아닐 경우 그 숫자를 더해야한다. 짝일 경우는 두 수를 더했을 시 0이 되어야한다. 우선순위 큐를 사용했고, 두 수를 더했을 때 0이면 결국 -k 와 k를 더했을 경우 0이 되기에 2개의 힙을 사용했다. (양수 넣는 힙과 음수 넣는 힙) 입력받은 숫자들을 2개의 힙중 하나의 힙에 구분하여 넣는다. 두개의 힙중 하나라도 비어지면 반복문 종료한다. 짝이 아닐 경우 둘중 절대값이 작은 수를 res에 넣는다. (res는 짝이 없는 수들의 리스트) / 반복 반복문이 종료되면 힙에 남는 값들을 전부 res에 넣어준다. res에 들어간 값들의 합을 출력 ✅ 정답 코드 from heapq import heappop, heappush import sys.. 2023. 5. 10.
[자료구조] 우선순위 큐(Priority Queue) 우선순위 큐(Priority Queue) 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 자료구조 사용 용도 물건 데이터를 자료구조에 넣었다가 가치가 높은 물건부터 꺼내서 확인해야하는 경우 특징 힙(heap)을 이용한 구현 방법 루트 노드엔 우선순위가 높은 값이 들어간다. 힙에서는 항상 루트 노드를 제거한다. 힙은 완전 이진 트리 형태로 구성되어있다. import sys from heapq import heappush, heappop input = sys.stdin.readline n = int(input()) heap = [] for i in range(n, 0, -1): heappush(heap, i) print('-' * 15, 'heappop', '-' * 15) for i in ra.. 2023. 5. 10.
[알고리즘] 소수 판별 : 에라토스테네스의 체 하나의 수가 소수인지 판별할 때는 간단하게 아래와 같이 짤 수 있다. # n : 소수인지 판단할 숫자 is_prime = 1 for i in range(2, n): if n % i == 0: is_prime = 0 소수를 여러번 판별할 경우 에라토스테네스의 체를 사용하는 것이 효율적이다! 10^12 의 큰 수를 소수 판별시 위의 방법 사용 10^6 이하의 모든 소수를 구할때는 에라토스테네스의 체를 활용!! 에라토스테네스의 체 시간 복잡도 O(nloglogn) 어떤 수가 소수가 아닌지를 판정하는 방식으로 동작 2부터 순서대로 그 수가 소수이면 그의 배수들을 모두 소수가 아님! 예시 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 .. 2023. 5. 9.

티스토리툴바