잡다로그

정렬(Sorting)이란, 데이터를 특정 기준에 따라 순서대로 나열하는 것. 데이터의 갯수가 적을 때 / 갯수가 많지만 범위가 특정되어 있을 때 / 이미 정렬된 경우 ... 다양한 상황에 따라 적절한 정렬 알고리즘이 공식처럼 사용된다. 1. 선택 정렬 처리되지 않은 데이터 중 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾼다. array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(array)): min_index = i for j in range(i+1, len(array)): if array[min_index] > array[j]: min_index = j array[i], array[min_index] = array[min_index], arr..

구현 ★ 시뮬레이션과 완전 탐색을 중심으로 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제들을 지칭한다. 프로그래밍 언어에 따라 구현 문제의 유형이 달라질 수 있다. ex) 실수 연산을 다루고 특정 소수점까지 출력하기, 문자열을 기준에 따라 끊어 처리하기, 적절한 라이브러리 찾기(순열 등) 등의 문제가 있다. 일반적으로 2차원 공간은 행렬(Materix)의 의미로 사용된다. (2차원 리스트) 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용된다. 1. 상하좌우 (시뮬레이션 유형) 여행가 A가 입력된 계획서를 따라 움직였을 때 최종적으로 도착할 지점의 좌표를 출력하라. * 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류됨. 구현의 대표적..

그리디 알고리즘 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법. ex) 루트부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶다. A. 매 상황에서 가장 큰 값 고르기 위의 경우에서도 확인할 수 있듯이 일반적으로 그리디는 최적의 해를 보장할 수 없을 때가 많다. 그러나 코딩테스트에서 출제되는 '그리디 유형'의 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 것이고 이를 알아내는 문제인 것이다. 즉 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 그래서 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이뤄 출제된다. 그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 다음 두 조건을 ..