개발자로 살아남기

버블 정렬 (Bubble Sort) 버블 정렬 (Bubble Sort) 가장 단순한 정렬 알고리즘 인접한 요소와 정렬 기준(오름차순, 내림차순)대로 교환 안정 정렬 (stable sort) : 정렬 후에도 같은 값들 끼리의 순서가 보장됨을 의미 제자리 정렬 (in-place sort) : 데이터에 필요한 공간을 제외하고 추가적인 공간이 필요없음을 의미 정렬한 데이터의 개수가 적을때는 나쁘지 않은 속도를 보임 버블 정렬 방법 (오름차순 기준) 첫 번째 사이클이 끝나면 맨 마지막 값이 정렬되고, 두 번째 사이클이 끝나면 뒤에서 두 번째의 값이 정렬된다. 이같은 과정을 계속 반복하면 최종적으로 정렬이 된다. 버블 정렬의 성능 시간복잡도 최악의 경우 : O(n^2) 최선의 경우 : O(n) 최악의 경우 : 모든..

깊이 우선 탐색 깊이 우선 탐색 DFS (Depth-First Search) 깊이 우선 탐색 시 끝없이 깊어지는 것을 방지하기 위해 깊이 제한 적용 (조건을 이용) 목표 노드에 도달하지 못하면 부모노드로 되돌아감 (부모노드로 되돌아가는 것을 백트래킹(backtracking)이라고 함) 하나의 정점에서 아래쪽으로 깊게 탐색 후 더이상 탐색이 불가능하면 되돌아가 인접한 다른 노드를 탐색 시간 복잡도 : O(V + E) V : 정점의 개수 (위 사진에서 A, B, C, D, E, F, G) E : 간선의 개수 (각 정점을 잇는 선) 공간 복잡도 : O(V) 방문 여부를 확인하기 위한 visited 배열 추가 필요 방문 여부를 확인하기 위한 visited 배열 필요성 방문 여부를 체크하지 않으면 두 번 탐색할 ..

순열 순열 하나의 집합을 다른 순서로 뒤섞는 것 n개의 집합에서 순열의 총 개수는 n! ex) n = 5, 5x4x3x2x1 = 순열의 총 개수 nPr 수식 (P = Permutation 약자) 3P2 = 3! / (3-2)! = 6 / 1 = 6 (1, 2) / (1, 3) / (2, 1) / (2, 3) / (3, 1) / (3, 2) 총 6개 재귀로 구현 가능 자주 사용되는 swap, visited 방법으로 구현 완전탐색 문제에서도 자주 나올 수 있음 swap을 이용한 순열 배열의 값을 직접 교환해서 구함 Depth를 이용한 풀이 Depth와 r의 값이 같으면 모두 다 뽑았다는 것이므로 결과값 출력 순열 함수가 종료됐을 때 배열의 값을 다시 원상복구 해주어야 함 (그 다음 수와 다시 순열을 계산해야..

그리디(Greedy) 알고리즘 (탐욕 알고리즘) 참고 사이트 : 1. https://www.geeksforgeeks.org/greedy-algorithms/ 2. https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 그리디 알고리즘 매 순간마다 최적의 값을 찾음 매 순간의 최적값을 모두 더한것이 전체의 최적값이길 바람 결과값이 항상 최적값이라고 보장할 수 없음 탐욕스러운 선택 조건, 최적 부분 구조 조건이 만족해야만 최적해를 구할 수 있음 탐욕스러운 선택 조건 : 앞서 선택한 것이 이후의 선택에 영향을 미치지 않음 최적 부분 구조 조건 : 문제에 대한 최적해가 부분 문제에 대해서도 최적해가 됨 조건이 만족..