Marryakirise's coding

문제 Point ✨ bfs 문제에서 상하좌우로 노드를 탐색하고, 최단경로를 찾는문제인데, 이 문제의 포인트는 "1일 때만 이동할 수 있기 때문에 중심이 되는 노드에서 상하좌우로 탐색한 노드가 1이면, 중심이 되는 노드의 최소 칸 수에 1을 더한 값으로 그 탐색한 노드의 값을 바꾼다." 이다. import sys from collections import deque # 최단 경로를 찾는 문제 def bfs(start, end): queue = deque([(start,end)]) visited = [[0] * m for _ in range(n)] visited[start][end] = 1 dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] cnt = 0 while queue: x, y = ..

문제 설계 ✨ 점을 찍는 순서대로 시계방향과 반시계방향을 결정하는 문제이다. 먼저, 점 p1, p2를 지나가는 직선 그래프를 그려서 생각했다. 이 그래프 위쪽 영역에 점 p3를 찍으면 무조건 반시계방향이고, 이 그래프 아래쪽 영역에 점 p3를 찍으면 무조건 시계방향임을 알아냈다. 그래프의 위쪽 점 p3는 점 p1, p2과 삼각형을 만들었을 때 높이가 '+'이고, 그래프의 아래쪽 점 p3는 점 p1, p2과 삼각형을 만들었을 때 높이가 '-'이다. 따라서 세 점의 좌표를 알 때, 삼각형의 넓이를 구하는 공식 (신발끈 공식)을 이용하여 +,- 방향성을 구할 수 있다. import sys # 삼각형 공식 def ccw(p1, p2, p3): return (p1[0]*p2[1] + p2[0]*p3[1] + p3..

문제 설계 ✨ 문제에서 p와 n 범위를 보았을 때 for문으로 하나씩 돌아가면서 풀면 시간초과가 발생할 것으로 파악되었다. 그래서 어떤 방법이 있을까 생각해보다가 dp는 조건에 맞지 않고, 투포인터로 문제를 풀어야하나 고민하던 와중에 R이 2번, 4번, 6번...이면, 원래 배열과 같다는 것을 일단 파악하였다. 그렇다면 R일때 카운트를 증가시키고, D일때 카운트가 홀수이면 뒤에서 빼고, 카운트가 짝수이면 앞에서 빼면 되겠다고 생각하였다. 이 과정에서 deque의 popleft() (앞에서 빼기) , pop() (뒤에서 빼기)을 생각하여 deque를 이용하였다. 또 이 문제에서 중요한 포인트는 예제 입력 중 '[1,2,3,4]'와 같이 입력받는 것을 어떻게 처리하는지이다. input()말고 속도가 더 빠른..

문제 설계 ✨ 처음 수빈이의 위치 N 에서 동생의 위치 K로 가는 최단 시간을 찾는 것이다. 최단 시간을 찾는 것이기에 DFS, BFS를 먼저 생각할 수 있다. 기존 위치에서 이동하는 위치는 3가지 X - 1, X + 1, 2 x X 로 총 3가지가 있다. 즉 노드가 3개로 펼쳐져 나갈 수 있다. 하나의 노드가 얼마나 깊이까지 가는지 모두 확인해서 최단시간을 찾으려면 모든 경로를 다 탐색해야하므로 비효율적이다. 즉 DFS 보다는 BFS 임을 생각한다. BFS로 문제를 풀기로 했으니, 기존 BFS 코드를 작성한다. 다음 노드로 펼쳐져 가는 것이 3가지가 있으니 Queue에 append할 아이템이 3가지이다. X - 1, X + 1, 2 x X 값이 범위를 넘어가지 않도록 조건문을 사용해준다. 방문 위치를 ..

문제 설계 ✨ 힙에 대해서 공부 후에 문제를 풀었다. Heap은 최대값, 최소값을 찾는 연산을 빠르게 하기위해 고안된 완전이진트리를 기본으로 한다. 이 문제는 시간초과 조건이 포함되어있고, 배열에서 가장 작은 값을 찾으라고 하였기 때문에 힙을 쓰는 것이 좋다. 최소 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙 최대 힙: 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙 파이썬에서는 힙 알고리즘을 heapq라는 내장모듈을 import하면 쓸 수 있다. 다음은 heapq의 주요 함수 기능이다. heapq.heappush(heap, item) : item을 heap에 추가 heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexErr..

문제 설계 ✨ 순간이동은 건전지가 사용되지 않지만, 현재까지 온 거리 * 2에 해당하는 위치로 순간이동해야하고, k칸 앞으로 점프하는 것은 건전지가 k만큼 사용된다고 한다. 즉, 이 문제는 최대한 순간이동을 사용해서 얼만큼 점프했는지 알아보는 문제이다. 1. 0부터 주어진 거리를 수직선을 그려놓고 설계했다. 2. 주어진 거리에 있는 곳까지 딱 도착해야하므로 뒤에서부터 생각해보았다. 3. 주어진 거리에서 2로 나누어 떨어지면 점프없이 바로 그 위치로 순간이동을 할 수 있고, 주어진 거리에서 2로 나누어 떨어지지 않으면 2로 나눈 나머지만큼은 점프해야하고, 2로 나눈 몫만큼은 순간이동을 할 수 있다. 4. 출발점에서 최소 한칸을 점프를 해야 현재까지 온 거리가 1이상이 되어서 *2를 했을 때 거리가 계산되므..

문제 설계 ✨ +, - 를 그래프에 넣어야하나 하면서 트리를 구성해봤는데 불필요하게 노드를 많이 추가해야하기 때문에 다른 방법을 생각해보았다. 그렇다면, 값을 누적시키는 방법은 어떨까? 하고 고민하게 되었고, 현재 원소에서 다음 원소를 더한 값을 왼쪽 노드에 넣고, 현재 원소에서 다음 원소를 뺀 값을 오른쪽 노드에 넣는 방식을 떠올리게 되었다. 즉. 트리에서 작대기가 +, - 역할을 하도록 트리를 구성한 것이다. 예제 2번을 설명한 대로 트리로 구현해본 것이다. 루트 노드는 0으로 설정했다. 코드는 해당 값에 다음 값을 더한 값을 큐에 추가하고, 해당 값에 다음 값을 뺀 값을 큐에 추가해서 값을 누적시켜 leaf 노드까지 왔을 때 target값과 일치하는지 확인하는 방식으로 설계했다. 다시 한번 정리하자..

문제 설계 및 코드✨ 가장 먼저 떠올렸던 아이디어는 회전을 위해 큐를 사용하는 것과 괄호가 순서대로 있어야 올바른 괄호 문자열이 된다는 것이었다. 그런데 괄호가 순서대로만 있다고 올바른 괄호 문자열이 되는 것은 아님을 발견했다. [{]} 이런 반례예시가 존재하기 때문이다! 그렇기 때문에 나는 큐와 스택 모두를 사용하는 방식을 선택하였다. 큐를 순회하다가 여는 괄호가 나오면 여는 괄호에 해당하는 닫는 괄호를 스택에 추가, 닫는 괄호가 나오면 스택의 top과 현재 큐 원소와 비교하여 같으면 넘어가고, 아니면 break 하도록 설계했다. 여는 괄호에 해당하는 닫는 괄호를 연결해주기위해 딕셔너리를 사용했다. # 큐사용 # 괄호 순서대로 있을 때 )( X # [{]} 이런 경우는 어떻게? => 스택과 큐 둘다 이..