huiyu's blog

Dynamic Programming(DP) , 동적 계획법 - 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 -> 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것 -> 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결 * 동적계획법은 계산 횟수를 줄일 수 있다. 특히 하위 문제의 수가 기하급수적으로 증가할 때 유용 위키 (https://ko.wikipedia.org/wiki/%EB%8F%99%EC%A0%81_%EA%B3%84%ED%9A%8D%EB%B2%95) *피보나치 수로 DP 기초 다지기 F(0) = 0 F(1) = 1 F(N) = F(N-1)+F(N-2) (N>=2) 0 ..

문제)타일채우기(S)2x1 혹은 2x2 크기의 타일을 2xn 크기의 직사각형 모양 틀에 넣으려고 한다. 이 때 가능한 경우의 수를 구하여라. 경우의 수가 커지므로, 주어지는 수 m으로 나눈 나머지를 출력한다. 첫 줄에는 직사각형 틀의 가로 길이 n이 주어진다. 둘째 줄에는 m이 주어진다 (1

문제)Combination nCk 는 n개 중 k개를 고르는 방법의 수이다. nCk를 구하는 일반식은 다음과 같다. 위 식은 n!을 이용하기 때문에 n이 커지면 overflow가 발생하여 정확한 값을 구할 수가 없다. 물론 위 방법 외에도 다양한 점화식으로 구할 수 있다. nCk를 정확하게 구하는 프로그램을 작성하시오. 첫 번째 줄에 n과 k가 공백으로 구분되어 입력된다. (단, 1 n >> k; cout

DFS/BFS의 경우 사실 이론은 조금만 읽어도 금방 이해가 가능한데요,그러나 막상 처음 구현하려 하면 바로 구현하기 힘든 경우가 많은데 알고리즘 문제를 반복적으로 풀며 구현해보면 금방 익숙하게 구현할 수 있게 됩니다. 다음은 DFS/BFS 학습을 위해 풀었던 문제들로[기본]은 간단하게 DFS/BFS를 이용하여 풀 수 있는 문제이고, [응용]은 DFS/BFS 중에도 조금 응용을 해야 풀 수 있는 문제입니다기본적인 이론을 학습한 후 아래 문제들을 순서대로 풀어보면 좋을 것 같습니다. [기본]1. 바이러스 : https://www.acmicpc.net/problem/26062. 단지번호 붙이기 : https://www.acmicpc.net/problem/26673. 보물섬 : https://www.acmic..

관계기반 알고리즘 설계(1) 탐색기반 알고리즘 설계 : 컴퓨터의 빠른 연산 속도를 이용하여 짧은 시간에 가능한 해의 집합을 탐색하면서 최적의 해를 구하는 기술적인 방법(2) 관계기반 알고리즘 설계 : 해를 구하는 행위를 하나의 함수로 표현하고 이 함수들의 관계를 이용하여 해를 구하는 방법 - 문제의 정의 및 상태를 함수로 정의, 이 함수들 간의 관계를 점화식 혹인 이와 유사한 형태로 표현, 수학적 귀납법/점화식 등의 표현 기반 수학적 귀납법 - 자연수 n에 관한 명제 P(n)이 모든 자연수에 대해서 성립함을 증명하기 위한 수학의 증명법 중 한 방법 - 다음의 두가지 단계로 증명 1) P(1)이 성립함을 보인다. 2) P(k)가 성립한다고 가정하고 P(k+1)이 성립함을 보인다. - 수학적 귀납법을 이용한..

3. 깊이우선탐색(Depth first search, dfs)그래프 중 회로(cycle)가 없는 그래프를 트리라고 한다. 이 트리의 가장 위에 있는 정점에서 출발하여 모든 정점들을 깊이 우선으로 탐색한다. 출발 정점을 트리의 가장 위에 있는 정점으로 하고, 한 정점에서 이동 가능한 정점이 여러개 있을 경우 왼쪽 정점부터 방문한다고 가정하면, 단계별 탐색 과정은 다음과 같다. 탐색과정에서 3단계 이후 더이상 진행할 정점이 없어 더이상 진행하지 않는다.이처럼 더이상 진행할 수 없을 때 다시 이전 정점으로 되돌아가는 과정이 필요한데, 일반적으로 이러한 과정을 백트랙(backtrack)이라고 한다. 백트랙은 비선형구조의 탐색에서 매우 중요하다. 백트랙은 스택(stack)이나 재귀함수(recursion)을 이용하..

2. 비선형 구조 탐색 - i번째 원소를 탐색한 다음 그 원소와 연결된 다른 원소를 탐색하려고 할 때, 여러 개의 원소가 존재하는 탐색구조 - 자료가 트리나 그래프로 구성되어 있을 경우 비선형구조, 이를 모두 탐색하는 것을 비선형 탐색이라 함. - 선형과 달리 자료가 순차적이지 않아 단순히 반복문을 이용하여 탐색하기에는 어려움 - 스택이나 큐와 같은 자료구조를 활용하여 탐색하는 것이 일반적. -일반적으로 깊이우선탐색(depth first search, dfs)과 너비우선탐색(breadth firrth search, bfs)으로 나뉨. (1) 비선형구조 : 그래프의 구성- 트리를 이루는 기본 요소를 정점(vertex)과 간선(edge)라 한다.- 원은 정점, 선분은 간선 - a-b 보통간선 - b-c 방향..

※ 탐색이란? - 같은 형태의 한 개 이상의 자료들이 모여 있는 집합에서 특정 자료를 찾는 모든 작업 - 탐색할 자료가 저장되어 있는 구조를 먼저 파악하는 것이 중요 (탐색 구조가 직접적으로 드러난 경우는 쉬운문제, 직접 드러나지는 않으나 문제 해결과정에서 자체적으로 구조화하며 탐색하는 경우 중급 이상 문제) ※ 탐색기반설계 - 주어진 문제에서 주어진 데이터를 특성에 맞도록 구조화하고 이 자료를 적절한 방법으로 탐색해 나가면서 원하는 해를 찾는 알고리즘 설계법 - 전체를 탐색하는 전체탐색법과 탐색할 영역을 적절한 방법으로 배제하여 탐색의 효율을 높은 부분탐색법이 있다. ※ 탐색이 되는 구조 - 선형구조 : 배열이나 연결리스트로 표현될 수 있는 구조 - 비선형구조 : 트리나 그래프의 형태로 표현되는 구조 ..

퀵소트1. Pivot(기준값)을 정한다.2. Pivot보다 작은 원소들은 왼쪽으로, pivot보다 큰 원소들은 오른쪽으로 보낸다.3. pivot을 기준으로 왼쪽 배열과 오른쪽 배열을 새로운 배열로 정하고, 각 배열 구간에 대해 1번 과정을 재귀적으로 반복한다. * 일반적으로 처음의 원소 또는 가장 마지막 원소를 pivot으로 잡는방법을 이용 12345678910111213141516171819202122232425262728293031323334353637383940414243#include#define SWAP(A,B) {int temp = A; A=B; B=temp;}int arr[101]; void quick_sort(int s, int e){ if(s>=e) return; int p = s; in..

[C] char *str와 char str[] 의 차이 C/C++ 2014/06/06 15:54 http://blog.naver.com/chhh92/220022245722 전용뷰어 보기 ​char *str와 char str[]은 문자열을 담기위해 사용합니다. 용도는 같더라도 담는 방법이 다릅니다. 잘 알고 상황에 맞게 문자열을 담으면 되겠습니다. 당연한 소리지만, char *str는 포인터고 char str[]는 배열입니다. 얼핏 보면 둘다 문자열을 담거나 작업할때 쓰여서 같아보일지라도, char *str도 char str[]처럼 "선언과 동시에 초기화"를 할 경우 확실하게 차이가 납니다. 우선 역할을 보면 char *str은 주소를 담고, char str[]은 값을 담습니다. 만약 선언과 동시에 초기화..