맞왜틀

🤔문제 해결 G2 | 수학, 우선순위 큐 DP로 구해보려고 했지만 역시 아니었다. 2**31 길이의 배열은 좀 아닌거 같다. 어려워서 알고리즘 분류를 보니 우선순위 큐로 해결하는 문제였다. 우선순위큐는 큐 안에 있는 값들 중 최소 값을 반환할 수 있다. 파이썬에서는 힙큐를 불러와서 사용하고 힙큐는 최소힙 기반으로 되어있다. 해결방법은 최초 힙큐에 주어진 소수를 넣는다. 힙큐에서 숫자를 하나씩 꺼내면서 주어진 소수들을 곱해서 힙큐에 넣는다. (이 때 꺼내는 횟수가 소수의 곱들 중에서 N번째 수이다) 하지만 이렇게 되면 중복이 발생한다. ( 2*3 이나 3*2 ) 3*2는 되지만 2*3은 안된다는 식으로 힙큐에서 꺼낸 수가 소수로 나누어 떨어지면 그 다음 소수는 건너뛴다. 결과는 아래와 같다 💻소스 코드 i..

큐 스택과 같이 데이터를 임시 저장하는 자료구조이다. 하지만 스택과 반대로 가정 먼저 넣은 데이를 가장 먼저 꺼내는 선입선출(FIFO: First In First Out) 구조를 가진다.예: 놀이공원에서 보통 줄 서는 구조 큐에 데이터를 넣을 떄는 인큐(enqueue), 큐에서 데이터를 꺼낼 때는 디큐(dequeue) 함수를 정의 데이터를 직접 꺼내는 것이 아니라 두개의 포인터(front, rear) 를 사용해서 위치를 나타낸다. 코드 # 고정 길이 큐 구현하기 with 링 버퍼. # 기존의 리스트로 dequeue 구현 시 시간 복잡도가 O(n) 으로 상당히 비효율적이다. # 이를 해결하기 위해 링 버퍼를 사용. from typing import Any class FixedQueue: class Empt..

🤔문제 해결 G5 | deque, 시뮬레이션 deque 를 이용하여 뱀을 만든다. deque의 앞쪽은 꼬리, deque의 뒷쪽은 머리 (반대로 해도 상관없음) 머리를 방향에 따라 한칸 늘린다.(deque에 머리 추가: append()) 벽에 부딪히지 않고, 뱀의 몸통에 부딪히지 않으면 통과 이 때 머리의 위치에 사과가 있으면 통과 없으면 꼬리를 줄인다.( deque에서 꼬리를 제거: popleft()) 매초 세주면서 해당 초에 오더가 있으면 ( 방향 바꾸기 ) 진행 방향을 바꿔준다. 주의: 사과를 먹으면 맵에서 사과 지우기 💻소스 코드 from sys import stdin from collections import deque input = stdin.readline def move_snake(direc..

🤔문제 해결 G2 | 우선순위 큐 처음에는 가볍게 정렬로 풀었지만, 시간초과가 발생했다. ( 바이너리서치는 통과 된다고 함 ) 가운데 값 구하기를 열심히 찾아봤지만 없었다. 어쩔 수 없다. 이 문제의 의도는 우선순위 큐를 활용하는 것이다. 파이썬의 힙큐 모듈을 사용하면 되는데, 최소힙 기준으로 되어있다. 최소힙은 가장 작은 원소가 루트에 위치하는 것이다. 우리는 가운데 값을 찾아야 하기 때문에 힙을 두개 만들어서 왼쪽의 가장 큰 수와 오른쪽의 가장 작은 수를 비교하여 가운데 값을 구할 것이다. 이렇게 두 부분으로 나누면 가운데 값을 구 할 수 있다. 하지만!!!!!!!!!!! 최소힙으로 힙큐 모듈이 구성되어 있으므로, 왼쪽의 구성은 음수를 붙여서 거꾸로 만들어야한다. 이렇게 하면 왼쪽의 0번과 오른쪽의 ..

스택 데이터를 임시 저장할 때 사용하는 자료구조, 데이터의 입력과 출력 순서는 후입선출(LIFO) 방식이다. 한 쪽 끝에서만 데이터를 넣거나 뺄 수 있는 선형구조로 되어있다.데이터를 넣을 때는 push, 데이터를 꺼낼 때는 pop을 사용한다. 파이썬에서는 보통 스택을 구현하지 않고 리스트로 만들고 append 해서 데이터를 넣거나 pop으로 데이터를 꺼낸다.아래의 코드는 스택을 클래스로 구현해본 것이다. 코드 class Stack: class Empty(Exception): """스택이 비어있을 때 pop 또는 peek 를 수행할 때 예외 처리""" print("야") pass class Full(Exception): """스택이 가득일 때 push 를 수행할 때 예외 처리""" pass def __in..

🤔문제 해결 G5 | 에라토스테네스의 체, 문자열 소수를 찾고, 그게 소수이면 팰린드롬인지 확인한다. 팰린드롬인지 확인하는 법은 간단하다. 문자를 뒤집어서 같으면 True 브루트포스로 찾아도 문제해결은 가능하지만 에라토스를 쓰는것과 시간이 10배 이상 차이난다. 에라토스테네스의 체를 써서 제한 숫자까지 소수들을 구해놓는다. 그 소수이면서 팰린드롬이면 값을 반환하고 끝 💻소스 코드 def make_eratos(l: int) -> list: eratos = [1] * (l + 1) eratos[0], eratos[1] = 0, 0 for i in range(2, l): if eratos[i]: for j in range(i * 2, l, i): eratos[j] = 0 return eratos def is_..