취업을 준비하며 정리하는 컴퓨터 지식/Algorithm (18) 썸네일형 리스트형 [Algorithm] 알고리즘 정리 정렬 선택 정렬(selection sort) 배열에서 가장 큰 값을 선택하여 정렬되지 않은 배열의 맨 뒤로 이동시켜 정렬하는 방법입니다. 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다. 버블 정렬(bubble sort) 배열에서 인접한 두 값을 비교하여 조건에 맞게(오름차순, 내림차순에 따라 다름) 값의 위치를 이동시켜 정렬하는 방법입니다. 선택 정렬과 마찬가지로 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다. 향상된 버블 정렬(enhanced bubble sort) 버블 정렬과 같은 방법으로 동작하지만 이중 반복문을 순환하는 동안 값이 한 번도 바뀌지 않으면 정렬되었다고 가정하는 정렬 방법입니다. 버블 정렬과 마찬가지로 모든 경우에 대해서 O(n^2)의 시간 복잡도를 가집니다. 삽.. [Algorithm] 유클리드의 호제법은 뭐야? 두 정수 또는 두 정식인 a와 b가 있을 때, a를 b로 나눈 나머지 a'로 b를 나누고 그 나머지로 a'를 나누는 일을 완전히 나누어질 때까지 계속하여 a와 b의 최대 공약수를 구하는 방법. 단, a, b가 자연수일 때 a>b, 다항식일 때는 a의 차수가 b의 차수 이상이어야 한다. - 네이버 '유클리드의 호제법' 사전 정의 위의 정의에서는 아래의 조건이 만족해야 한다. a, b는 자연수이다. a > b가 만족한다. 유클리드의 호제법은 다음의 과정을 실행한다. a, b는 자연수(a > b), value = a % b이다. b!= 0 이 되기 전까지 a % b 연산을 실행한다. a에 b의 값을 대입하고, b에 value값을 대입한다. 1의 과정을 반복한다. 다음은 위의 과정을 그림으로 표현한 것이다. 다.. [Algorithm] 에라토스테네스의 체는 뭐야? 에라토스테네스의 체는 소수의 배수들을 지우면서 소수를 찾는 방법이다. 해당 알고리즘에서 중요한 점은 만약 1부터 150까지의 소수를 구하고 싶다면 13^2 > 150 이므로 13보다 작은 수의 배수들만 지워주면 된다는 것이다. 에라토스테네스의 체는 다음의 과정으로 진행된다. 구하고자 하는 소수의 구간을 n, √n을 m이라고 한다. n개의 배열을 생성해준다. 2부터 m+1까지의 숫자들 중에 계산되지 않은 값을 확인한다. 계산되지 않은 값이 있다면 해당 값의 배수들을 계산 처리하고, 2번의 과정으로 돌아간다. 계산 처리되지 않은 값들을 출력한다. 위의 과정을 코드로 구현하면 다음과 같다. 1 2 3 4 5 6 7 8 9 10 def primeNumber(n): sieve = [True] * n m = int.. [Algorithm] 브루트 포스는 뭐야? 브루트 포스 알고리즘은 가능한 모든 경우의 수를 하나씩 확인해보는 알고리즘이다. 모든 경우의 수를 탐색하는 과정에서는 막대한 자원과 시간이 소모되지만 모든 경우의 수를 하나씩 확인해본다는 것은 100%의 정답을 도출할 수 있는 방법이기도 하다. 백준 2231번 문제를 예시로 확인해보자 문제 해설 문제를 확인하기 위해서는 주어진 수를 n, 계산 중인 값을 m이라 할 때 다음의 과정을 따른다. m의 각 자릿수와 자기 자신을 더한다. 해당 값과 n을 비교한다. 2번 과정이 참이면 결과를 출력하고 종료한다. 2번 과정이 거짓이면 m을 1 더해주고 1의 과정으로 돌아간다. 모든 과정이 끝나도 출력 값이 없다면 0을 출력한다. 다음은 "216"을 계산 중인 값을 그림으로 표현한 것이다. 위의 그림에서 볼 수 있듯이.. [Algorithm] 다익스트라 알고리즘 (2) 다익스트라 알고리즘의 구현에 대해서 다뤄보겠다. 앞서 다익스트라 알고리즘 (1)에서 설명했듯이 다익스트라 알고리즘 구현은 2가지 방법으로 가능하다. 간단한 구현, 높은 시간 복잡도를 가지고 있는 방법 우선순위 큐를 사용한 빠른 시간복잡도를 가지고 있는 방법 우선 간단한 구현, 높은 시간복잡도를 가지고 있는 방법의 코드이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 import sys input = sys.stdin.readline INF = int(1e9) n, m = map(int, input().split()) start = int(i.. [Algorithm] 다익스트라 알고리즘 (1) 다익스트라 알고리즘은 특정한 노드에서 다른 모든 노드의 최단거리를 구하는 알고리즘이다. 간선의 방향은 상관없지만 간선의 가중치가 음수이면 해당 알고리즘은 사용할 수 없다. 이러한 점 때문에 내비게이션, GPS 등에 많이 이용되는 알고리즘이다. 다익스트라 알고리즘은 2가지 방법으로 구현이 가능한데 1번째 방법은 O(V^2)의 시간복잡도를 가지고, 나머지 하나는 우선순위 큐를 이용하여 O(ElogV)의 시간 복잡도를 가지게 된다. 다익스트라 알고리즘의 순서는 다음과 같다. 출발 노드를 지정한다. 최단 거리 테이블의 값을 무한으로 설정한다. 방문하지 않은 노드 중에 최단 거리 테이블에서 가장 작은 값을 가진 노드를 선택한다. 해당 노드에서 다른 노드의 거리를 계산하여 최단 거리 테이블의 값을 갱신한다. 위의 .. [Algorithm] 다이나믹 프로그래밍이 뭐야? 다이나믹 프로그래밍은 중복되는 연산을 줄이기 위해 메모리 공간을 더 사용하여 연산 속도를 높이는 프로그래밍 기법으로 탑다운과 바텀업 방식이 있다. 한번 연산한 값을 기억해 두었다가 재활용하는 것과 같다. 우선 다이나믹 프로그래밍에는 조건이 따른다. 문제가 여러개의 작은 문제로 나눠질 수 있어야 한다. 문제의 정답을 작은 문제의 정답에서부터 구할 수 있다. 다음은 탑다운 방식과 바텀업 방식 설명이다. 탑다운 방식: 큰 문제를 해결하기 위해 작은 문제를 호출하여 해결 바텀업 방식: 작은 문제부터 답을 도출하여 문제를 해결 피보나치수열을 예시로 다이나믹 프로그래밍을 설명하겠다. 다음은 재귀 함수를 이용하여 구현한 피보나치 수열이다. 1 2 3 4 5 6 # 재귀함수를 이용한 피보나치 수열 def fibo(x).. [Algorithm] 탐욕법은 뭐야? 탐욕이란 지나치게 탐하는 욕심이라는 뜻이다. 여기서 알 수 있듯이 탐욕법은 주어진 상황에서 최선의 방법을 고르는 알고리즘을 말한다. 탐욕법은 앞서 소개했던 정렬 알고리즘, 탐색 알고리즘 등과는 다르게 사전에 외우고 있지 않아도 풀 수 있는 가능성이 많은 코딩 테스트 문제 유형이지만 그만큼 사전 지식보다는 수험생의 창의력, 논리력, 판단력, 관찰력 등 여러 가지 능력을 요구하는 문제 유형이다. "백준 2847번 게임을 만든 동준이" 라는 문제를 예로 탐욕법을 설명하겠다. 문제 확인 해당 문제에서는 더하기는 불가능하고 빼기는 가능하다. 따라서 "가장 뒤에 있는 수는 변하지 않는다."라는 생각을 할 수 있다. 그러므로 문제 해결을 위해서는 주어진 배열의 앞에서부터 값을 바꾸는 것이 아니라 뒤에 있는 숫자를 기.. 이전 1 2 3 다음
