tony9402

SCCC 스터디 7일차 1月 21日 DP 어려워;;;;;;;; 1. DP1 DP는 다이나믹 프로그래밍의 약자로 한국말로 하면 동적계획법이라 한다. (DP가 부르기 좋은 듯) 처음에 디피가 뭔지도 모르겠고 그냥 "어렵다"라는 말만 들어서 접근하기가 매우 힘들었다. 근데 맨 처음 풀 때 삽질과 다른 사람이 푼 방식을 보고 대충 어떤 느낌인지 깨닫기 시작했다. - 중복계산을 피해 한번 계산 했던 것은 저장해서 처리속도를 높인다. - 큰 문제를 해결하기 위해 작은 문제를 이용(이전 작업을 이용)하여 큰 문제를 해결 - 점화식을 이용해 문제 해결 첫 번째에 쓴 건 많이 들어봤을 것이다. (메모이제이션, memoization)두 번째는 분할정복과 비슷하다는 것을 느낄 수 있다.세 번째에는 점화식을 세워 풀면 된다는..

문제 : 1로 만들기문제 유형 : 다이나믹 프로그래밍 이 문제의 핵심은 입력 받은 수를 최소 횟수로 1로 만드는 것이다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다.2. X가 2로 나누어 떨어지면, 2로 나눈다.3. X에서 1을 뺸다. 위 세가지를 이용해서 1로 만들어야 하는데 이를 어떻게 할까? 다이나믹 프로그래밍 문제를 풀 땐 너무 복잡하게 생각하면 오히려 안풀린다. 다이나믹 프로그래밍 문제를 풀기 위한 방법은 탑다운 방식과 바텀업 방식이 있다. 나도 공부하는 입장이니 두 가지 방법으로 설명하겠다. 1. 탑다운(Top-down) 방식 현재 수를 X라 하자. X가 3으로 나눠떨어진다면 X/3을 만드는 횟수는 X 만든 횟수에 한번더 연산을 한 것이기 때문에 X를 만든 횟수에 +1을 해주면 된다.이..

문제 : 파도반 수열 문제 유형 : 다이나믹 프로그래밍 이 문제는 규칙을 찾기만 하면 되는 문제이다. 난 두가지 점화식으로 풀었다. 1. 점화식1 일단 가장 먼저 풀었던 방식을 설명하자면, 소용돌이처럼 이어지는 수를 한 줄로 써보았다. 1 1 1 2 2 3 4 5 7 9 12 ... 이것을 보고 규칙이 바로 보였다. 지금 현재 위치에서 왼쪽으로 2칸 떨어진 것과 같은 방향으로 3칸 떨어진 것의 합이 현재 위치의 값과 같다는 점화식을 발견했다. 이를 식으로 쓰자면 아래와 같다. 이 식을 가지고 초기값만 잘 넣어주면 쉽게 맞추는 문제이다. 또한 n이 커지면 int형의 범위가 벗어나니 맞왜틀 했던 사람들은 int를 long long으로 바꿔보기 바란다. - 소스코드 123456789101112131415161..

SCCC 스터디 5일차 1月 16日 (수학 어렵다.........................) 1. 수학1 에라토스테네스의 체 - N 이하의 소수를 빠르게 찾는 알고리즘이다. 소수의 배수를 없애는 방식으로 진행한다. 자세한 내용은 여기에서 참고하면 될 것이다. 이 방법을 이용하면 시간복잡도는 O(n log log n)이다. 유클리드 호제법 - 최대공약수(GCD)를 빠르게 구하는 알고리즘이다.나머지 연산을 이용해서 빨리 구할 수 있는데 이에 대한 자세한 내용은 여기에서 참고하면 될 것이다. 에라토스테네스의 체 - 소수인지 판별하는 방식은 거의 동일하지만 소스코드를 작성할때 살짝 다른게 있다. 다른 곳에서 계산과정 중 오버플로우를 방지하기 위해서 사용한다고 들었다. - 에라토스테네스 1. 에라토스테네스의 ..

SCCC 스터디 5일차 1月 15日 오늘은 미세먼지로 인해 전날 스터디 모임이 취소가 됬다. 그래도 배울 내용은 적어 홈스터디로 진행됬다. 1. 분할정복 분할정복은 Divide and Conquer로 문제를 같은 유형의 여러 작은 문제들로 나눈 뒤, 그 작은 문제들의 답을 이용해서 문제를 해결하는 방식을 말한다. 분할정복을 이용하면 시간 복잡도를 줄일 수 있다. 예를 들어, 1부터 100까지 더하는 것을 공식을 이용하지 않고 더한다면 아주 간단하게 O(n)로 더할수는 있다. 하지만 분할정복을 이용하면 O(log n)으로 더 줄일 수 있다. 1 + 2 + 3 + ... + 51 + 52 + 53 + ... + 99 + 100 이를 한번 Divide(분할)을 해보자. 1 + 2 + 3 + ... + 50 +..

SCCC 스터디 4일차 1月 14日 오늘은 기초 자료구조에 대해 공부했다. 1. list STL에 있는 list을 이용하여 구현해봤다. list를 이용한 문제가 잘 안나온다고 하는데 그렇게 어려운것도 아니고 간단한 자료구조이기도 하고 혹시 나오면 당황해서 못짜는 것보단 아는 것이 좋아 list를 이용해 백준에 있는 문제를 풀었다. 2. Graph Graph를 인접행렬로 표현 할 수 있고, 인접리스트로 표현 가능하다. 각자의 장단점이 존재한다. 어느정도 작을땐 인접행렬을 이용해 문제를 풀어도 되고 좀 클땐 인접리스트가 효율적이다. 3. Tree 트리에 가장 큰 특징은 사이클이 없는 연결 그래프라는 점이다. 즉, Tree는 Graph의 일종이다. 또한 트리는 정점이 n개가 있으면 간선은 n - 1개가 있다...

C++ 환경에서 코딩을 하면 STL이라는 것을 사용할 수 있다. STL에는 queue가 기본적으로 만들어져있다. 또한 이 queue을 상황에 따라 편하게 선언을 할 수 있다.STL을 이용하여 n을 입력받고 1부터 n까지의 값을 queue에 넣고 queue에 있던 모든 값을 출력해보는 간단한 소스코드를 작성해보자. 12345678910111213141516171819202122232425#include#include using namespace std; queue q; int main(){ int n; cin >> n; //scanf("%d",&n); for (int i = 1; i

이번엔 선택 정렬, 병합정렬(merge sort), 퀵 소트(quick sort), 카운팅 소트(counting sort)를 직접 구현해보았다. 1. 선택 정렬 -구현 난이도 : ●○○○○ 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include#include#include using namespace std; vector list; int main(){ ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; for (int i = 0; i > input; list.push_back(input); } for (int i = 0; i

SCCC 스터디 3일차 정렬 - 힙 정렬 - 선택 정렬 - 삽입 정렬 - 버블 정렬 - 합병 정렬 - 쉘 정렬 - 퀵 정렬 - 카운팅 정렬 1. 힙 정렬 STL priority_queue를 이용하지 않고 힙 정렬 구현해보기 - 최대 힙 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) - 최소 힙 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) - 수 정렬하기2 ●●◐○○ (만약 STL을 이용하면 난이도 ●○○○○) 2. 삽입 정렬 - 수 정렬하기 ◐○○○○ - 수 정렬하기2 ●●●●● (수 정렬하기2에서는 삽입 정렬를 이용해서 절.대.로 맞았습니다!가 뜨지 못한다.) 3. 합병 정렬(merge sort) - 수 정렬하기2 ●●●○○ 4. 퀵 정렬 - 수 정렬하기2 ●●●○○ (퀵 정렬은 최..

SCCC 스터디 2일차 시간복잡도에 대해 간단히 이해하고 어떤 표기법을 쓰는지 알고 나머지 시간은 구현 time~ 1억번의 연산을 수행할 때 걸리는 시간을 약 1초가 걸린다고 생각하면 된다. 단순 연결 리스트 - 조회, 삽입, 삭제 - O(N) 정렬 - 선택, 버블, 삽입 - O() - 퀵정렬 - O() -> 평균은 O(NlogN) - 힙, 머지. etc - O(NlogN) 스택, 큐 - 삽입, 삭제 O(1) 이분 탐색 - 탐색 - O(NlogN) 힙 - 삽입, 삭제 O(logN) 1. 터널의 입구와 출구 - ●○○○○2. 도깨비말 - ●◐○○○3. 크로스워드 만들기 - ●○○○○4. 그림 비교 - ●◐○○○5. 지뢰 찾기 - ●○○○○6. 비밀번호 발음하기 - ●●○○○7. 고장난 시계 - ●○○○○8..