정렬개념 정리정렬데이터를 특정한 기준에 따라서 순서대로 나열하는 것예) 카드 크기에 따라 순서대로 나열하도록 하는 것특징프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나데이터를 정렬하면 이진 탐색 (Binary Search)이 가능 (다음 챕터 내용)정렬 알고리즘 소개 다양한 알고리즘이 존재하지만, 이 중에 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬을 소개하려고 한다. 여기서는 모두 오름차순 정렬을 수행한다고 가정한다. 내림차순 정렬은 오름차순 정렬 알고리즘에서 크기 비교를 반대로 수행하면 된다.아래의 카드를 기준으로 정렬 알고리즘 설명 진행선택 정렬매번 가장 작은 것을 선택해 앞의 데이터와 변경하여 정렬알고리즘가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 변경다음으로 작은 데이터를 선택..
데크(Deque)란?큐(queue)는 선입선출(FIFO) 방식으로 작동하며, 스택(Stack)은 후입선출(LIFO) 방식으로 작동한다. 큐와 스택이 합쳐져 양방향에서 Push와 Pop을 할 수 있는 자료구조가 데크(Deque)이다. 앞, 뒤 방향에서 요소(element)를 추가하거나 제거할 수 있다. 큐와 스택은 반대쪽에 존재하는 요소를 Pop 하려면 O(n)의 시간이 필요하지만, 데크를 사용하면 어느 방향이든 O(1)의 시간으로 연산을 수행할 수 있다.파이썬 라이브러리 deque파이썬에서는 데크를 라이브러리로 사용할 수 있다. 아래의 공식문서에서 자세한 설명과 예시를 확인해 볼 수 있다. 여기에는 알고리즘 문제를 해결할 때 필요한 연산을 정리하려고 한다. collections — Container da..
문제 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 이해꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾음아래로 이동할 때는 대각선 오른쪽/왼쪽 한 칸으로만 이동 가능배열 triangle이 주어질 때, 최댓값을 반환하도록 작성풀이 (1)배열 triangle을 len(triangle) - 2(마지막에서 한 칸 위)부터 역으로 순회하여 수를 더함대각선 한 칸 아래 오른쪽/왼쪽 중에 더했을 때, 더 큰 값을 해당 칸에 대입코드 문제에 제공된 예로 순서를 설명하면, [2, 7, 4, 4]가 나타난 행부터 순회를 시작한다. 그리고 2+..
동적 계획법(Dynamic Programming, DP)이란?동적 계획법이란 하나의 큰 문제를 여러 개의 작은 부문제로 나누고, 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 기법이다.동적 계획법 vs 재귀적 호출재귀적 호출일반적인 재귀 방식은 동적 계획법과 매우 유사하다. 단, 재귀를 사용 시 동일한 작은 문제가 여러 번 반복되어 비효율적인 계산이 이루어진다는 것이다. 예를 들어 피보나치 수열을 살펴보자. 각 항을 구하기 위해 f(1), f(0)이 등장할 때까지 계속해서 반환하고, 더하는 작업을 진행한다. 또한 값을 따로 저장해두지 않기 때문에 이전에 구했던 값을 다시 처음부터 계산한다. 이러한 계산 방식 때문에 구하는 항이 증가함에 따라 계산 횟수가 기하급수적으로 늘어난다. 1, 1, 2..
