Scribbling

class Solution: def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int: INF = int(1e9) distance = [[INF] * (n) for _ in range(n)] for i in range(n): distance[i][i] = 0 for edge in edges: u = edge[0] v = edge[1] w = edge[2] distance[u][v] = w distance[v][u] = w for k in range(n): for a in range(n): for b in range(n): distance[a][b] = min(distance[a][b], distance[a][k..

최단 거리 알고리즘을 정리해보자. 1. 다익스트라 알고리즘 - 하나의 node로부터 다른 모든 node까지의 최단거리를 계산 가능 - 음의 간선이 없는 경우에만 유효 - O(VlogV) import heapq def dijkstra(start): pq = [] heapq.heappush(pq, (0, start)) distance[start] = 0 while pq: dist_u, u = heapq.heappop(pq) # node u가 이미 처리된 경우 if distance[u] dist_uv + dist_u: distance[v] = dist_uv + dist_u heapq.heappush(pq, (..

다익스트라 알고리즘을 활용하여 푼다. import heapq class Solution: def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int: INF = int(1e9) graph = [[] for _ in range(n+1)] distance = [INF] * (n+1) for time in times: u = time[0] v = time[1] w = time[2] graph[u].append((w, v)) self.dijkstra(graph, distance, k) max_dist = 0 for i in range(1, n+1): max_dist = max(max_dist, distance[i]) if max_dist ..

1. 노가다성 답안 class Solution: def addTwoNumbers(self, l1, l2, up=0): if l1 != None and l2 != None: val1 = l1.val val2 = l2.val val = (val1 + val2 + up) % 10 up = (val1 + val2 + up) // 10 ret_node = ListNode(val=val) ret_node.next = self.addTwoNumbers(l1.next, l2.next, up=up) elif l1 == None and l2 != None: val2 = l2.val val = (val2 + up) % 10 up = (val2 + up) // 10 ret_node = ListNode(val=val) ret_..

XO (1) XO란? XO란 quartz crystal oscillator를 일컫는다. 이는 압력을 가하면 전기가 발생되고 반대로 전기를 가하면 진동을 하는 ‘압전효과’를 이용한다. 즉, 적절한 제어 회로를 통해 크리스탈을 초당 32768회 진동하게 만들 수 있다. 이러한 진동을 감지하여 디지털 회로의 clock 및 RF 회로 내 PLL의 reference clock으로 사용할 수 있다. 이처럼 clock generation에 crystal을 사용하는 이유는 crystal의 정확성에 있다. 특히 PLL같이 매우 정확한 frequency가 요구되는 회로에는 비교적 low frequency에서 정확한 주파수를 생성할 수 있는 기제가 필요하다. 때문에 crystal 기반의 XO는 이에 가장 적합한 것이다. 그..

RACH는 Random Access Channel로, UE가 처음 power on되었을 때 eNB에 보내는 first message에 해당된다. LTE의 RACH를 예를 들어보면, UE가 켜지면 먼저 Frequency Search 과정을 진행한다. 적절한 주파수가 감지될 경우, 해당 기지국과 Time 및 Frame Synchronization 과정을 진행한다. PSS(Primary Sync. Signal) 및 SSS(Secondary Sync. Signal)은 이 과정에서 eNB가 UE에 송신하는 신호이다. UE는 PSS 및 SSS를 수신하여 이를 통해 PCI(Physical Cell Number)를 detect한다. 위 과정이 완료되면, UE는 MIB(Master Information Block) De..

Throughput과 UE Category 1. LTE Throughput (1) LTE Throughput Throughput이란 기본적으로 data rate을 의미한다. LTE 시스템의 Throughput은 대략적으로 아래 식을 통해 계산할 수 있다. 여기서 Transport Block Size(TBS)란 말 그대로 Transport Block의 크기(Block이 몇 Bit를 포함하는지)를 의미한다. LTE TBS는 MCS(Modulation and Coding Scheme)과 Resource Block(RB)의 개수에 의해 결정된다. 여기서 MCS는 LTE 기지국 eNB가 결정하는 것으로, eNB가 단말(UE)에게 어느 정도의 code-rate으로 data를 송출하는지와 관련된다. 즉, eNB와 U..