알고리즘
1.정렬과 재귀
정렬이란 여러 데이터를 특정 순서로 나열하는 조작예를 들어 아래와 같은 조작이다.오름차순 : 31, 41, 55, 22 -> 22, 31, 41, 55내림차순 : 5, 2, 3, 2, 3, 8 -> 8, 5, 3, 3, 2, 2사전 순 : "algo", "mast",
2.소수 판정법
3.[알고리즘]뉴턴법 : 수치 계산
뉴턴 - 랩슨법(Newton-Raphson Method) > 주어진 함수의 근을 찾기 위한 반복적인 수치 방법 중 하나. 뉴턴법은 함수의 접선을 반복해서 그어, 어떠한 수치의 근삿값을 계한하는 알고리즘이다. 예를 들어서 $$\sqrt{2}$$의 근삿값을 구하려고
4.[알고리즘] 에라토스테네스의 체
소수를 구하는 알고리즘으로 유명한 $에라토스테네스의 체$ 관련해서 정리를 해보겠다. 에라토스테네스의 체
5.[알고리즘] 탐욕법
탐욕법(그리디) 알고리즘이란? Greedy의 뜻은 '탐욕스러운, 욕심이 많은'의 의미를 갖고 있다. 해당 알고리즘은 선택의 순간에 최적의 상황만을 찾아 최종적인 답에 도달하는 알고리즘이다. 하지만 가장 좋은 결과는 최종적인 결과 도출에 대한 최저의 해를 보장해주는
6.[알고리즘]-이진 탐색
이진(이분) 탐색 (Binary Search) 해당 알고리즘은 검색범위를 줄여 나가면서 원하는 데이터를 검색하는 알고리즘이다. 아래의 이미지는 이진 탐색을 가장 잘 나타내는 이미지다.
7.[알고리즘]-계차 누적합 계산
계차와 누적합 정수 $A1, A2, ···, A_N$ 이 있을 때, > 계차는 수열에서 인접한 항들 간의 차이를 나태낸다. $Bi=Ai - A_{i-1}$ > 누적합은 각 항의 값들을 차례로 더한 결과를 타나낸다. $Bi=A1 + A2 + ··· + AN$ |3|
8.[알고리즘] - 계산 기하학
🧐 계산 기하 알고리즘?? 컴퓨터 과학과 수학에서 사용되는 알고리즘의 한 부분이다. 기하학적인 문제 해결을 하는 데 주로 사용이 된다. (점, 선, 다각형과 원 등 기하학적 도형을 다룬다) 2차원과 3차원의 도형을 다루는 주제이지만, 2차원 기하학만을 다루겠다.
9.[알고리즘] - 해시 (Hash)
해시 Hash 해시는 데이터를 다루는 기법 중 하나이다. 임의의 크기를 갖고있는 데이터를 고정된 크기의 값으로 변환시켜 Key - Value의 형태로 저장을 한다. 이런 형태로 인하여 Key의 값이 배열의 인덱스로 저장되기 때문에 검색과 저장의 실행이 빠르다. 키에
10.[알고리즘] 그래프를 사용한 알고리즘
그래프란? 여러 대상을 연결하여 표현한 네트워크 구조를 그래프라고 표현을 한다. 즉, 네트워크 구조를 의미한다. 그래프는 정점(vertex)과 변(edge)으로 이루어진다. 정점은 대상을 나타내고, 변은 대상들의 관계를 나타낸다. 그래프의 종류 무향 그래프, 유향
11.[알고리즘] - 경우의 수
곱의 법칙 Multiplication Principle 곱의 법칙은 두 개 이상의 독립적인 선택이 있을 경우, 전체 선택의 경우의 수를 계산하는 방법이다. 만약 첫 번째 선택의 경우의 수가 $n$가지이고 두 번째 선택의 경우의 수가 $m$가지라면 전체 경우의 수는
12.[알고리즘] 투 포인터
Two Pointer 배열이나 리스트와 같은 1차원 자료구조에서 두 개의 포인터를 이용하여 문제를 보다 효율적으로 해결하는 방법이다. 주로 정렬된 배열에서 특정한 조건을 만족하는 부분 배열이나 쌍을 찾는 데 사용이 된다. 배열의 시작과 끝, 또는 다른 두 위치에 포인
13.[알고리즘] 모듈러 연산 part. 1
모듈러 연산은 어느 하나의 값을 나눈 나머지를 구하는 연산이다.두 정수 A와 B가 있다고 하자, A를 B로 나누었을 때 나머지는 C일 경우를 표현하면A $mod$ B = C 로 표현할 수 있다.앞에서 간단하게 모듈러 연산이 무엇이고 어떻게 표현을 하지는 알아봤지만 이러
14.[Algorithm] 교점 구하기
코딩 테스트 문제를 풀면서 아주 가끔 두 직선이 주어질 때, 교점을 구하는 문제가 나타나긴 한다.이 같은 문제가 주어지면 노트와 펜으로 해결하면 상당히 쉬운 문제이다.그런데 프로그램 언어를 사용하면 해당 공식을 모른다면 다소 어렵거나? 생각을 좀 해야 해결이 가능하다.
15.[알고리즘] Kadane's Algorithm (카데인 알고리즘)
솔직히 카데인 알고리즘에 대한 개념이 없었기 때문에 초기에는 각 시작 인덱스를 기준으로 부분 배열의 경우의 수를 계산하여 결과를 반환했다.그러면 주어진 배열에서 가능한 모든 경우의 부분배열을 찾아서 계산해야 한다는 불편한 부분이 있었다,기존에 생각한 방법이 아닌 좀 더
16.[Algorithm] 프림 & 크루스칼 알고리즘 (최소 신장 트리 알고리즘, MST)
최소 신장 트리 (MST) 는 가중치가 있는 무방향 그래프에서 모든 노드를 포함하면서 가중치의 합이 최소가 되는 트리를 의미한다. 즉, 모든 정점을 연결하면서 최소의 가중치로 연결하는 그래프의 부분 그래프를 찾는 것이 목적이다.N개의 정점을 가지는 그래프에서 MST
17.[Algorithm] Dijkstra’s Algorithm(데이크스트라 or 다익스트라 알고리즘)
다익스트라 알고리즘은 한 꼭짓점에서 다른 꼭짓점까지의 최단 경로를 계산하기 위해서 사용되는 알고리즘이다. 해당 알고리즘은 여러 변형들이 존재한다. 일반적인 변형은 두 꼭짓점에서 최단 경로 계산에 국한된 것이 아닌 모든 꼭짓점에 대한 최단 경로를 계산하는 알고리
18.[Algorithm] Manacher’s Algorithm - 회문 찾기
회문 또는 팰린드롬이라 부르는 것은 특정 단어를 거꾸로 읽어도 원래의 문자와 동일한 단어를 부른다. 간단한 예를 들면 오디오, 기러기, bob, level, abbcdcbba 와 같이 거꾸로 읽어도 동일한 것을 나타낸다.회문은 앞에서 거꾸로 읽어도 원래의 단어와 동
19.[Algorithm] Floyd - Warshall’s Algorithm
최단 경로를 구하는 과정에서 사용되는 여러 알고리즘 중 모든 노드에서 또 다른 모든 노드까지의 최단 거리를 구하기 위해서 사용되는 알고리즘이다. 최단 경로를 구할 때 사용되는 다른 알고리즘으로 Dijkstra’s Algorithm가 사용된다. (두 알고리즘