Algorithm/concept
Coding Test(Sliding Window)
고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이요해 문제를 풀이하는 알고리즘 ● Brute Force - list slicing 을 이용한 방법 for i in range(len(nums)-k+1): r.append(max(nums[i:i+k])) ● queue을 이용한 방법 (Fast) for i, v in enumerate(nums): window.append(v) if i
Coding Test(Union-Find, Disjoint-set)
유니온 파인드(Union-Find) Disjoint-set(서로소 집합, 분리 집합) 이라고도 하며 순수히 노드 간의 연결 관계를 파악할 때 유용하게 사용 무방향 그래프 내에서의 사이클을 판별할 때 사용(서로의 Root Node가 같다면 사이클 발생) 방향 그래프에서 사이클을 판별할 땐 DFS(DFS타다가 자기자신으로 돌아오면 사이클 발생) 0) Make - 간선이 아직 연결되어있지 않은 그래프에서 모든 값이 자기 자신을 가르키게한다 = > 자기 자신이 부모노드가된다 for(int i=1;i
Coding Test(Priority Queue, Heap)
우선순위 큐(Priority Queue) 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조 - list를 이용한 구현 - heap을 이용한 구현 단순히 N개의 데이터를 heap에 넣었다가 모두 깨내는 작업은 정렬과 동일 == Heap Sort =>O(NlogN) Heap - Max value or Min value을 찾아내는 연산을 빠르게 하기위해 완전 이진 트리를 기본으로한 자료구조 - heap에서는 항상 root node를 제거 최소 힙(min heap) - root node가 가장 작은 값을 가진다 - 값이 작은 데이터가 우선적으로 제거 최대 힙(max heap) - root node가 가장 큰 값을 가진다 - 값이 큰 데이터가우선적으로 제거 완전 이진 트리(Complete Binary T..
Python - 깊은 복사(Deep Copy)
*** BOJ 17488을 풀면서 리스트에 대한 변수 할당에 대해 의문을 가지면서 Deep Copy에 대해 공부해봤다. Immutable(불변) vs Mutable(만변) 파이썬에서의 변수 개념은 저장공간을 할당 받지 않고 객체를 가리키는 포인터 개념이다 C언어에서는 int a = 1을 하면 a변수는 1의 값을 가지며 변수 a와 1은 같은 존재이다. 하지만 파이썬에서 a = 1은 a와 1은 별개의 존재이다. a라는 변수는 Integer 1이라는 객체를 가리키고 있을뿐 변수에 정수 1의 값이 할당 된 것이 아니다. Immutable : 숫자형(Number), 문자형(String), 튜플(Tuple) a = 1 b = a print(a, b) # 1 1 b = 2 print(a, b) # 1 2 Mutabl..
Coding Test(최단 경로 알고리즘)
최단 경로 알고리즘 - 가장 짧은 경로를 찾는 알고리즘 - 각 지점은 그래프에서 노드로 표현 - 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 - 특정한 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 계산 - 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다 - 그리디 알고리즘으로 분류 - 현실 세계에 사용하기 매우 적합한 알고리즘 - 인공위성 GPS S/W에서 많이 사용 1. 출발 노드를 설정한다. 2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다. 3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다. 4. 해당 노드를 거쳐서 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다. 5. 위 과정에서 3~4번을 반복한다...