Algorithm

Python Asterisk(*) 사용 용도

곱셉 용도 1 * 2 = 2 2 ** 2 = 4 리스트 확장 test = [1] * 5 test_t = (1,) * 5 print('list {}'.format(test)) print('tuple {}'.format(test_t)) >>list [1,1,1,1,1] >>tuple (1,1,1,1,1) 가변인자 가변인자 : 이름 그대로 길이가 변할 수 있는 argument를 말한다. 임의의 함수에 인자로 몇개의 데이터가 들어올지 모르게 되는 경우 사용하면 편리 이때 여러 api나 잘 짜여진 코드를 구경하다보면 함수에 *args나 **kwargs라고 되있는 표현들 이게 바로 가변인자를 사용하겠다는 의미이다. 한개와 두개의 차이는 positional과 keyward 인자의 차이 def function(a, b..

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번을 반복한다...

Coding Test(다이나믹 프로그래밍)

다이나믹 프로그래밍 - 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 - 이미 계산된 결과는 별도의 메모리 영역에 저장 ==> 메모이제이션(Memoization) TopDown(메모이제이션) : 하향식 BottomUp : 상향식 1. 최적 부분 구조(Optimal Substructure) - 큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제(Overlapping Subproblem) - 동일한 작은 문제를 반복적으로 해결해야 한다. 다이나믹 프로그래밍 vs 분할 정복 - 2개 모두 최적 부분 구조를 가질 때 사용(큰 문제를 작은 문제로 나눌 수 있을 때) - 차이점은 부분 문제의 중복 다이나믹 프로그래밍 : 각 ..

Coding Test(이진 탐색)

순차 탐색 - 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법 이진탐색 - 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 - 시작점, 끝점, 중간점을 이용하여 탐색 범위 설정 - 시간복잡도 : O(logN) # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return ..

Coding Test(DFS/BFS)

스택(Stack) stack = [] stack.append(5) stack.append(2) stack.append(6) stack.pop() stack.append(3) stack.pop() 큐(Queue) from collections import deque queue = deque() queue.append(6) queue.append(2) queue.append(1) queue.popleft() queue.append(7) queue.popleft() DFS (Depth-First Search) - 깊이 우선 탐색, 깊은 부분을 우선적으로 탐색하는 알고리즘 - 스택 or 재귀 함수를 이용 장점: 최선의 경우, 가장 빠른 알고리즘이다. ‘운 좋게’ 항상 해에 도달하는 올바른 경로를 선택한다면, 깊..