Daily Log

DP - 다이나믹 프로그래밍 구하기 1) n이 1,2,3.. 일때의 규칙성을 찾는다. n=1 답:1 n=2 답:2 n=3 답:3 2) 점화식 구하기 // BJ - 11726 2*n 타일링 // 다이나믹 프로그래밍 #include using namespace std; int arr[1001]; int dp(int x) { if (x == 1) return 1; if (x == 2) return 2; if (arr[x] != 0) return arr[x]; return arr[x] = (dp(x - 1) + dp(x - 2)) % 10007; //%10007은 오버플로우 방지 } int main() { int N; cin >> N; cout > n; cout

https://www.acmicpc.net/problem/10219 10219번: Meats On The Grill 각 테스트 케이스마다 각 고기덩이를 뒤집은 후의 불판의 상태를 H줄에 걸쳐서 출력한다. 각 줄에는 W개의 문자가 있어야 하며, 입력에서 주어진 각 고기 덩이가 뒤집힌 채로 있어야 한다. 이를 만족하는 어느 답을 출력해도 정답으로 인정한다. www.acmicpc.net 문제 abbb aabb aa.. 이런식으로 고기 모양이 주어지는데, 같은 영어 소문자는 고기 한덩이다. 이 고기들을 90도/180도/270도/반전 하여 겹치지 않게 주어진 그리드 안에서(h*w) 고기를 뒤집는 것 => 고기 한덩이가 붙어 있도록 회전 or 반전 시키면 됨 reverse() #include int a[5] = {..

삽입정렬 - 적절한 위치에 삽입 하는 것 - 처음부터 왼쪽에 있는 원소와 비교해서 해당 원소가 비교값보다 작다면 왼쪽으로 이동하는 식으로 더 큰 수를 만날때까지 반복해준다. - 항상 왼쪽에 있는 것은 정렬되어 있다고 가정되어 있음. 즉, 멈출 코드를 알고 있다는 것. (왼쪽의 원소값보다 해당값이 크면 멈추면 된다.) - 시간 복잡도(Big O) : 10 + 9 + 8 + 7 ... + 1 => O(N^2) - Big O는 선택/버블과 같지만 실제로는 선택/버블/삽입 중에서는 삽입이 제일 연산이 적다. - 거의 정렬된 상태의 정렬을 삽입 정렬로 한다. => 삽입 정렬이 굉장히 빨라짐 // 삽입정렬 insertion sort #include using namespace std; int main(void) {..

- 입력받을 배열을 공간을 선언한다. - 입력받은 배열을 for문을 통해서 %42 해준다. - %42한 값은 set container에 넣어준다. 이때, set container는 중복 값을 받지 않기 때문에 나머지 중 같은 수는(이미 담긴 수) 제외되고 담긴다 - set container의 size를 구하면 담긴 원소 개수를 알 수 있다. => 10개의 값을 각 %42를 한 후, 나머지 값들 중 중복을 제외한 서로 다른 값의 나머지 개수만 구하기 // BJ 3052 #include #include using namespace std; int main(void) { int array[10]; int count = 0; for (int i = 0; i > array[i]; ..

버블 정렬 - 당장 옆에 값과 비교 - 1회차가 끝나면 가장 큰수가 가장 뒤에 정렬돼있다. 5 3 4 1 2 6 1회차 3 5 4 1 2 6 3 4 5 1 2 6 3 4 1 5 2 6 3 4 1 2 5 6 3 4 1 2 5 6 2회차 - 맨 뒤에 정렬된 6 제외한 나머지 앞 5개의 수만 비교 => 6 + 5 + 4 + 3 + 2 + 1 (등차수열) => n*(n-1) / 2 (컴퓨터에서는 가장 큰 차수만 보기 때문에 -1 과 /2 제거) => n*n => 시간 복잡도 ? 데이터가 N개 일때 총 몇 번의 비교 연산을 하는가 시간복잡도 빅오 : O(N^2) 데이터가 10000개면 약 1억번 계산해야하는 비효율적인 알고리즘 *시간복잡도는 선택정렬과 같지만, 실제 수행 시간은 버블정렬이 더 느리다. 매번 바로 ..

- 선택정렬 : 전체 배열 중 가장 작은 것을 선택해서 맨 앞으로 보내는 것 (맨 앞에 숫자는 제일 작은 것에 있던 숫자의 자리로 값을 스와핑한다.) 5 2 6 1 3 4 1 2 6 5 3 4 1 2 6 5 3 4 1 2 3 5 6 4 1 2 3 4 6 5 1 2 3 4 5 6 - 1회차 : 6번 비교 - 2회차 : 5번 비교 - 3회차 : 4번 비교 ... => 6 + 5 + 4 + 3 + 2 + 1 (등차수열) => n*(n-1) / 2 (컴퓨터에서는 가장 큰 차수만 보기 때문에 -1 과 /2 제거) => n*n => 시간 복잡도 ? 데이터가 N개 일때 총 몇 번의 비교 연산을 하는가 시간복잡도 빅오 : O(N^2) 데이터가 10000개면 약 1억번 계산해야하는 비효율적인 알고리즘 //선택정렬 Sel..

어제부로 정보처리기사 실기 시험도 끝나서 알고리즘 공부를 다시 시작했다. 다행히 실기는 가채점 결과 통과했다.. ㅎㄷㄷ 2년 전 합격률 11% 일 때 실기를 봤는데 너무 어려워서 탈락했다. 매번 50~60%대의 합격률이 나오던 시험이 갑자기 내가 응시하는 시점에 주관식으로 바뀌고 출제 기관에서 난이도 조절에 실패해서 합격률이 11%대로 떨어지다니 운도 지지리도 없다고 생각했다. 하지만 사실 제대로 공부안한 나의 탓이 크다. 10명 중 1명꼴로 합격한 사람이 있으니.. 어쨌든 이번에 통과해서 정... 말 다행이다. ^^ 이번에 통과를 못했으면 다시 필기부터 봐야 했으니깐... 그리고 이번에 재시를 하면서 전공기초 공부를 다시 할 수 있어서 좋은 기회였다고 생각한다. 공부할때는 깊이는 없지만 방대한 양(신기..

- 하나의 문제는 단 한번만 풀도록 하는 알고리즘 - 이미 해결한 문제를 반복 계산하는 것을 막아 효율적으로 만드는 것 - 한번 계산한 결과를 "메모이제이션"을 활용해서 배열에 저장 #include using namespace std; int d[100]; int fibonacci(int x) { if (x == 1) return 1; if (x == 2) return 1; if (d[x] != 0) return d[x]; return d[x] = fibonacci(x - 1) + fibonacci(x - 2); } int main(void) { cout

- C++의 벡터는 동적 배열구조 클래스 - 자동으로 배열의 크기 조절과 추가 삭제 가능 - 모든 자료형에 대해 배열처럼 저장 가능 But 한번에 한 타입만 저장 가능 - 자바 벡터처럼 배열 크기 추가할 때, 기존 배열 크기의 100% 늘어남 vector integer_vector; vector double_vector; vector char_vector; - 벡터의 기본 함수 //iterator 반복자 begin() //beginning iterator 반환 end() //end iterato 반환 //추가 및 삭제 push_back(element) //벡터 제일 끝에 원소 추가 pop_back() //벡터 제일 끝 원소 삭제 //조회 [i] //i번째 원소 반환 at(i) //i번째 원소 반환 fro..