파이썬 킹냥이😺

✅ 인접 리스트 (Adjacency List) 1️⃣ 인접 리스트의 특징그래프를 표현하는 또 다른 방법으로, 연결된 노드만 저장하는 방식입니다.메모리 효율적: 필요한 간선만 저장하므로 **공간 복잡도가 O(N + E)**로 줄어듭니다.연결 여부 확인 속도가 느림: 특정 두 노드가 연결되었는지 확인하려면 리스트를 탐색해야 하므로 O(N)의 시간이 걸립니다.✅ 장점:메모리를 절약할 수 있음 (O(N + E)) → 불필요한 공간 낭비 없이 저장 가능노드가 많고 간선이 적은 경우(희소 그래프)에 유리❌ 단점:특정 노드 간 연결 여부 확인 속도가 느림 (O(N))구현이 다소 복잡할 수 있음  2️⃣ 인접 리스트 예제 (양방향 그래프)다음과 같은 그래프를 인접 리스트로 표현해보겠습니다.예제 그래프 (0) --..

✅ 인접 행렬 (Adjacency Matrix)인접 행렬의 특징그래프를 표현하는 방법 중 하나로, 2차원 리스트(배열)을 사용하여 노드 간의 연결 정보를 저장하는 방식입니다.노드 개수가 N개라면, N x N 크기의 행렬을 사용합니다.graph[i][j] = 1이면 i번 노드에서 j번 노드로 갈 수 있음을 의미합니다.무방향 그래프의 경우 graph[i][j] == graph[j][i]가 항상 성립합니다.✅ 장점:연결 여부를 빠르게 확인 가능 (O(1)) → 특정 노드 간의 연결을 빠르게 조회할 수 있습니다.구현이 직관적 → 2차원 배열을 사용하기 때문에 접근이 쉬움❌ 단점:메모리를 많이 사용 (O(N^2)) → 노드 수가 많아지면 메모리 낭비가 심함간선 개수가 적은 경우 비효율적 → 사용하지 않는 공간이 ..

✅Graph(그래프)그래프(Graph)는 노드(Node, 정점)와 간선(Edge, 연결선)으로 이루어진 자료구조입니다. 이는 현실 세계의 관계를 모델링하는 데 많이 사용됩니다. 예를 들어,SNS 친구 관계 → 사람(노드)들이 친구(간선)로 연결지하철 노선도 → 역(노드)들이 선(간선)으로 연결지도 네비게이션 → 도시(노드)들이 도로(간선)로 연결그래프는 탐색 알고리즘을 사용해 특정 노드를 찾거나, 최단 경로를 구할 수 있습니다. 대표적인 탐색 방법으로 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)이 있습니다.1️⃣ 그래프의 기본 요소그래프는 두 가지 주요 요소로 구성됩니다.노드(Node, 정점): 데이터를 저장하는 기본 단위입니다.간선(Edge): 노드 간의 관계를 나타내는 연결선입니다.🔹 노드(..

⚠️ 작성 예정입니다! ⚠️ ⭕ 예시문제https://zerokee.tistory.com/3 18258. 큐 2https://www.acmicpc.net/problem/18258 # 기본 세팅입니다.import syssys.stdin = open('input.txt')input = sys.stdin.readlineN = int(input())queue = []for i in range(N): order = input().rstrip() if order == 'pop': if queue: print(queue[0]) queue.pop(0)zerokee.tistory.com

✅Knuth-Morris-Pratt (KMP 알고리즘) KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 검색(String Matching) 알고리즘 중 하나로, 텍스트에서 특정 패턴을 효율적으로 찾을 수 있는 방법입니다.일반적인 브루트 포스(완전 탐색) 방법(O(NM))은 불필요한 비교가 많아 비효율적입니다.KMP는 접두사-접미사 배열(Prefix Table, LPS 배열) 을 활용하여 중복되는 비교를 줄여 O(N + M) 시간 복잡도로 최적화합니다.1️⃣ KMP 알고리즘이 필요한 이유문자열 검색을 수행할 때, 일반적인 브루트 포스 방식을 사용하면 최악의 경우 O(NM) 시간이 걸립니다.하지만 KMP 알고리즘을 사용하면 O(N + M) 으로 줄일 수 있습니다.✔ KMP의 핵심 아이디어패턴 내..

✅ Two Pointer (투 포인터) 알고리즘Two Pointer(투 포인터) 알고리즘은 배열이나 리스트에서 두 개의 포인터를 사용하여 문제를 해결하는 기법입니다.이 방법은 정렬된 배열, 부분 배열, 두 배열 간의 비교 문제에서 자주 활용됩니다. 활용 예시:배열 내에서 특정 조건을 만족하는 두 개의 값 찾기부분 배열의 특정 조건 만족 여부 판단두 개의 정렬된 리스트 병합 또는 비교 1️⃣ Two Pointer 기법이 필요한 이유일반적으로 브루트 포스(완전 탐색) 를 사용하면 시간 복잡도가 높아지기 때문에 효율적인 탐색 방법이 필요합니다.Two Pointer를 사용하면 불필요한 탐색을 줄이고 O(N) 또는 O(N log N) 시간 복잡도로 최적화할 수 있습니다.✔ Two Pointer의 핵심 아이디어두 ..

✅Sliding Window (슬라이딩 윈도우) 알고리즘Sliding Window(슬라이딩 윈도우) 알고리즘은 배열 또는 리스트에서 일정한 크기의 범위를 유지하면서 이동하는 기법입니다. 즉, 고정된 크기(또는 가변 크기)의 윈도우를 활용하여 데이터를 효율적으로 탐색하는 방법입니다.활용 예시:배열, 문자열의 특정 범위 내 최대/최소값 찾기연속된 부분 배열의 합 계산 (최대 또는 최소 합 등)문자열 내 패턴 찾기 (애너그램, 부분 문자열 검색 등)1️⃣ Sliding Window 기법이 필요한 이유브루트 포스(완전 탐색) 를 사용하면 모든 경우를 검사해야 하므로 시간 복잡도가 높아 비효율적입니다.하지만 Sliding Window를 사용하면 불필요한 계산을 줄이고 효율적으로 문제를 해결할 수 있습니다. ✔ S..

1️⃣ 기본적인 시간 복잡도 계산 방법 (반복문 중심)  ✅ 시간 복잡도를 계산하는 일반적인 방법론시간 복잡도(Time Complexity)는 알고리즘이 실행되는 데 걸리는 시간을 입력 크기(n)에 대한 함수로 나타낸 것입니다.시간 복잡도를 분석하는 방법은 크게 두 가지로 나눌 수 있습니다.기본적인 반복문을 포함한 경우 (반복문 분석)재귀 함수가 포함된 경우 (재귀 분석) ① 단일 루프 → O(n) for i in range(n): print(i)  i는 0부터 n-1까지 증가 → n번 반복시간 복잡도: O(n)   ② 중첩 루프 (이중 루프) → O(n²)for i in range(n): for j in range(n): print(i, j) i가 n번 실행될 때마다 ..

✅ Selection Sort (선택 정렬)  선택 정렬(Selection Sort)은 가장 작은(또는 큰) 값을 선택하여 정렬하는 알고리즘입니다.배열에서 가장 작은 값을 찾아 첫 번째 값과 교환, 그다음 두 번째로 작은 값을 찾아 두 번째 값과 교환하는 방식으로 진행됩니다.이 과정을 반복하면 배열이 정렬됩니다. 항목설명알고리즘 이름Selection Sort (선택 정렬)시간 복잡도최선: O(n²), 평균: O(n²), 최악: O(n²)공간 복잡도O(1) (추가적인 메모리 사용 없음, 제자리 정렬)알고리즘 설명주어진 리스트에서 가장 작은 값을 찾아 맨 앞의 값과 교환하는 방식으로 정렬특징단순한 구조, 작은 데이터에 적합, 안정 정렬이 아님적용 예시데이터 개수가 적고, 추가 메모리를 쓰기 어려운 환경  ✅..

✅ Greedy 알고리즘 (Greedy Algorithm)  Greedy 알고리즘은 매 단계에서 현재 상황에서 가장 좋아 보이는 선택을 하는 방식으로 문제를 해결하는 알고리즘입니다. 즉, 국소 최적해(local optimum)를 구하는 방식으로, 이를 통해 전체 최적해(global optimum)를 찾고자 합니다. Greedy 알고리즘은 직관적이고 빠르게 구현할 수 있지만, 모든 문제에 대해 최적의 해를 보장하지는 않습니다. 하지만 특정 유형의 문제에서는 매우 효율적이고 정확한 결과를 낼 수 있습니다. 항목내용알고리즘 정의각 단계에서 가장 좋은 선택을 하여 문제를 해결하는 방식특징1. 직관적이고 간단한 구현 2. 최적해 보장 안 됨 3. 빠른 실행 속도시간 복잡도보통 O(n log n) 또는 O(n) 정..