tony9402

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 +..

이번 글에서는 Github에서 Github Desktop을 다운 받는 방법과 Clone하는 방법에 대해 알아보자. 1. 자신의 Profile을 누르면 아래와 같이 이 창이 뜰 것이다. 여기서 초록색 버튼인 New를 누르자. 2. 프로젝트 이름에 영어로 넣자. 또한 이 Repository를 Public으로 할껀지 Private으로 할껀지 체크하면 된다. 그 밑에 Readme에 대한 체크를 하라는게 있는데 이는 Repository에 대한 설명을 쓰면 되는 공간이다. 하지만 Readme는 md(markdown)으로 작성한다. markdown은 그렇게 어렵지 않기 때문에 구글링하면 간단히 이해할 수 있다. 3. 위에 작업을 다 하고 초록색 버튼을 누르면 아래와 같은 장면이 뜬다. 여기서 Set up in Des..

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

3일차에서 최소 힙을 짰었는데 너무 드럽게 짜서 다시 간단하게 짜봤다.또한 최소 힙을 짜면서 최대 힙도 다시 짜봤다. 1. 최대 힙 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include#include using namespace std; int heap[200000];int Size = 1; void push(int data){ heap[++Size] = data; int idx = Size; while (idx > 1) { if (heap[idx] > heap[idx / 2]) { swap(heap..

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