알고리즘
1.[알고리즘] | 시간 복잡도
효율성 알고리즘 문제 해결 코드가 얼마나 효율적인지 판단할때 아래 두가지가 가장 중요한 요소이다. 수행시간 사용한 메모리 수행시간 효율성을 판단하는데 제일 중요한 단 한가지 요소를 뽑자면 수행시간 이라고 할 수 있다. 어떤 프로그램을 작성했는데 시간이 20일이 걸리면 20일동안 실행시켜야한다. 해결 불가능 어떤 프로그램이 메모리가 64GB가 필요한...
2.[알고리즘] | 최대공약수와 최소공배수
최대공약수 > 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. 최대공약수를 간단히 줄여 GCD라고 한다. [일반적인 최대공약수를 구하는 방법] 최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A,B)까지 모든 정수로 나누어보는 방법이다. 이때 걸리는 시간복잡도는 O(N) 최대공약수가 1인 두 수를 서로소라고 한다...
3.[알고리즘] | 소수
소수(Prime Number) > 약수가 1 그리고 자기 자신밖에 없는 수 N이 소수가 되려면, 2보다 크거나 같고, N-1보다 작거나 같은 자연수로 나누어 떨어지면 안된다. 1부터 10까지의 소수 : 2, 3 ,5 ,7 소수 관련 알고리즘 어떤 수 N이 소수인지 아닌지 판별하는 방법 N보다 작거나 같은 모든 자연수 중에서 소수를 찾아내는 방법 어떤 ...
4.[알고리즘] | 비트마스크
비트마스크란? > 컴퓨터는 내부적으로 모든 자료를 이진수(비트)로 처리한다. 이런 컴퓨터의 연산방식을 이용한, 정수의 이진수 표현을 활용하여 문제를 해결하는 기법을 말한다. 비트(Bit)란? 비트는 이진수(과로 구성된 수)를 나타내는 말로 컴퓨터에서 사용하는 데이터의 최소 단위이다. 비트는 과의 값을 가질 수 있고 또는 라는 상태를 나타낼수도 있다. ...
5.[알고리즘] | 위상정렬(Topological Sort)
위상정렬의 개념 > 방향 그래프에서 정점(vertex)을 간선(edge)의 방향에 거스르지 않도록 나열하는것을 말한다. 위상정렬은 선후 관계가 정의된 그래프 구조상에서 선후 관계에 따른 정렬에 사용될 수 있다. 대표적으로 대학교 수강과목에서 선수과목의 구조를 예를 들 수 있다. 선수과목이 있다면 선수과목을 먼저 수강해야 하기 때문에 특정 과목을 수강해야 ...
6.[알고리즘] | 누적합(Prefix Sum), 2차원 누적합(Prefix Sum of Matrix)
배열의 인덱스는 0부터 시작한다. 예를 들어 개의 데이터가 있다면 부터 번 인덱스까지 존재한다. 다만, 누적 합을 구현함에 있어 인덱스를 번 인덱스부터 사용하는것이 더 편할 수 있다. 즉, 개의 데이터가 있을경우 번 인덱스부터 인덱스까지 사용하는것이다. 아래의 글의 그림에서는 번 인덱스부터 사용하고 있지만 실제로 누적합을 구현할때는 번 인덱스부터 사용하도...