작은개발자

정렬 알고리즘 n개의 원소를 기준에 맞게 열거하는 알고리즘 구현이 간단한 경우는 시간복잡도가 비효율적 시간 복잡도가 효율적인 경우는 구현이 복잡함 1. 버블/거품 정렬 (Bubble Sort) 서로 인접한 두 원소의 대소를 비교 및 교환 구현이 쉽고 간단하지만 효율이 좋지 않다. 시간 복잡도 평균 시간 복잡도는 $O(n^2)$ 비교 한번의 순회를 마칠 때 마다 비교 대상이 하나씩 줄어든다. 전체 원소의 개수가 n이라고 하면 n-1번 순회를 하면 정렬이 끝난다. 위 그림에서는 원소의 개수가 5개이므로 4+3+2=10번의 비교를 하게 된다. 일반화 수식은 아래와 같다. $$(n-1)+(n-2)+...+2+1 = {n*(n-1)\over2}$$ 자리 교환 최선의 경우: 자리 교환이 한번도 이루어 지지 않기 때..

다익스트라는 세마포어의 아버지시죠 - YG 최단 경로 알고리즘 다익스트라 알고리즘은 그래프의 특정 지점에서 다른 지점까지 최단 경로(효율적인 경로)를 구하는 알고리즘으로, 각 지점은 그래프에서 노드로 표현하고 지점 간 연결된 도로는 그래프에서 간선으로 표현한다. 그래프 알고리즘에서 대표적인 최단경로 알고리즘으로 다익스트라, 벨만-포드, 플로이드-워샬이 있는데, 다익스트라 알고리즘은 간선의 가중치가 하나라도 음수면 사용할 수 없다는 특징을 가지고 있다. (가중치가 음수일 경우 벨만-포드 알고리즘을 사용하면 되지만 현실적으로 음수일 경우가 없다고 한다) 간선의 가중치가 양수인데 서로 다를 때는 다익스트라! 간선이 모두 1일 때는 BFS 사용 가능! 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 ..

📌 Dynamic Programming 복잡한 문제를 여러 개의 문제로 나누어 푸는 방법 필요한 계산 값을 저장해두었다가 재사용하는 알고리즘 대표적 예시로 피보나치 수열이 있다. 피보나치 수열 피보나치 수열 점화식: F0​=0, F1​=1, Fn+2​=Fn+1​+Fn​ 다음과 같이 재귀함수를 사용하여 코드를 구현할 수 있다. def fibonacci(num): if num == 1 or num == 2: return 1 return fibonacci(num-1) + fibonacci(num-2) 단순 재귀함수로 구현했을 때, 동일한 함수가 반복적으로 호출되는 것을 볼 수 있는데 시간복잡도가 O(2^N)으로 N값이 커짐에 따라 연산 수행시간이 기하급수적으로 늘어난다. 동적 계획법을 사용하면 이러한 반복적인..

비트 마스크 (BitMask) 컴퓨터의 연산방식을 이용하여 정수의 이진수 표현을 자료구조로 쓰는 기법 *비트 (bit)란? 컴퓨터에서 다루는 최소 단위로 0과 1로 이루어짐 장점 빠른 수행시간 간결한 코드 더 적은 메모리 사용 비트 연산자 c = a & b # AND 000101 & 000011 = 000001 c = a | b # OR 000101 | 000011 = 000111 c = a ^ b # XOR 000101 ^ 000011 = 000110 c = ~a # NOT ~000101 = 111010 c = a b # SHIFT 000101 >> 000011 = 000000 1. AND 연산 대응하는 두 비트가 모두 1일 경우 1, 아니면 0 2. OR 연산 대응하는 두 비트가 모두 0일 경우 0,..

📌 Two Pointers 1차원 배열에서 두 개의 포인터를 사용하여 원하는 결과를 얻는 알고리즘 "특정한 합을 가지는 부분 연속 수열" 문제에서는 Two Pointer를 사용! 대표적으로 투 포인터를 활용한 문제는 다음과 같은 문제다. Q. 정렬된 리스트 A와 타겟 값 S가 주어졌을 때, 두 수의 합이 S가 되는 순서쌍을 모두 구하여라. 가장 먼저 떠오르는 풀이는 이중 반복문을 이용해 탐색하는 방법일 것이다. for i in range(len(A)): for j in range(i+1, len(A)): if A[i] + A[j] == S: print(A[i],A[j]) 매우 단순하고 직관적이지만 시간 복잡도가 O(n^2)이라 데이터가 커지면 시간초과가 발생할 가능성이 크다. 또한 문제가 두 수의 합이 ..