코딩테스트 개념
1.[Python] 배열과 리스트
Python은 배열과 리스트를 구분하지 않음Python의 리스트는 리스트와 배열의 특징까지 모두 가진다.리스트를 선언할 때는 다음과 같이 사용하면 된다.리스트 기본 활용리스트 출력각 요소에 접근 : 인덱싱array-1 array-2 \`\`\`범위 요소에 접근 : 슬라
2.[Python] 구간 합
합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘주어진 수열에서 임의의 구간에 포함된 요소의 합을 빠르게 구하는 방법앞에서부터 합을 누적하여 미리 계산해 저장해 놓고 활용하는 방법
3.[Python] 투 포인터
리스트에서 순차적으로 접근하려고 할 때 두 개의 포인터를 사용하여 원하는 값을 찾거나 구간 합, 반복 등의 처리를 할 때 유용한 알고리즘시작점(start)와 끝점(end) 2개의 점으로 접근할 데이터의 범위 표현 가능슬라이딩 윈도우와 유사한 알고리즘이지만, 투 포인터는
4.[Python] 슬라이딩 윈도우
슬라이딩 윈도우 고정 크기의 윈도우를 이동하면서 윈도우 내의 요소들의 값을 이용하여 문제를 해결하는 알고리즘 투 포인터와 유사한 알고리즘이지만, 슬라이딩 윈도우는 고정된 구간을 탐색함 정렬 여부에 관계 없이 사용 가능함 단방향 포인트 이동 전체 탐색(반복문)은 O(N
5.[Python] 버블 정렬, 선택 정렬, 삽입 정렬
인접한 원소들을 비교하고 필요에 따라 위치를 교환하는 방식이다. 큰 값(또는 작은 값)이 배열을 통해 버블(거품)처럼 서서히 상단(또는 하단)으로 이동하며 정렬한다.배열의 처음부터 끝까지 순회를 시작한다.현재 원소와 바로 다음에 있는 원소를 비교. 정렬하려는 순서(오름
6.[Python] 퀵 정렬, 병합 정렬, 기수 정렬
평균적으로 매우 빠른 실행 시간을 가지는 비교 기반 정렬 알고리즘이다. 분할 정복(divide and conquer) 방식을 통해 큰 문제를 작은 문제로 나누어 해결한다. '피벗(pivot)'을 사용하여 배열을 분할하는 것이 핵심이며, 피벗을 기준으로 피벗보다 작은 모
7.[Python, Java] 팀 정렬(Tim sort) : 내장 정렬 함수
버블 정렬 (Bubble Sort): 최선의 경우는 이미 정렬된 경우로 한 번의 패스에서 아무 교환도 일어나지 않는다.선택 정렬 (Selection Sort): 항상 𝑂(n^2)시간 복잡도를 가진다.삽입 정렬 (Insertion Sort): 최선의 경우는 이미 정렬된
8.[Python] 깊이 우선 탐색 DFS
평균적으로 매우 빠른 실행 시간을 가지는 비교 기반 정렬 알배열에서 하나의 요소를 피벗으로 선택한다. (첫 번째, 마지막, 중간, 무작위 등)특징
9.[Python] 너비 우선 탐색 BFS
루트노드(혹은 다른 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법시작 정점으로부터 가까운 정점을 방문해나가 가장 멀리 떨어진 정점을 나중에 방문하는 순회 방법말그대로 넓게 탐색하는 방법 (방문한 노드를 기준으로 주변을 탐색해나가므로)깊이 우선 탐색보다 조금 더
10.[Python] 이진 탐색
정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.
11.[Python] 그리디 알고리즘
정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색하도록 제한하여 원하는 원소를 찾는 알고리즘이다. 리스트 중간 부분에 찾는 원소가 있는지 확인하고, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색하거나 중간부터 검색한다.
12.[Python] 그래프의 표현
그래프(Graph)는 데이터 구조 중 하나로, 객체 간의 관계를 나타내는 데 사용된다. 그래프는 정점(Vertex)과 간선(Edge)으로 구성되며 정점은 객체를 나타내고, 간선은 그 객체들 간의 관계를 나타낸다. 🔍 그래프의 기본 속성정점 (Vertex)그래프의 기본
13.[Python] 다익스트라(Dijkstra) 알고리즘
다익스트라 알고리즘(Dijkstra's Algorithm)은 주어진 시작 정점으로부터 모든 다른 정점까지의 최단 경로를 찾는 알고리즘이다. 이 알고리즘은 가중치가 있는 그래프에서 최단 경로를 찾는 데 유용하며, 특히 가중치가 모두 양수일 때 효율적으로 작동한다.
14.[Python] 플로이드-워셜(Floyd-Warshall) 알고리즘
그래프 내의 모든 쌍 최단 경로 문제를 해결하는 데 사용되는 알고리즘이다. 주어진 그래프에서 모든 정점 쌍 사이의 최단 경로 거리를 계산하며, 그래프는 가중치가 있는 방향 그래프일 수 있다. 동적 계획법을 사용하여 점진적으로 최단 경로를 찾는다.초기화: 그래프의 인접
15.[Python] 최소신장트리(MST)
최소 신장 트리(Minimum Spanning Tree, MST)는 가중치가 있는 무향 그래프에서 모든 정점을 포함하는 최소 가중치 트리를 의미한다. MST는 여러 실제 문제(예: 네트워크 설계, 클러스터링)에서 중요하게 사용된다.MST를 찾기 위한 대표적인 알고리즘으
16.[Python] 동적 계획법(Dynamic Programming, DP)
복잡한 문제를 더 간단한 하위 문제로 나누어 해결하는 방법론이다. DP는 하위 문제의 해결 결과를 저장하여 동일한 하위 문제가 다시 나타날 때 재사용함으로써 계산을 반복하지 않아 효율성을 높이는 방법을 사용한다.일반적으로 다음 두 가지 조건을 만족할 때 유용하다.최적
17.[Python] 구현 : 시뮬레이션, 완전 탐색
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정.풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제를 지칭함.완전 탐색, 시뮬레이션 두 유형이 있다.📒 완전 탐색모든 경우의 수를 주저 없이 다 계산하는 해결 방법📒 시뮬레이션문제에서 제시한 알고리즘을 한 단