[Algorithm] DP(Dynamic Programming) 동적계획법

동적계획법(DP) 이란? 하나의 큰 문제를 여러개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할때 사용하는 것 계산한 값을 저장해두는 메모리 장소 캐쉬(cache)에 저장하고, 답을 여러번 계산(중복)하는 대신 한번 만 계산해서 계산결과를 재활용함으로써 속도 향상을 꾀할 수 있는 알고리즘이다 * 그럼 분할 정복이랑 뭐가 다른건가요? 동적계획법과 분할 정복이 차이가 발생하는 부분은 문제를 나누는 방식이다 분할 정복은 단지 큰문제를 작은 문제로 나누어 푸는 것으로 중복된 것이 없다 동적 계획법은 어떤 부분 문제는 두개 이상의 문제를 푸는 데(반복이 일어남) 사용될 수 있기 때문에, 답을 여러번 계산 하는 대신 한번만 계산한다(중복된 것 활용) * 그럼 다른 dfs등 과 같은 재귀함수 쓰..

[코딩테스트 / c++] 봉우리, 이차원 배열 활용

문제 지도 정보가 N*N 격자판에 주어집니다. 각 격자에는 그 지역의 높이가 쓰여있습니다. 각 격자 판의 숫자 중 자신의 상하좌우 숫자보다 큰 숫자는 봉우리 지역입니다. 봉우리 지역이 몇 개 있는 지 알아내는 프로그램을 작성하세요. 격자의 가장자리는 0으로 초기화 되었다고 가정한다. 만약 N=5 이고, 격자판의 숫자가 다음과 같다면 봉우리의 개수는 10개입니다. ▣ 입력설명 첫 줄에 자연수 N이 주어진다.(1

[코딩테스트 / c++] 멀티태스킹(카카오 먹방 문제 변형)

2019년 카카오 코딩테스트 무지의 먹방라이브 문제를 변경한 문제입니다. https://programmers.co.kr/learn/courses/30/lessons/42891 코딩테스트 연습 - 무지의 먹방 라이브 programmers.co.kr 문제 현수의 컴퓨터는 멀티태스킹이 가능하다. 처리해야 할 작업이 N개 들어오면 현수의 컴퓨터는 작업을 1부터 N까지의 번호를 부여하고 처리를 다음과 같이 한다. 1) 컴퓨터는 1번 작업부터 순서대로 1초씩 작업을 한다. 즉 각 작업을 1초만 작업하고 다음 작업을 하는 식이다. 2) 마지막 번호의 작업을 1초 했으면 다시 1번 작업으로 가서 다시 1초씩 후속 처리를 한다. 3) 처리가 끝난 작업은 작업 스케쥴에서 사라지고 새로운 작업은 들어오지 않는다. 그런데 현..

[코딩테스트 / c++] 백준 1158 요세푸스 문제

https://www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 요세푸스 유사한 문제를 풀다가 백준에 비슷한 문제가 있어서 연습삼아 풀어보았다. 요세푸스는 조세퍼스라고도 하며 순열을 가리킨다. > 요세푸스 유사문제 포스팅 https://meongj-devlog.tistory.com/201 [코딩테스트 / c++] 공주 구하기 (조세퍼스) 문제 문제 풀이 #include #include #include using namespace std; int main(){ int n, k, pos=0, bp=0, cnt=0, i; scanf("%d %d", &n, ..

[코딩테스트 / c++] 공주 구하기 (조세퍼스) 문제

문제 풀이 #include #include #include using namespace std; int main(){ int n, k, pos=0, bp=0, cnt=0, i; scanf("%d %d", &n, &k); vector prince(n+1);//0으로 초기화 while(1){ pos++; if(pos>n) pos=1;//pos=9일 경우 1로 pos초기화 if(prince[pos]==0){ cnt++; if(cnt==k){ prince[pos]=1;//out cnt=0; bp++;//n-1명 out명수 체크 } } if(bp==n-1) break; } for(i=1; i

[알고리즘] 병합정렬(Merge Sort)의 개념 with c++

병합정렬 또는 합병정렬은 정렬할 데이터들을 일단 반으로 쪼개고 각 각 정렬한 후 나중에 합치는 알고리즘이다. 비교 기반 정렬 알고리즘이고, 일반적인 방법으로 구현했을 때 안정 정렬에 속하며 분할 정복 알고리즘의 하나이다. 매번 정렬된 데이터를 담을 배열 공간이 추가적으로 필요하다는 점에서 메모리 사용이 비효율적인 문제가 있다. 이에 병합 정렬의 시간 복잡도는 어떤 상황에서도 O(N*logN)이다. 병합 정렬 c++ 코드구현 #include #include //배열 #include using namespace std; int a[101], b[101], c[300]; int main(){ // 두 배열 합치기 int n, m, i, p1=1, p2=1, p3=1;//포인트 scanf("%d", &n); f..

[코딩테스트 / c++] Inversion Sequence (삽입 정렬 풀이)

문제 1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예를 들어 다음과 같은 수열의 경우 4 8 6 2 5 1 3 7 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래 의 수열을 출력하는 ..

[코딩테스트 / c++] Least Recently Used(2018 카카오 캐시 문제 변형)

문제 캐시메모리는 CPU와 주기억장치(DRAM) 사이의 고속의 임시 메모리로서 CPU가 처리할 작업 을 저장해 놓았다가 필요할 바로 사용해서 처리속도를 높이는 장치이다. 워낙 비싸고 용량이 작아 효율적으로 사용해야 한다. 철수의 컴퓨터는 캐시메모리 사용 규칙이 LRU 알고리즘을 따 른다. LRU 알고리즘은 Least Recently Used 의 약자로 직역하자면 가장 최근에 사용되지 않 은 것 정도의 의미를 가지고 있습니다. 캐시에서 작업을 제거할 때 가장 오랫동안 사용하지 않은 것을 제거하겠다는 알고리즘입니다. 만약 캐시의 사이즈가 5이고 작업이 2 3 1 6 7 순으로 저장되어 있다면, (맨 앞이 가장 최근에 쓰인 작업이고, 맨 뒤는 가장 오랫동안 쓰이지 않은 작업이다.) 1) Cache Miss :..