Algorithm

# 최대 부분 배열 합이란? 개념은 아주 간단합니다. 주어진 수 배열에서 연속된 부분 배열 중 합이 최대인 부분 배열을 찾는 알고리즘입니다. 이 문제는 완전 탐색, 부분합 수열, 분할 정복, DP 를 활용하여 풀 수 있지만 각각 시간 복잡도가 O(2^n), O(n^2), O(nlogn), O(n) 로 다르기 때문에 가장 효율적인 DP로 푸는것이 가장 바람직합니다. # 예제 코드 def getSum(arr): dp = sequence[0]# 현재까지의 최대합 cur = 0# 실시간 최대합 for x in arr: cur = max(x, cur + x)# 특정 구간까지의 합 + 현재 값 vs 현재 값 dp = max(dp, cur)# cur이 현재까지 최대합보다 크다면 갱신 return dp # 알고리즘의 ..

# P / NP 문제 P : 결정론적 다항 시간(Deterministic Polynomial time)에 문제의 해를 찾을 수 있는 문제 집합입니다. ex) O(n^2) NP : 비결정론적 다항 시간(Non-deterministic Polynomial time)에 문제의 해를 검증할 수 있는 문제 집합입니다. 즉, 다항 시간 내에 주어진 답이 올바른지 검증하는 알고리즘이 존재합니다. ex) O(2^n) 이러한 NP문제를 풀때 백트래킹을 사용하면 문제를 효율적으로 해결하는데에 도움을 줍니다. (다만, 모든 NP문제를 백트래킹으로 풀 순 없습니다. 상태공간트리로 표현가능해야합니다.) # backtracking이란? 백트래킹(Backtracking) 알고리즘은 가능한 모든 상태를 탐색하면서 해결책을 찾아내는 ..

# 정의 벨만-포드 알고리즘은 음의 가중치를 가지는 간선이 있는 그래프에서 최단 경로를 찾는 알고리즘입니다. 이 알고리즘은 다익스트라 알고리즘과 다르게, 그래프 내의 모든 정점을 대상으로 최단 경로를 갱신하므로 음의 가중치를 가지는 간선이 있어도 사용할 수 있습니다. 그러나 음의 사이클이 존재하는 경우에는 최단 경로를 구할 수 없습니다. 벨만포드를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야합니다. 다른 글에서 설명을 이미 했기 때문에 링크만 올려두겠습니다. https://whitem4rk.tistory.com/18 BFS (Breadth First Search ) # 정의 너비우선탐색이라 불리는 BFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리즘이다...

# 정의 누적합 알고리즘(Cumulative Sum Algorithm)은, 1차원 배열의 일부 또는 전체 원소들의 합을 빠르게 구할 수 있는 알고리즘입니다. 이 알고리즘은 입력 배열의 각 원소를 한 번씩만 방문하면서, 각 위치에서 누적합을 계산하고, 미리 계산해 둔 누적합을 사용하여 구간 합을 계산합니다. 글로만 읽어도 이해가 갈 정도로 굉장히 간단한 알고리즘입니다. 그래서 겉보기에 그냥 당연한 얘기처럼 보입니다. 하지만 오늘 알고리즘 문제를 풀면서 엄청난 활용을 발견했습니다. # Code 가장 기본적인 파이썬 코드입니다. 정말 간단합니다. # 입력 배열을 정의합니다. arr = [1, 2, 3, 4, 5] # 누적합 배열을 초기화합니다. prefix_sum = [0] * len(arr) prefix_s..

# 정의 플로이드-워셜 알고리즘은 그래프에서 모든 정점 쌍 간의 최단 경로를 구하는 알고리즘입니다. 다익스트라 알고리즘과는 다르게 음의 가중치를 가진 간선이 있어도 처리할 수 있습니다. 이를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다. BFS를 설명할때 이미 했기 때문에 링크만 올려두겠습니다. https://whitem4rk.tistory.com/18 BFS (Breadth First Search ) # 정의 너비우선탐색이라 불리는 BFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리즘이다. chatGPT에 따른 BFS의 정의는 다음과 같다. BFS(Breadth-First Search) whitem4rk.tistory.com # Code 플로이드-워..

# 정의 다익스트라 알고리즘은 하나의 시작 정점으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘입니다. 이 알고리즘은 음의 가중치를 가지는 간선이 없을 때(BFS와 큰 차이점)만 사용할 수 있습니다. 다익스트라를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다. 다른 글에서 설명을 이미 했기 때문에 링크만 올려두겠다. https://whitem4rk.tistory.com/18 BFS (Breadth First Search ) # 정의 너비우선탐색이라 불리는 BFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리즘이다. chatGPT에 따른 BFS의 정의는 다음과 같다. BFS(Breadth-First Search) whitem4rk.tistory.c..

# 정의 너비우선탐색이라 불리는 DFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리즘이다. chatGPT에 따른 DFS의 정의는 다음과 같다. DFS는 그래프의 한 노드에서 시작하여 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 더 이상 탐색할 수 없을 때까지 깊이 우선으로 탐색합니다. DFS를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다. BFS를 설명할때 이미 했기 때문에 링크만 올려두겠다. https://whitem4rk.tistory.com/18 BFS (Breadth First Search ) # 정의 너비우선탐색이라 불리는 BFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리..

# 정의 너비우선탐색이라 불리는 BFS 알고리즘은 굉장히 잘 알려져있고 컴퓨터 관련 전공생들은 거의 모두 알고 있는 알고리즘이다. chatGPT에 따른 BFS의 정의는 다음과 같다. BFS(Breadth-First Search) 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘입니다. 이 알고리즘은 너비 우선 탐색을 하며, 시작 노드에서 가까운 노드들부터 우선적으로 방문합니다. BFS를 이해하기 위해선 "그래프"라는 것이 무엇인지부터 알아야한다. # Graph 그래프(Graph)는 데이터를 저장하고 관리하는 자료구조 중 하나로, 객체들 간의 관계를 나타내는 추상적인 자료구조입니다. 그래프는 노드(Node)와 간선(Edge)로 이루어져 있습니다. 노드는 그래프에서 하나의 객체를 나타내며, ..