Search
⚠️

알고리즘

태그
tech
algorithms
작성일자
1 more property
갤러리 보기
Search
알고리즘
•
알고리즘 계산 복잡도는 다음 두 가지 척도로 표현될 수 있음
◦
시간 복잡도 : 얼마나 빠르게 실행되는지
◦
공간 복잡도 : 얼마나 많은 저장 공간이 필요한지
좋은 알고리즘은 실행 시간도 짧고, 저장 공간도 적게 쓰는 알고리즘
•
통상 둘 다를 만족시키기는 어려움
◦
시간과 공간은 반비례적 경향이 있음
◦
최근 대용량 시스템이 보편화되면서, 공간 복잡도보다는 시간 복잡도가 우선
◦
그래서! 알고리즘은 시간 복잡도가 중심
공간 복잡도 대략적인 계산은 필요함
•
기존 알고리즘 문제는 예전에 공간 복잡도도 고려되어야할 때 만들어진 경우가 많음
•
그래서 기존 알고리즘 문제에 시간 복잡도뿐만 아니라, 공간 복잡도 제약 사항이 있는 경우가 있음
•
또한, 기존 알고리즘 문제에 영향을 받아서, 면접시에도 공간 복잡도를 묻는 경우가 있음
1.
공간 복잡도(Space Complexity)
•
프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
•
총 필요 저장 공간
◦
고정 공간(알고리즘과 무관한 공간) : 코드 저장 공간, 단순 변수 및 상수
◦
가변 공간(알고리즘 실행과 관련있는 공간) : 실행 중 동적으로 필요한 공간
◦
S(P) = c + Sp(n)
▪
c = 고정 공간
▪
Sp(n) : 가변 공간
빅 오 표기법을 생각해볼 때, 고정 공간은 상수이므로 공간 복잡도는 가변 공간에 좌우됨
2.
공간 복잡도 계산
•
공간 복잡도 계산은 알고리즘에서 실제 사용되는 저장 공간을 계산하면 됨
◦
이를 빅 오 표기법으로 표현할 수 있으면 됨
공간 복잡도 예제1
1. 공간 복잡도
2022/06/24 08:13
1.
알고리즘 연습 방법
•
알고리즘을 잘 작성하기 위해서는 잘 작성된 알고리즘을 이해하고, 스스로 만들어봐야 함
◦
모사! 그림을 잘 그리기 위해서는 잘 그린 그림을 모방하는 것부터 시작

알고리즘 연습 방법

1.
연습장과 펜을 준비한다.
2.
알고리즘 문제를 읽고 분석한 후에,
3.
간단하게 테스트용으로 매우 간단한 경우부터 복잡한 경우 순서대로 생각해보면서, 연습장과 펜을 이용하여 알고리즘을 생각해본다.
4.
가능한 알고리즘이 보인다면, 구현할 알고리즘을 세부 항목으로 나누고, 문장으로 세부 항목을 나누어서 적어본다.
5.
코드화하기 위해, 데이터 구조 또는 사용할 변수를 정리하고,
6.
각 문장을 코드 레벨로 적는다.
7.
변수가 코드에 따라 어떻게 변하는지를 손으로 적으면서, 임의 데이터로 코드가 정상 작동하는지를 연습장과 펜으로 검증한다.

1. 정렬(sorting)이란?

2. 버블 정렬
2022/06/24 08:43
유클리드 호제법 (백준)
•
최대 공약수 : A와 B 두 수가 주어지면 A의 약수들을 모두 구하고, B의 약수들을 모두 구한 뒤 공통 된 약수들만 찾아내어
약수들의 곱으로 다시 나타내준다.
•
정리
두 수 a, b ∈ ℤ 이고, r = a mod b 이라고 한다. (r 은 a에 b를 나눈 나머지를 의미)
이 때 r은 (0 ≤ r < b) 이고, a ≥ b 이다.
이 때 a 와 b의 최대공약수를 (a, b)라고 할 때 (a, b)의 최대공약수는 (b, r)의 최대공약수와 같다.
즉, GCD(a, b) = GCD(b, r)
•
최소 공배수: A와 B 두 수가 주어진다면 A,B의 공통된 최소 배수
•
정리
최대공약수를 구해준 뒤 입력받은 두 수의 곱에서 최대공약수를 나눠준다.
•
코드
알고리즘(유클리드 호제법)
2022/02/21 05:48
1.
선택 정렬(selection sort)란?
•
다음과 같은 순서를 반복하여 정렬하는 알고리즘
1.
주어진 데이터 중, 최소값을 찾음
2.
해당 최소값을 데이터 맨 앞에 위치한 값과 교체함
3.
맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함
2.
어떻게 코드로 만들까
간단한 로직에 집중해서, 각각 데이터가 저장되어 있는 배열이 있다고 가정
•
데이터가 두 개 일때
◦
예: dataList = [9, 1]
▪
dataList[0] > dataList[1] 이므로 dataList[0] 값과 dataList[1] 값을 교환
•
데이터가 세 개 일때
◦
예 : dataList = [9, 1, 7]
▪
처음 한번 실행하면 : 1, 9 ,7
▪
두번 째 실행하면 : 1, 7, 9
•
데이터가 네 개 일떄
◦
예: dataList = [9, 3, 2, 1]
▪
처음 한번 실행하면 1, 3, 2, 9
▪
두번째 실행하면 1, 2, 3, 9
▪
세번째 실행하면 변화 없음
3.
알고리즘 구현
1. for(int stand = 0; stand < dataList.size()-1;stand++)로 반복 2. lowest = stand로 놓고 3. for(int index = stand + 1; index < dataList.size();index++)로 stand 이후부터 반복 - 내부 반복문 안에서 dataList[lowest]>dataList[index] 이면, - lowest = num 4. dataList[lowest]와 dataList[index]
Java
복사
import java.util.ArrayList; import java.util.Collections; public class SelectionSort { public ArrayList<Integer> sort(ArrayList<Integer> dataList){ int lowest; for(int stand = 0; stand<dataList.size()-1; stand++){ lowest = stand; for(int index = stand + 1; index < dataList.size(); index++){ if(dataList.get(lowest) > dataList.get(index)){ lowest = index; } Collections.swap(dataList, lowest, stand); } return dataList; } }
Java
복사
3. 선택 정렬
2022/06/29 06:55
1.
삽입 정렬 이란?
•
삽입 정렬은 두 번째 인덱스부터 시작
•
해당 인덱스 앞에 있는 데이터부터 비교해서 key 값이 더 작으면, B 값을 뒤 인덱스로 복사
•
이를 key값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key값을 이동
2.
어떻게 코드로 만들까?(결국 프로그래밍으로 일반화할 수 있도록 만드는 것)
알고리즘 연습 방법에 기반해서 단계별로 생각해봅시다.
연습해보기 1
•
데이터가 두 개일 떄 동작하는 삽입 정렬 알고리즘을 함수로 만들어보기.
연습해보기 2
•
데이터가 세 개일 떄 동작하는 삽입 정렬 알고리즘을 함수로 만들어보기.
연습해보기 3
•
데이터가 네 개일 때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보기.
4. 삽입 정렬
2022/07/03 08:41
1.
재귀 용법
•
함수 안에서 동일한 함수를 호출하는 형태
2.
재귀 용법 이해
•
예제를 풀어보며, 재귀 용법을 이해해보기
예제
•
팩토리얼을 구하는 알고리즘을 Recursive Call을 활용해서 알고리즘 작성하기
예제 - 분석하기
•
간단한 경우부터 생각해보기
◦
2! = 1 x 2
◦
3! = 1 x 2 x 3
◦
4! = 1 x 2 x 3 x 4
•
규칙 n! = n x (n-1)!
1. 함수를 하나 만든다.
2.
함수(n)은 n > 1 이면 return n x 함수(n-1)
3.
함수(n)은 n = 1 이면 return n
예제 - 코드 레벨로 적어보기
5. 재귀 용법
2022/07/03 08:59
1.
정의
•
동적계획법(DP라고 많이 부름)
◦
입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
◦
상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
◦
Memoization 기법을 사용함
▪
Memoization(메모이제이션) 이란 : 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
▪
문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨
•
예 : 피보나치 수열
•
분할 정복
◦
문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
◦
하향식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
▪
일반적으로 재귀함수로 구현
◦
문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지않음
▪
예 : 병합 정렬, 퀵 정렬 등
b.
공통점과 차이점
•
공통점 : 문제를 잘게 쪼개서, 가장 작은 단위로 분합
•
차이점
◦
동적 계획법 : 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨, Memoization 기법 사용(부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용
◦
분할 정복 : 부분 문제는 서로 중복되지 않음, Memoization 기법 사용 안함
c.
동적 계획법 알고리즘 이해
•
피보나치 수열 : n 을 입력받아서 다음과 같이 계산됨
•
n 을 입력받았을 때 피보나치 수열로 결과값을 출력하세요.
6. 동적 계획법과 분할 정복
2022/07/03 09:24

1. 탐욕 알고리즘 이란?

•
Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움
•
최적의 해에 가까운 값을 구하기 위해 사용됨
•
여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식

2. 탐욕 알고리즘 예

문제1 : 동전 문제

•
지불해야 하는 값이 4720원 일 때 1원, 50원, 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.
•
가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현 가능
•
탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨
7. Greedy 알고리즘
2022/10/02 13:05

깊이 우선 탐색(Depth-First Search)

1.BFS 와 DFS란?
•
대표적인 그래프 탐색 알고리즘
◦
너비 우선 탐색: 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식
◦
깊이 우선 탐색:
8. DFS
2022/10/16 05:45

이진 탐색이란?

BinarySearch 라고 부르며, 정렬되어 있는 배열에서 특정 값을 찾는 알고리즘.
X 라는 숫자를 찾는다고 할 때, 배열의 중간값을 X 와 비교한다.
X 보다 중간값이 크면 X는 중간값 기준으로 배열의 왼쪽에 있고, X 보다 중간값이 작으면 X는 중간값 기준으로 오른쪽에 있다.
아래 배열 에서 40을 찾는다고 생각해보면
10
20
30
40
50
X = 40
mid = 30
X> mid 이기 때문에 X 는 mid기준으로 오른쪽
이런식으로 찾아 나간다.
코드로 보자면
9. 이진탐색
2022/11/21 23:30