알고리즘 다이나믹 프로그래밍 풀이 타일은 | 또는 ㅡ 같은 모양을 가진다. 직사각형 2*n에서 n이 하나 증가하면 열이 한칸 더 생기는 것으로 | 만큼이 더 생기게 된다. 그러므로 2*n-1을 채우는 방법에 | 을 붙여주면 된다. 이 외의 경우의 수가 하나 더있는데 = 가로 두개가 마지막에 붙는 경우이다. 이 경우에는 2*n-2을 채우는 방법에 = 을 붙여주면 된다. 즉 직사각형 2*n을 채우는 방법의 수는 2*n-1을 채우는 방법의 수 + 2*n-2을 채우는 방법의 수가 된다. 벡터 dy를 이용하여 나타낼 수 있다. dy[1]은 | 로 채울 수 있는 방법이 하나이므로 1으로 초기화 dy[2]는 || 또는 = 로 채울 수 있는 방법이 두가지이므로 2로 초기화 한다. dy[1]=1 dy[2]=2 dy[n]..
알고리즘 이분 탐색 누적 합 풀이 석순은 아래에서부터 종유석은 위에서부터 자란다. 이를 각각 bottom 벡터과 top 벡터로 나타낸다. 번갈아가면서 석순과 종유석의 길이가 입력되므로 차례대로 입력받은 값을 bottom 벡터 또는 top 벡터에 인덱스로 하여 1씩 더해준다. 실제로 석순의 길이가 3이라면 bottom[1], bottom[2], bottom[3]에 모두 1씩 더해주어야 하는데 이것을 이중 for문으로 다음과 같이 구현하면 시간 초과가 발생하므로 다른 방법을 사용하여야 한다. 시간 초과 코드 #include #include #include using namespace std; int main() { // freopen("input.txt", "rt", stdin); ios_base::sync..
알고리즘 그리디 알고리즘 정렬 풀이 시작하는 시간이 빨라도 늦게 긑나면 최대 회의의 수를 맞출 수 없으므로 각각의 스케줄에서 회의의 종료시간이 중요하게 작용한다. 각 회의 시작시간과 종료시간을 입력받으면 이를 종료시간을 기준으로 오름차순으로 정렬한다. 이때 종료시간이 같으면 시작시간을 기준으로 오름차순으로 정렬한다. 첫번째 end 변수는 종료시간이 가장 빠른 스케줄의 종료시점으로 초기화한다. 두번째 스케줄의 시작 지점이 첫번째 스케줄의 종료시점보다 크거나 같은지 확인한다. 크거나 같아면 cnt++ 한다. 모든 스케줄을 확인할 떄 까지 2번을 반복한다. 성공 코드 #include #include #include using namespace std; int n; struct Con{ int s, e; Con..
알고리즘 자료 구조 정렬 이분 탐색 해시를 사용한 집합과 맵 풀이 1. 가지고 있는 숫자 카드를 card 배열에 오름차순으로 정렬한다. 2. card 배열의 원소들을 돌며 숫자가 동일한 카드 번호를 하나로 만들고 card 배열의 원소들의 개수를 cardCnt배열에 저장한다. 우선, cardCnt 배열을 완성시키고 cardCnt 배열의 원소 인덱스를 나타내는 point 변수를 0으로 초기화한다. cardCnt에 1을 넣고 연속되는 동일한 card 번호가 나오는 동안 해당 cardCnt[point]++ 한다. 반복문을 빠져나오면 해당 card 번호의 개수를 다 세아린 것이므로 point++한다. erase와 unique 함수를 통해 동일한 숫자는 한개만 남긴다. 3. lt=0, rt=n-1로 카드의 존재 여..
알고리즘 자료 구조 정렬 이분 탐색 풀이 1. 가지고 있는 숫자 카드를 card 배열에 오름차순으로 정렬한다. 2. 가지고 있는지 구분하기 위해서 lt=0, rt=n-1로 카드의 존재 여부를 표시하는 변수 exist=0으로 초기화한다. 3. mid=(lt+rt)/2하여 card[mid] 값이 확인하고자 하는 숫자와 일치하면 exist 변수를 1로 하고 반복문을 탈출한다. card[mid] 값이 확인하고자 하는 숫자보다 작으면 lt=mid+1로 하여 탐색한다. card[mid] 값이 확인하고자 하는 숫자보다 크면 rt=mid-1로 하여 탐색한다. 이 과정은 lt num; card.push_back(num); } sort(card.begin(), card.end()); cin >> m; for(int i=0..
[백준 1654번/c++] 랜선 자르기
문제 구하고자 하는 것 K개의 랜선을 잘라 길이가 모두 같은 N개의 랜선을 만들 때, 만들 수 있는 최대 랜선의 길이 조건 랜선을 자르거나 만들 때 손실되는 길이는 없다. 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다. 항상 센티미터 단위로 정수길이만큼 자른다. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 변수 범위 K는 1이상 10,000 이하의 정수 N은 1이상 1,000,000 이하의 정수 랜선의 길이는 2^31-1보다 작거나 같은 자연수 접근 길이 별로 몇 개의 랜선이 나오는지 확인하여야 한다. 모든 1부터 가장 긴 랜선의 길이까지 모두 탐색하면? 시간초과가 난다. O(가장 긴 랜선길이) 가장 긴 랜선의 길이는 최대 2^31-1(약 20억) 그리고 랜선의 개수만큼 순..