tony9402

SCCC 스터디 9일차 1月 23日 오늘은 디피랑 그리디 문제들을 처음부터 끝까지 풀었다.디피랑 그리디는 역시 문제를 좀 풀어보면서 익히는게 답이긴 하지만.... 어렵다.. 1. 저울 - ●●◐○○ (아이디어 생각하는게 좀 어려웠다.)2. 포도주 시식 - ●●◐○○ 3. 한 줄로 서기 - ●●○○○ 4. 동전 2 - ●●○○○ 5. 타일 채우기 - ●●●◐○ 6. 잃어버린 괄호 - ●●●○○ 7. 이항 계수 2 - ●◐○○○ 8. 기타줄 - ●●●○○ 9. 크게 만들기 - ●●●◐○ 10. RGB거리 - ●◐○○○ 11. 제곱수의 합 - ●◐○○○ 12. Revenge of the Pancakes (Large) - ●●●○○13. 행렬 - ●●●◐○ 14. 문자열 - ●◐○○○15. 암호코드 - ●●●○..

SCCC 스터디 8일차 1月 22日 그리디도 어렵다..그리디는 Greedy로 탐욕 알고리즘이라 불린다. 현재 선택이 나중 선택에 영향을 미치지 않게 고르는 것이다.디피랑 그리디에 대한 자세한 개념은 라이님 블로그, 나동빈님의 블로그에 잘 설명 되어있으니 거기서 개념을 보는게 좋다. (난 여기에 쓰는건 그냥 간단히 일기장처럼 쓰는 것이여서 개념보단 문제 리스트를 올리는 것이다.) 그리디 알고리즘의 종류가 있다. (여기서 내가 아는건 거.....의 없다....) 1. Fractional Knapsack Problem (=> 거스름돈 문제)2. 시간표 배정3. 수학적 성질이 최적해를 보장하는 경우4. Huffman Code5. 다익스트라6. MST(Kruskal, Prim)7. 최대 유량 1. 동전 0 - ●..

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

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

오늘 풀 문제는 바로 단지번호붙이기이다. 이 문제에 대해 이미 올렸었는데 이 글은 여기와 또 다른 소스코드가 있다. 거기에서도 C로 queue를 구현했지만 너무 못짰다............ 거기는 C로 구현한거 빼고 보는걸 추천한다. 설명은 거기서 했었으니 바로 소스코드만 올리겠다. (간단한 설명을 보고 싶은 사람은 여기에 가서 읽고 오면 된다.) 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031..

앞에 글에선 큐가 작동하는 과정과 간단한 소스코드를 작성하였다. 그 소스코드를 이용하여 어떤 알고리즘을 만들때 각 큐에 대한 함수를 엄청 많이 만들어야 한다. 이번 글에선 이를 한번 개선시켜보자. 먼저 Queue *head와 Queue *tail을 하나의 구조체로 묶고 size라는 변수까지 추가하면 깔끔해지겠다. 1. 새로운 구조체 만들기 12345678typedef struct{ Queue *head; Queue *tail; int size = 0;}qq; typedef qq* Q;cs 2. init() 함수 큐를 인자로 받고 그 큐를 초기화하는 함수로 바꾸면 된다. 12345678void init(Q q){ q->head = (Queue*)malloc(sizeof(Queue)); q->head->ne..

자료구조 Queue를 를 이용하여 구조체 + 포인터를 이용해서 간단히 구현해보자. Queue에 대한 함수를 간단하게 4개(push, front, pop, empty)만 만들어 사용하겠다. 간단하게 구현하는 과정을 아주 자세하게 그림을 밑에 올려놓았다. (애니메이션으로 일일이 다 만들었는데 혹시 쉬운 방법을 아는 사람은 댓글을 남겨주시면 감사하겠습니다.) 1. Queue에 push하는 과정 2. Queue에서 pop하는 과정 이를 C로 구현한 소스는 아래와 같다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include#include str..

이번엔 선택 정렬, 병합정렬(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