Algorithm
1.0. Introduction (23.08.20 수정)
파이썬으로 코딩테스트를 준비하면서 공부한 알고리즘 내용을 내가 알기 쉽게, 남에게 설명하듯 작성하고, 많은 문제를 풀이하고, Write-Up을 작성하고, 적은 경험이지만 남들에게 공유하고 싶다 라는 생각으로 만든 목적성 분명한 블로그입니다.목표는 24년 SW-Maest
2.0-1. 알고리즘 평가 방법
알고리즘이란 알고리즘은 컴퓨터가 따라할 수 있도록 자세히 설명한 과정을 나타낸 것이다. 즉, 어떤 작업이 주어졌을 때 컴퓨터가 이 작업을 해결하는 방법을 가르킨다. 따라서 알고리즘은 여러가지가 될 수 있다. 다만 주의할 점은 보통 알고리즘을 설명할 때 소스코드나 의사코
3.1. 그리디 알고리즘
최적해를 고르는 근사적인 방법 이며, 지금 당장 좋은것만 고르는 알고리즘이다.해당종류의 알고리즘은 응용이 많아 단순히 암기로 풀이하기 어렵다. 따라서 많은 문제를 풀어보는 것이 좋으며, 특히 다른 알고리즘과 접합하여 문제가 나오면 난이도가 높아진다. 특히 정렬 알고리즘
4.2. 구현
머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다. 구현 문제는 풀이를 떠올리는 것은 쉽지만, 소스코드로 옮기기 어려운 문제들이 많다. 또한 문제가 길거나, 문제의 조건이 많은 것들이 구현으로 구분된다.구현 문제는 프로그래밍 문법의 숙지가 미흡하거나, 라이브러리 사용
5.3. 정렬 1
데이터를 특정한 기준으로 나열하는것을 정렬이라고 하며, 오름차순 또는 내림차순으로 정렬한다. 또한 정렬문제를 풀이하다보면 다중조건을 이용해 정렬해야 하는 경우도 생긴다. 파이썬의 정렬 매소드인 sort()와 sorted()는 병합정렬(Merge Sort)을 이용하였다.
6.4. 정렬 2
파이썬의 정렬을 도와주는 함수sorted()와 리스트 등에서 사용할 수 있는 메서드 sort()가 있습니다.처음 사용할 때 가장 많이 햇갈렸었는데 한 줄로 설명하면 다음과 같습니다.1\. sort는 반환 값이 없다2\. sorted는 반환 값이 있다.이 말을 소스코드로
7.5. 탐색
탐색 알고리즘은 크게 2가지로 나눌수 있는데 선형 탐색(Linear Search)와 이진 탐색 (Binary Search) 이다. 앞서 구현에서 설명한 완전 탐색을 이용하여 탐색하는 방법도 있겠지만, 탐색할 데이터의 범위가 기하급수적으로 늘어난다면 완전탐색만으로 문제를
8.6-1. 다이나믹 프로그래밍
동적 계획법 (Dynamic Programming)은 최적화 문제를 연구하는 수학이론에서 왔으며, 큰 의미에서 분할 정복과 같은 접근 방식을 의미한다.동적 계획법 (이하 DP)에서 사용되는 알고리즘은 처음 주어진 문제를 더 작은 문제들로 나눈 뒤, 각 조각의 답을 계산
9.6-2. 다이나믹 프로그래밍 - 최적화 문제 (LIS)
LIS(Longest Incresing Subsequence) 개요 최대증가수열 문제는 Dynamic Programming을 공부하기에 좋은 문제 중 하나로 잘 알려져 있다.
10.6-3. 다이나믹 프로그래밍 - 경우의 수와 확률
동적 계획법은 애초에 최적화 문제를 풀기위해 고안되었지만, 경우의 수나 확률을 계산하는데에도 흔히 사용한다.대개 경우의 수를 사용하는 문제에서 답은 지수적으로 증가한다. 그래서 많은 경우에서의 답이 일반적으로 우리가 사용하는 컴퓨터에서 표현할 수 있는 정수의 범위를 넘
11.6-4 다이나믹 프로그래밍 - 반복적 동적계획법
앞선 방법으로는 동적계획법을 항상 재귀로 구현하였다. 직관적이다 라는 이유 때문이었는데, 재귀가 동적계획법을 구현하는 유일한 방법은 아니다.책에서는 이 글에서 정리할 내용같이 반복문을 통해 동적계획법을 구현하는 방법을 반복적 동적계획법 (iterative dynamic
12.6-5 동적계획법 테크닉
동적계획법 테크닉 아마 이 포스트가 마지막 동적계획법 정리이지 않을까 싶다. 동적 계획법으로 풀 수 있는 다양한 문제들과, 기법들에 대한 내용을 정리한다. 최적화 문제의 실제 답 계산하기 이전 포스트에서 LIS(nlogn)방식에서 실제 답을 찾는 방법을 공부했던 적
13.7-1 그래프 이론
이 포스트에서는 그래프의 기본적인 명칭 예를들면 노드, 간선 과 같은 내용은 생략한다. 또한 그래프의 구현 방법인 인접행렬과 인접리스트 방식 또한 생략한다.또한 아래에서 나오는 예시 (문제 풀이 제외)의 그래프 구현 방법은 인접행렬 방식을 사용한다.깊이 우선 탐색은 그
14.7-2 그래프 이론 - 그래프 알고리즘
이전 포스트에서 그래프 탐색을 기반으로하고 그래프 자료구조 형태에서 사용할 수 있는 다양한 알고리즘에 대한 소개를 한다.분리집합 또는 서로소 집합 이라고 불리는 Union-Find 알고리즘은 공통 원소가 없는 두 집합을 의미한다. 이 자료구조는 서로소 부분집합들로 나누
15.게임 이론
모든 정보가 공개되어 있어야 한다 \- 포커는 정보가 공개되어 있지 않다. \- 베스킨라빈스 31은 모든 정보가 공개되었다두 플레이어가 할 수 있는 행동이 같아야 한다.즉 선공, 후공의 차이 외에 모든 조건이 같아야 한다.즉, 승리조건으로는 선공이 누구인가, 덩어리