이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다음과 같다. Greedy Approach (GA, 탐욕 알고리즘) Minimum Spanning Tree (MST, 최소 신장 트리) GA - 1. Prim's algorithm (프림 알고리즘) 1. Greedy Approach (탐욕 알고리즘) 동적 프로그래밍이 작게 쪼개고 재귀를 통해 작은 것들부터 해결해나가는 기법이었다면, 탐욕 알고리즘은 작게 나누지 않고 그때그때 탐욕스러운 (가장 이익이 되는) 선택을 해나가는 알고리즘이다. 접근 방식은 다음과 같다. 선택 과정 가장 가까운 노드들 중에서 현재 고려사항을 최고로 만족..

이번 챕터에서는 그래프에 대해 알아보고, 그래프를 이용해 최단거리를 구하는 Floyd algorithm (플로이드 알고리즘)도 살펴보려고 한다. 목차는 아래와 같다. 그래프 이론 플로이드 알고리즘 최단경로 구하기 - Floyd vs Brute-force 1. 그래프이론 (Graph Theory) 정말정말 x100!! 중요한 부분이다. 그래프 부분을 해놔야 이후에 나오는 다른 문제들을 해결할 수 있다! 그래프는 여러 개의 점(정점)들이 간선으로 연결된 구조를 나타낸다. 즉 그래프는 정점(V)와 간선(E)로 구성된다. G = (V, E) 그래프 종류 그래프는 가중치 존재의 여부, 방향 존재의 여부에 따라 종류가 다양하다. 가중치그래프 (weighted graph) : 간선에 값(가중치)이 존재한다면 그 그래..

이번 챕터에서는 Dynamic Programming에 대해 작성할 예정이다. 목차는 다음과 같다. 동적 프로그래밍 ? Dynamic Programming vs Divide-and-conquer (feat. 피보나치) 1. Dynamic Programming이란? 진짜 동적으로 프로그래밍을 하는게 아니고, 큰 문제를 작은문제로 나누어 푸는 방법을 말한다. Divide-and-Conquer처럼 문제를 하나 이상의 작은 인스턴스로 분할해 접근하지만, Divide-and-Conquer와 달리 Bottom-up approach를 사용한다. Bottom-up approach는 작은 인스턴트들을 먼저 해결해가는 접근법을 의미한다. Bottom-up approach는 다음과 같은 순으로 진행한다. 재귀적 속성 설정 작..

이번 게시글에서는 divide and conquer의 마지막으로 Master Theorem 에 대해 다뤄볼 예정이다. 목차는 다음과 같다. Master Theorem? divide and conquer에 대한 내용은 아래 링크에서 볼 수 있다. https://wanna-developer02.tistory.com/46 [알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort 이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 wanna-developer02.tistory.com..

지난 챕터에는 divide and conquer에 대해 다루어 보았다. 이번 챕터에서는 그 중에서도 퀵정렬에 대한 내용을 다루어 볼 예정이다. 목차는 다음과 같다. Quicksort? divide and conquer에 대한 내용은 아래 링크에 작성하였다! https://wanna-developer02.tistory.com/46 [알고리즘] CHAP 1. Divide and Conquer (분할정복) - mergesort 이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 wanna-developer02.tist..

이번 챕터에서는 divide and conquer에 대해 다뤄볼 예정이다. 목차는 다음과 같다. 분할정복 알고리즘? 예시 - merge sort 그럼 시작! 1. Divide-and-Conquer ? 분할정복은 본격적인 알고리즘 수업의 첫 시간에 배운 알고리즘이다. 그만큼 기초적인 부분이라고 할 수 있다. 분할정복이란 하나의 문제를 작은 여러개의 문제로 쪼갠 후 재귀적으로 각 문제를 해결한 후 이를 다시 합쳐 원래 문제를 해결하는 방법이다. 이에 대한 접근은 다음과 같이 할 수 있다. STEP 1) Divide 답을 얻을 수 있을 때까지 한 문제를 2개 이상의 작은 문제로 나눈다. STEP 2) Conquer 길이가 충분히 짧아지면 답을 바로 구할 수 있다. STEP 3) Combine 작은 문제를 해결..

2학기가 끝난 기념(?)으로 가장 중요한 과목이었던 알고리즘을 정리해보려고 한다. 더 미뤄서 머리에서 사라지기 전에..!자료구조랑 겹치는 부분은 최대한 배제하겠지만 어느정도의 교집합은 어쩔 수 없는 거 같다. 그럼 시작-! 이번 챕터에서는 첫 주에 배웠던 order function을 정리해 볼 예정이다. 1. order function의 종류우리는 알고리즘의 time complexity, 즉 시간복잡도를 함수를 이용해 표현한다. 사용하는 함수는 크게 7가지이다. lg n n (linear) n lg n n^2 (quadratic) n^3 (cubic) 2^n (exponential) n! (combinatorial)세로선을 그었을 때 그래프와의 교점이 아래에 있을수록 시간이 짧게 걸리는 함수라고 할 수 ..

프로그래머스 _ 코딩 기초 트레이닝 DAY 22 - (2) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181846 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 0 이상의 두 정수가 문자열 a, b로 주어질 때, a + b의 값을 문자열로 return 하는 solution 함수를 작성해 주세요. (1 풀이

프로그래머스 _ 코딩 기초 트레이닝 DAY 21 - (2) 출처 - https://school.programmers.co.kr/learn/courses/30/lessons/181851 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 0번부터 n - 1번까지 n명의 학생 중 3명을 선발하는 전국 대회 선발 고사를 보았습니다. 등수가 높은 3명을 선발해야 하지만, 개인 사정으로 전국 대회에 참여하지 못하는 학생들이 있어 참여가 가능한 학생 중 등수가 높은 3명을 선발하기로 했습니다. 각 학생들의 선발 고사 등수를 담은 정수 배열 rank와 전국 대회 ..

프로그래머스 _ 코딩 기초 트레이닝 DAY 21 - (1) 출처 -https://school.programmers.co.kr/learn/courses/30/lessons/181852 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 | 정수로 이루어진 리스트 num_list가 주어집니다. num_list에서 가장 작은 5개의 수를 제외한 수들을 오름차순으로 담은 리스트를 return하도록 solution 함수를 완성해주세요. 입력 #1 | [12, 4, 15, 46, 38, 1, 14, 56, 32, 10] 출력 #1 | [15, 32, 38, 46, ..