Python 코딩테스트/이것이 취업을 위한 코딩 테스트다 (6) 썸네일형 리스트형 다이나믹 프로그래밍(동적 계획법) 다이나믹 프로그래밍: 중복되는 연산을 줄이자 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있다. 대표적인 방법이 다이나믹 프로그래밍 기법이다. 다이나믹 프로그래밍(Dynamic Programming) 기법은 동적 계획법이라고 표현하기도 한다. 다이나믹 프로그래밍에 대해 알아보기 전에 기존의 알고리즘으로 해결하기 어려운 문제 중에서 다이나믹 프로그래밍으로 해결할 수 있는 문제를 살펴보자. 다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로 피보나치 수열이 있다. 피보나치수열은 이전 두 항의 합을 현재의 항으로 설정하는 특징이 있는 수열이다. 피보나치수열은 다음과 같은 형태로 끝없이 이어진다. 수학자들은 점화식을 사용해 수열의 항이 이어지는 형태를 간결하게.. 이진 탐색: 탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 이진탐색: 반으로 쪼개면서 탐색하기 이진탐색(Binary Search)은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색 과정이다. 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 살펴보자. step1: 시작점과 끝점을 확인한 다음 둘 사이에 중간점을 정한다. 중간점이 실수일 때는 소수점 이하를 버린다. 그림에서 각각의 인덱스는 시작점은 [0].. 정렬 알고리즘: 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬, sort 정렬 알고리즘 개요: 정렬(Sorting)이란 데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 데이터를 가공할 때 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해서 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 가장 많이 사용되는 알고리즘 중 하나다. 정렬 알고리즘으로 데이터를 정렬하면 이진 탐색(Binary Search)이 가능해진다. 정렬 알고리즘은 이진 탐색의 전처리 과정이기도 하니 제대로 알고 넘어가자. 정렬 알고리즘은 굉장히 다양한데 이 중에서 많이 사용하는 선택 정렬, 삽입 정렬, 퀵 정렬, 계수 정렬만 학습해보자. 1.1 선택 정렬: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 선택해 앞에서 두 번째 데이터와 .. DFS/BFS: 깊이 우선 / 너비 우선 탐색 알고리즘 DFS DFS는 Depth-First Search, 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 스택 자료구조에 기초한다는 점에서 구현이 간단하다. 실제로는 스택을 쓰지 않아도 되며 탐색을 수행함에 있어서 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다는 특징이 있다. 또한 DFS는 스택을 이용하는 알고리즘이기 때문에 실제 구현을 재귀 함수를 이용했을 때 매우 간결하게 구현할 수 있다. DFS 예제 # DFS 메서드 정의 def dfs(graph, v, visited): # 현재 노드를 방문처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 다른 노드를 재귀적으로 방문 for i in graph[v]: .. 구현: 아이디어를 코드로 바꾸는 구현 코딩 테스트에서 구현(implementation)이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다. 어떤 문제를 풀든 간에 소스코드를 작성하는 과정은 필수이므로 구현 문제 유형은 모든 범위의 코딩 테스트 문제 유형을 포함하는 개념이다. 그런 의미에서 알고리즘 교재에서는 대부분 구현을 별도의 유형으로 다루지 않지만, 취업을 목표로 하는 코딩 테스트에서는 구현이 중심이 되는 문제가 자주 출제되기에 다른 알고리즘을 배우기 전에 먼저 다루고자 한다. 이 책에서는 완전 탐색, 시뮬레이션 유형을 모두 '구현' 유형으로 묶어서 다루고 있다. 완전 탐색은 모든 경우의 수를 주저 없이 다 계산하는 해결 방법을 의미하고, 시뮬레이션은 문제에서 제시한 알고리즘을 한 단계식 차례대로 직접 수행해야 하는 문제 유형을.. 그리디: 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 그리디 알고리즘은 단순하지만 강력한 문제 해결 방법이다. 이 알고리즘 유형은 국내 알고리즘 교재에서 단어 그래도 번역하여 '탐욕 법'으로 소개된다. 이름에서 알 수 있듯이 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다. 여기서 탐욕적이라는 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법'을 의미한다. 코딩 테스트에서 만나게 될 그리디 알고리즘의 문제 유형은 앞으로 다루게 될 알고리즘과 비교했을 때 '사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형'이라는 특징이 있다. 정렬, 최단 경로 등의 알고리즘 유형은 그 알고리즘의 사용 방법을 정확히 알고 있어야만 해결 가능한 경우가 많다. 그리디 알고리즘 유형의 문제는 아주 다양하기 때문에 암기한다고 해서 항상 .. 이전 1 다음
