hyunjin

백준 9012 바로가기 더 쉽고 메모리, 시간 적게 사용되는 코드로 바꾸고 있다. 소스 코드 1 - 배열 활용 #include using namespace std; int main(){ ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N; string s; cin >>N; while(N--){ cin>>s; int arr[2]={0,}; for(char c : s){ arr[int(c-'(')]++; if(arr[0]

백준 합분해(2225) 풀이 K ＼ N 0 1 2 3 4 0 0 0 0 0 0 1 1 1 1 1 1 2 1 2 3 4 3 1 3 6 4 1 4 10 5 1 5 15 점화식 D[K][N] = D[K][N-1] + D[N-1][N] 소스 코드 #include #define Moduler 1000000000 using namespace std; int main (){ int K,N; long long dp[201][201]={0,}; // k n scanf("%d %d",&N,&K); for(int i = 0; i

[BOJ 2751] #include using namespace std; int main(){ int n,*arr; scanf("%d",&n); arr = new int [n]; for(int i=0;i>a>>b; v.push_back(make_pair(a,b)); } stable_sort(v.begin(),v.end(),compare); //sort와 다르게 구조체처럼 여러 값들이 묶여 있을 때 하나의 요소로 정렬 했을 때 // 다른 요소들의 정렬 순서도 정렬 전과 같이 그대로 유지될 수 있게 해줌 for(auto e : v) cout

데이터 정렬 이유 : 탐색을 위해서 (정렬이 탐색보다 시간이 덜 걸린다 했나?..) 1. 삽입 정렬(Insertion Sort) 두 번째 원소부터 맨 마지막 원소까지 각 원소가 왼쪽에 있는 모든 원소 보다 크거나 같을 때 까지 왼쪽으로 이동 현재 위치보다 아래쪽 순회하며 알맞은 위치에 넣는 정렬 //insertion sort #include using namespace std; template void insertSort( Vector* v, const int l, const int r){ for(int i = l+1 ; i left && v[j] < v[j-1] ; j--){ swap(v[j-1],v[j]); } } } 이미 정렬되어 있는 자료 구조에선..

백준 2xn 타일링(11726) 백준 2xn 타일링2(11727) 1. 풀이 11726 N 번째 타일 배치는 1. N-1 번째에 2x1 타일을 붙이는 방법 (세로 타일 | 붙이기) 2. N-2 번째에 1x2 타일 2개를 붙이는 방법 (가로 타일 = 붙이기) 을 통해 만들 수 있다. 11726 점화식 D[n] = D[n-1] + D[n-2] 11727의 점화식도 11726과 크게 다르지 않다, 1. N-1 번째에 2x1 타일을 붙이는 방법 (세로 타일 | 붙이기) 2. N-2 번째에 1x2 타일 2개를 붙이는 방법 (가로 타일 = 붙이기) 3. N-2 번째에 2x2 타일 1개를 붙이는 방법 11727 점화식 D[n] = D[n-1] + D[n-2]*2 2. 코드 11726번 //https://www.acm..

1. Dynamic Programming(동적 계획법) 이란? 큰 문제를 작은 문제로 나누어 푸는 문제 1.1 Divide&Conquer(분할정복) 과 다른 점은? 거의 비슷하지만 결정적 차이가 있다. 작은 문제가 중복이 일어나나는 아닌지 분할 정복 큰 문제를 해결하기 어려워 단순히 작은 문제로 나누어 푸는 방법 작은 문제에서 반복이 일어나는 부분이 없다 DP 작은 부분 문제들이 반복되는 것(답이 바뀌지 않는다.)을 이용해 풀어나는 것 1.2 Dynamic Programming 방법 모든 작은 문제들은 한 번만 풀어야함. 정답을 구한 작은 문제들을 어딘가에 메모해놓고 다시 그보다 큰 문제 풀어나갈 때 똑같은 작은 문제가 나타나면 앞에서 메모한 작은 문제의 결과값 이용 1.3 Dynamic Programm..

백준 1463번 1로 만들기 1. 문제 설명 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 합니다. 연산을 사용하는 횟수의 최소값을 출력 2. 풀이 횟수를 최소로 하는 경우의 수 1. 3으로 나누어 떨어진다. 2. 짝수지만 1을 빼면 3으로 나누어 떨어진다(x가 2보다 클 때 3번보다 우선 순위 높음 - 경우 따지는 2보다 클때라는 것 상관 없음) 2-2 짝수지만 2를 빼면 3으로 나누어 떨어진다(x가 8보다 클 때 3번보다 우선순위 높음...) 3. 2로 나누어 떨어진다. 4. 1을 뺀다(홀..

백준 회의실 배정 바로가기 어렵지 않았다. [풀이 전략] 회의 시작, 끝 시간을 pair로 묶어 vector에 넣자 1. 시작 시간 순서 기준 정렬 이렇게 하면 가장 많은 개수를 찾기가 조금 어렵다. 2. 끝 시간 순서 기준 정렬 끝 시간 기준 정렬 후 범위 내에 있는 것 선택하면 되니까 이건 가능하겠다. [소스 코드] #include using namespace std; bool compare(pair a,pair b){ if(a.second == b.second) return a.first >N; for(int i=0;i>start>>e..