알고리즘 & 자료구조/알고리즘
-
[Algorithm] 완전탐색 (Brute-Force Search ) 알고리즘알고리즘 & 자료구조/알고리즘 2021. 6. 20. 22:04
완전 탐색이란? 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법 '무식하게 푼다'라는 의미로 Brute-Force 라고 하기도 한다. 완전 탐색 기법 완전 탐색 방법을 이용하기 위해서 여러가지 알고리즘 기법이 이용된다. -단순 Brute-Force -비트마스크(Bitmask) -재귀 함수 -순열 (permutation) -BFS / DFS (너비 우선 탐색 / 깊이 우선 탐색) 1. 단순 Brute-Force 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법 2. 비트마스크 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식 3.재귀 함수 재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식 4.순열 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N 이므로 완전 ..
-
알고리즘 시각화 해서 볼 수 있는 사이트알고리즘 & 자료구조/알고리즘 2021. 3. 22. 21:12
www.pythontutor.com/visualize.html#mode=edit
-
[알고리즘] 삽입 정렬(Insertion Sort)알고리즘 & 자료구조/알고리즘 2021. 3. 6. 17:32
아래의 숫자들을 오름차순으로 정렬한다고 생각해보자 1 10 5 8 7 6 4 3 2 9 버블 정렬과 선택정렬을 사용 할 수도 있지만, 삽입 정렬을 사용하면 특정상황에 따라서는 보다 효율적으로 정렬할 수 있다. 다른 정렬들은 무조건 위치를 바꾸는 방식이였지만, 삽입정렬의 다른점은 '필요할 때만' 위치를 바꾼다는 것이다. 예를들어 보자, 아래와 같은 숫자들을 오름차순 정렬한다고 했을때, 삽입정렬은 1 10 5 8 7 6 4 3 2 9 바로 옆의 10과 대소를 비교한다. 10은 1의 앞 혹은 지금 현재 자리에 있을 수 있는데, 오름차순이기때문에 현재 위치를 그대로 유지하면 된다. 그다음 10 과 5를 비교해보면, 5가 더 작기때문에 10과 5의 자리를 바꿔준다. 조금 더 쉽게 생각하면 빈칸이 있다고 생각을 해..
-
[알고리즘] 선택 정렬 (Selection Sort)알고리즘 & 자료구조/알고리즘 2021. 3. 4. 11:28
예를 들어 *1 10 5 8 7 6 4 3 2 9 * 라는 숫자들을 오름차순으로 정렬하려고 한다고 가정해보자 사람이라면 직관적으로 보고 작은 수 를 찾아 순서대로 정렬하겠지만, 컴퓨터는 배열을 하나하나 읽기전 까지는 어떤 값이 들어있는지 알지 못한다. 따라서 정렬을 위해서는 알고리즘이 필요하다. 그 중에서도 선택정렬은 모든 배열을 탐색 후, 가장 작은 수를 앞으로 보내는 방식으로 동작한다. ex) arr[10] *1 10 5 8 7 6 4 3 2 9 * 모든 배열을 탐색 후 , 1이 가장 작은 숫자로 알맞은 위치에 있으므로, 이제는 1을 제외한 10 부터 9까지를 탐색해준다. *1 2 5 8 7 6 4 3 10 9 * 나머지 배열중에 가장 작은 수는 2이므로 arr[1] 인덱스의 값으로 넣어주고 원래 2..
-
[알고리즘] 버블 정렬알고리즘 & 자료구조/알고리즘 2021. 1. 19. 14:16
버블 정렬 버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법이다. 버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중한다. 접근법 자체는 간단하지만, 단 하나의 요소를 정렬하기 위해 너무 많은 교환이 발생할 수 있다. 예를 들어 6 3 8 5 2 7 4 1 이라는 숫자를 오름차순으로 정렬한다고 가정해보자. 우선 가장앞의 6 과 3을 비교해서 순서를 바꾼다. 3 6 8 5 2 7 4 1 이제 6 과 8을 비교해보면 교환할 필요가 없으므로 그대로 두고 바로 다음에 있는 쌓인 8과 5를 비교해서 순서를 바꾼다. 3 6 5 8 2 7 4 1 이런식으로 끝까지 진행한다면 3 6 5 2 7 4 1 8 위와 같이 정렬된다. 하지만 아직 오름차순으로 정렬이 되지 ..