Algorithm6

• [파이썬(Python)] 최단 경로 - 플로이드 워셜 알고리즘(Floyd-Warshall Algorithm) 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다. 플로이드 워셜 알고리즘은 모든 지점의 최단 경로를 구할 때 사용됩니다. 다이나믹 프로그래밍 방식으로, 한 노드에서 다른 노드로 이동할 때의 비용과 다른 노드를 거쳐서 목표 노드로 가는 비용을 비교했을 때 더 작은 비용을 택합니다. N개의 노드가 있을 때 1번부터 N번 노드를 순차적으로 돌면서, 다른 두 노드 사이에서 해당 노드를 거쳐서 이동할 때와 한 노드에서 다른 노드로 직접 이동하는 비용을 비교하여 더 작은 값을 최단 거리로 택합니다. 예를 들어, 4개의 노드가 있다고 합시다. a에서 b로 가는 비용을 Dab라고 표현하고, 1번 노드부터 4번 노드까지 순차적으로 따져보겠습니다. 먼저 1번 노드를 기준 노드.. Algorithm 2023. 3. 27.

• [파이썬(Python)] 다이나믹 프로그래밍 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다. 프로그래밍에서 다이나믹 또는 동적인 것은 어떠한 동작이 프로그램 수행 중에 일어나는 것을 의미합니다. 실행 중에 메모리를 할당하거나, CSS를 변경하는 것을 동적이라고 할 수 있습니다. 하지만 알고리즘 문제 유형에서 가르키는 다이나믹은 그 의미가 아닙니다. 이번에는 코딩테스트의 관점에서 다이나믹 프로그래밍이 무엇이고, 어떤 문제를 해당 방식으로 풀면 좋은지 알아보겠습니다. 다이나믹 프로그래밍이란? 어떤 문제를 작은 문제로 분할하고, 중복된 문제는 한 번만 풀어서 효율성을 높이는 프로그래밍 방식을 의미합니다. 일반적으로 사용되는 '다이나믹'의 의미와 큰 연관성은 없어보이는데, 이 방법을 고안한 Bellman에 .. Algorithm 2023. 3. 7.

• [파이썬(Python)]DFS/BFS 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다. DFS(Depth-First Search) 그래프에서 깊은 부분을 우선적으로 탐색하는 깊이 우선 탐색 알고리즘입니다. 그래프 그래프는 노드(Node)/정점(Vertex)와 간선(Edge)으로 구성됩니다. 간선은 두 노드를 잇는 선인데, 이때 '두 노드는 인접하다'라고 합니다. 그래프는 두가지 방식으로 표현합니다. 인접 행렬(Adjacency Matrix) INF = 999999999 # 2차원 리스트를 이용해 인접 행렬 표현 graph = [ [0, 7, 5], [7, 0, INF], [5, INF, 0] ] print(graph) 2차원 배열로 연결 관계를 표현합니다. 연결되지 않은 노드 간에는 무한(Inf.. Algorithm 2023. 3. 5.

• [파이썬(Python)] 구현 알고리즘 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다. 구현 알고리즘이란? 구현은 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정입니다. '모든 알고리즘 문제가 다 구현 문제 아닌가?'라는 생각이 들 수 있는데요. 맞습니다. 모든 유형의 코딩 테스트가 구현 문제라고 할 수 있습니다. 그러나 여기서 이야기하는 구현 문제는 '풀이 자체는 특별한 방법이 아니지만 코드로 나타내기가 어려운 문제'를 의미합니다. 취업 코딩테스트용 알고리즘에 이런 문제가 자주 출제되기 때문에 따로 유형화해서 공부하는 것이죠. 특징 사소한 입력 조건 등이 명시됩니다. 문제의 길이가 긴 편입니다. 일반적으로 C/C++ 보다 파이썬을 사용해서 구현하는 것이 쉽습니다. 보통 다음과 같은 문제가 어려.. Algorithm 2023. 3. 2.

• [파이썬(Python)] 그리디 알고리즘 나동빈 님의 이것이 취업을 위한 코딩 테스트다 with 파이썬을 학습 목적으로 정리한 글입니다. 현재 상황에서 가장 좋아 보이는 것만 선택하는 알고리즘입니다. 직역해서 탐욕스러운 알고리즘으로, 탐욕법이라고도 합니다. 그리디 알고리즘 유형은 특별히 암기를 할 유형이 정해져 있는 것은 아니어서, 문제마다 아이디어를 낼 수 있어야 합니다. 출제 빈도는 높지 않지만, 다양한 문제가 그리디 알고리즘 문제로 분류가 됩니다. 예제 어떤 금액을 500원, 100원, 50원, 10원 동전으로 거슬러 줄 때, 동전의 최소 개수를 구하시오 이 문제는 가능한 한 큰 액수의 동전을 사용해야 합니다. 가장 큰 액수인 500원 부터 시작해서 해당 금액을 깎아 나가는 방식입니다. n = 1850 cnt = 0 coins = [500.. Algorithm 2023. 2. 22.

• 

  알고리즘 시간 복잡도 표기법 알고리즘의 사전적 정의는 다음과 같습니다. 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서이다. [위키백과] 컴퓨터는 인간처럼 한 번에 많은 데이터를 직관적으로 처리하지 않고, 한 번에 하나씩 처리하는데, 알고리즘은 그 처리 방식을 의미합니다. 컴퓨터의 한정된 자원은 상황에 적합한 알고리즘을 통해 효율적으로 사용되어야 합니다. 그리고 그 알고리즘의 효율성을 측정하는 방법 중 하나가 시간 복잡도입니다. 알고리즘의 시간 복잡도를 나타내는 표기법으로는 Big O(빅 오), Big Ω(빅 오메가), Big θ(빅 세타)가 있습니다. 알고리즘 간 실행 속도 우위는 데이터의 크기에 따라 달라질 수 있는.. Algorithm 2023. 1. 2.