본문 바로가기

분류 전체보기

 (433)
다이나믹 프로그래밍(Dynamic Programming) 1. 의미 다이나믹 프로그래밍이란, 동적계획법이라고도 불리는데 위키백과에 따르면 다음과 같다. 수학과 컴퓨터 공학, 그리고 경제학에서 동적 계획법(動的計劃法, dynamic programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 이것은 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. 복잡한 문제를 간단한 여러 개의 문제로 나누어 푼다는 것이 핵심이다! 요약하면 큰 문제 -> 작은 문제로 나눠서 푸는 알고리즘이다. 그런데, 분할정복도 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이다. 단, 분할 정복은 작은 문제들이 중복이 되진 않지만, 다이나믹 프로그래밍은 중복된 작은문제를 푸는 것이라는 차이점이..
그래프의 심화 플러드 필 어떤 위치와 연결된 모든 위치를 찾는 알고리즘 연결 요소를 찾기와 유사한 문제 -> 그래프 문제 그렇지만 인접 행렬이나 리스트 만들 필요 없다, 단순히 주어진 이차원 배열을 통해 dfs, bfs로 탐색하면 모든 문제를 해결할 수 있다. 1. 단지번호 붙이기 문제 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로..
그래프의 탐색(DFS, BFS) 그래프의 탐색 목적 : 시작점으로부터 시작해서 모든 정점 한번씩 탐색 DFS(Depth First Search) 깊이우선탐색 - 스택(Stack) 통해 갈 수 있을 때 까지 계속 가다가 갈 수 없으면 이전 정점으로 돌아오기 1) 인접 행렬 통한 구현 2) 인접 리스트 통한 구현 3) 시간복잡도 인접행렬 O(V^2) 인접리스트 O(V+E) BFS(Breath First Search) 너비우선탐색 - 큐(Queue) 통해 현재 갈 수 있는 정점 다 담아둔 다음에 차례로 탐색. 1) 인접 행렬 통한 구현 2) 인접 리스트 통한 구현 3) 시간복잡도 인접행렬 O(V^2) 인접리스트(V+E) 1. DFS & BFS #include #include #include #include using namespace std..
그래프(Graph) 그래프는 용어가 많고 중요한 만큼 용어 개념을 확실히 정리해야 한다. 1. 그래프의 개념 먼저 그래프의 개념은, 일련의 노드(node, vertex, 정점, 꼭지점)V와 엣지(edge, 간선, 변) E로 구성된 자료구조이다. 이러한 그래프의 정보는 정점과 정점 간의 간선이 어떻게 연결되어 구성이 되어있는지의 정보도 포함된 형태를 뜻한다. 그래프에서 경로(path)란 노드들의 나열로 구성된 묶음을 뜻한다. 일종의 시퀀스로, 노드들의 간선을 따라 하나의 경로를 구성하게 된다. 이 때 Edge가 겹치지 않게 되면 단순 경로(Simple path)라고 일컫는다. 위의 이미지의 경우 v1-v2-v3-v4-v5 와 같이 v1~v5로 가는 path를 나열할 수 있다. 사이클의 경우에는 경로 중에서 출발점과 도착점이 ..
브루트포스-N과 M 1. N과 M 문제 참고 : https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net 풀이 #include #include #include using namespace std; void make_nm(int, int, int); vector a; vector c; int main() { int m, n; cin >> n >> m; //입력받기 a.assign(10, 0); // 할당 c.assign(10, false); // 할당 make_n..
비트마스크(BitMask) 비트마스크에 공부하기 앞서 기본적인 비트연산에 대해 알아야 한다. 비트연산이랑 &(AND), |(OR), ^(XOR), ~(NOT), (Shift Right) 로 이루어진 bit 간의 연산을 수행하는 것이다. 해당 연산들을 통해 비트마스크를 이용할 수 있는데, 비트마스크란 쉽게 말해 정수로 집합을 나타낼 수 있는 것이다. 570 = 1000111010 = 2^9 + 2^5 + 2^4 + 2^3 + 2^1 으로 나타내서 1,3,4,5,9의 부분집합을 뜻하는 것이다. 배열보다 정수(비트마스크)로 쓰면 공간적인 장점, 다른 배열에 넣을 수 있는 점. 0~N-1 의 정수로 이루어진 집합을 나타낼 수 있다. (1~N 을 쓰려면 2배의 수가 필요 -> 따라서 줄여서 쓰기) 비트마스크 연산 S & (1
재귀함수(Recursive Function) 재귀함수는 기본적으로 반복적으로 함수를 호출해서 많은 메모리를 차지하면서 함수 stack을 통해 메모리에 부담을 주는 것으로 알려져있다. 그럼에도 불구하고 재귀함수를 사용하는 이유는 명확하다. 알고리즘 자체가 재귀적으로 표현이 더욱 쉬울 때가 존재한다. 예를 들어 팩토리얼을 구하는 공식을 살펴보면 다음과 같다. 해당 공식을 보면 n! = (n-1)! * n (n>0) 이 부분 자체가 재귀함수의 형태와 매우 닮아있다. 그래서 몇몇 알고리즘을 계산하는데 있어, 재귀함수가 유용할 때가 존재한다. 재귀함수를 사용할 때 주의해야할 3가지가 있다. 1) 종료조건(실패조건) : 재귀함수 호출 중 조건에 벗어나 그만 호출해야할 때 2) 종료조건(성공조건) : 재귀함수 호출 중 조건을 만족한 답을 구해서 그만 호출해야 ..
순열(Permutation) 구하기 수학에서, 순열(順列, 문화어: 차례무이, 영어: permutation 퍼뮤테이션[*]) 또는 치환(置換)은 순서가 부여된 임의의 집합을 다른 순서로 뒤섞는 연산이다. 다시 말해, 순열은 숫자 배열의 순서를 뒤섞는 연산이다. 예를 들어 1,2,3 세 숫자 순열은 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 다음과 같이 나열된다. 이러한 순열의 특징 중 하나는 특정 기준점 다음의 오름차순 정렬에서 기준점 다음으로 오는 가장 작은 숫자와 위치를 교환한 후 내림 차순 정렬로 바뀐다. 이러한 특징을 살려, 순열들을 차례로 구하여 값을 구할 수 있다. 1. A[i-1] A[i-1] 를 만족하는 가장 큰 j를 찾는다 3. A[i-1]과 A[j]를 swap 한다 4. A[i]부터 순열을 뒤집는다 ..

티스토리툴바