본문 바로가기

□ 이론/알고리즘

 (12)
각 방향으로 이동한 위치 값을 반복문으로 구하는 방법 ▶방향에 따른 이동 위치 값 반복문으로 구하기알고리즘 문제를 해결하다 보면 어떤 좌표에서 4~8방향으로 이동한 위치 값이 필요한 경우가 있습니다.만약 매번 모든 방향으로 이동한 위치 값을 확인해야 한다면 반복문을 통해 구현하는 것이 편리합니다. 예를 들어, 2차원 공간의 (x,y)의 위치에서 상/하/좌/우 네 방향으로 한 칸씩 이동한 위치 값이 필요하다면 (x는 행, y는 열을 나타냅니다!)상 : (x-1, y)하 : (x+1, y)좌 : (x, y-1)우 : (x, y+1) 이렇게 네 개의 위치 값을 구해야 합니다. 이해를 돕기 위해 (3,3)에서 상/하/좌/우 네 방향으로 이동했을 때 위치 좌표값을 나타낸 그림을 그려보았습니다. 이 네 방향의 위치 값을 편하게 구하기 위해서 아래와 같은 방법을 씁니다..
조합 생성 알고리즘 한번에 정리하기 ▶조합 (Combination)서로 다른 n개의 원소 중에 r개를 순서와 상관 없이 뽑은 것을 조합이라고 합니다. 뽑아낼 수 있는 조합의 모든 경우를 알아내야 하는 문제들이 많습니다.기본적인 구현 문제이지만 공부하지 않으면 어떻게 구현해야 할지 몰라 막막하게 느껴지기도 합니다. 조합을 코드로 구현하기 위해서 재귀 함수에 익숙해질 필요가 있습니다.재귀함수를 이해하기 위해 백준 온라인 저지에서 '피보나치 수를 구하는 문제'나 'N과 M'과 같은 문제들을 풀면서 재귀함수에 익숙해지도록 연습하는 것을 추천합니다. 1234567891011121314151617181920212223242526272829303132333435#include#includeusing namespace std; int n,r;vector..
[알고리즘] 시간 복잡도 쉽게 이해하기 ▶시간 복잡도, 이정도는 알고 있어야 한다! 알고리즘을 공부할 때 가장 먼저 나오는 개념이 시간 복잡도입니다. 문제 해결에 있어서 시간 복잡도를 줄이는 방법을 이해하고 활용하는 것이 알고리즘을 배우는 주된 목적이기 때문이죠. 시간 복잡도를 표기할 때 가장 일반적으로 사용되는 것은 빅오(O)-표기법 입니다. 어떤 알고리즘으로 문제를 해결하기 전에 입력 값에 따라 무엇을 어떤 변수로 놓을지 결정하고 난 뒤, 문제를 해결하는데 필요한 연산의 횟수를 식으로 구합니다. 구해진 식에서 최고 차항만을 남깁니다. 그 식에 최악의 입력 크기 값을 대입해보고 그 때에도 충분히 빠른 시간 내에 해결이 가능한지를 판단합니다. 예를들어 1부터 N까지의 누적합을 구하는 문제가 있다고 합시다. N의 범위는 1
삽입 정렬(Insertion sort) ▶삽입 정렬 (Insertion sort)앞에서부터 정렬될 하나의 데이터를 왼쪽으로 비교하며 swap해서 제 자리를 찾아가도록 정렬시키는 방법이다. 정렬될 데이터가 처음부터 제 위치에 있다면 바로 다음 데이터를 확인하게 되므로, 배열에 데이터가 대부분 정렬되어 있는 경우라면 삽입 정렬이 유리하다. 하지만 데이터가 정렬되어 있어야 하고 삽입/삭제가 빈번한 경우 처음부터 set/map에 데이터를 저장하여 사용하는 게 더 효율적이다. int arr[7] = {5,2,7,4,3,6,1}; 이런 배열이 선언되어있고, 이 배열의 원소들을 정렬한다고 해보자. 이해를 돕기 위해 표를 그려보았다. N개의 원소를 순서대로 확인하면서 바로 앞에 자신보다 큰 원소가 있다면 자리를 바꾸는데, 자신의 앞에 자신과 같거나 작은 원..
합병 정렬 (Merge sort) ▶합병 정렬 (Merge sort)분할 정복 기법으로 데이터를 정렬하는 방법이다. 가장 많이 쓰이는 정렬 기법이며, 크기 N의 데이터를 정렬해야하는 경우 N만큼의 공간이 더 필요하다. 데이터를 딱 한 번만 훑어서 정렬하기 위해서, 배열 arr의 데이터를 정렬하여 배열 tmp에 저장한 뒤 정렬되어있는 tmp의 데이터를 다시 arr에 반영하는 방법을 쓰기 때문이다. 1. 정렬할 N개의 데이터에 대해 범위를 계속해서 반으로 나눈다. (나뉘어진 범위의 데이터들을 덩어리 라고 표현하겠다.) 2. 덩어리의 크기가 1일 때부터 덩어리를 정렬하면서 합친다. 3. 그러면 크기 2의 정렬된 덩어리 하나가 만들어지게 되고, 그 덩어리는 또 다른 데이터 덩어리와 정렬하면서 합친다. 4. 그렇게 합쳐진 덩어리의 크기가 N이 될..
퀵 정렬(Quick sort) ▶퀵 정렬분할 정복 기법(Divide and conquer)으로 데이터를 정렬하는 방법이다. 1. pivot 값을 정하고 그 값보다 작거나 같은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 이동시킨다. (정복) 2. 더이상 이동시킬 데이터가 없다면 pivot 위치 기준으로 왼쪽/오른쪽으로 분할하여 재귀적으로 수행한다. (분할)재귀호출될 함수는 매개변수로 left, right를 가지고, left는 정복해야할 범위의 시작지점, right는 끝 지점을 의미한다. 인자 값으로 left와 pivot-1을 넘겨 [left, pivot-1] 범위에 대해 퀵 정렬을 재귀적으로 수행하고 인자 값으로 pivot+1과 right를 넘겨 [pivot+1, right] 범위에 대해 퀵 정렬을 재귀적으로 수행한다. 탈출 조건인 l..
프림(Prim)과 크루스칼(Kruskal) 알고리즘 ▶신장 트리 (Spanning Tree) 그래프의 모든 정점을 연결한 Tree를 말한다. 하나의 그래프에서 신장 트리는 여러 형태가 나올 수 있다. ▶최소 신장 트리 (MST : Minimum Spanning Tree) 다음과 같은 조건을 만족하는 신장 트리를 말한다.1. 간선의 가중치 합이 최소이다.2. 사이클이 존재하지 않는다.3. 모든 정점이 연결되어야 한다. (N개의 정점은 N-1개의 간선으로 연결됨)하나의 그래프에서 MST도 역시 여러 형태가 나올 수 있다. MST를 구하는 대표적인 알고리즘으로 프림 알고리즘과 크루스칼 알고리즘이 있다. ▶프림 알고리즘 (Prim algorithm) 시작 정점을 기준으로 가중치가 가장 작은 간선과 연결된 정점을 선택하며 트리를 확장시켜나가는 방법이다.트리 집합에..
계수 정렬(Counting sort) ▶계수 정렬(Counting sort)정렬할 데이터의 개수를 카운트하여 정렬하는 방법이다.O(N+k)의 시간이 걸리며, k는 정렬할 데이터의 최대 값을 의미한다.양의 정수이면서 k값이 작은 경우 활용하기 좋은 정렬 방법이다. 정렬할 데이터가 6,4,3,1,6,5,1,4,5라면 크기 7의 배열이 필요하다.정렬할 데이터를 처음부터 끝까지 보면서 해당 숫자의 개수를 구하고, 그 값을 누적 합으로 바꾸어 정렬에 활용한다. 좀 더 자세히 살펴보자.정렬해야 할 데이터가 6,4,3,1,6,5,1,4,5인 경우 배열에는 아래와 같이 저장된다. [해당 숫자의 개수][0] [1] [2] [3] [4] [5] [6] 0 2 0 1 2 2 2 이 값을 누적 합으로 바꾼다. [숫자 개수의 누적 합][0][1][2][3][4][..

티스토리툴바