tony9402

앞에 글에선 큐가 작동하는 과정과 간단한 소스코드를 작성하였다. 그 소스코드를 이용하여 어떤 알고리즘을 만들때 각 큐에 대한 함수를 엄청 많이 만들어야 한다. 이번 글에선 이를 한번 개선시켜보자. 먼저 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 ●●●○○ (퀵 정렬은 최..

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

SCCC 스터디 1일차 STL에 대해 설명을 듣고 간단한 문제를 풀며 공부했다. 내용 간단히 정리 1. memset string.h, memory.h 안에 있으며 초기화 할 값은 바이트 단위이다. (여기서 배운 내용은 아니지만 내가 알고 있는 꿀팁은 int형인 배열에 0x3F의 값을 초기화 한다면 배열에는 0x3F3F3F3F의 값이 들어간다.) int arr[1000];memset(arr, 0x3F, sizeof(arr)); arr[0] == arr[1] == arr[2] == ... == arr[999] == 0x3F3F3F3F 이는 다익스트라 등의 알고리즘에서 많이 사용한다. 2. math.h - 이 헤더파일 안에는 Hypot => sqrt(x^2 + y^2)의 값, 즉 두 점과의 거리를 구하는데 사..

보호되어 있는 글입니다.

문제 : 1,2,3 더하기 6유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기 4, 5보단 조금 더 쉽고 재밌었던 문제였다.더하기 식이 대칭이 되도록 만들면 되는 문제이다. 이를 어떻게 풀지 고민하다가 다이나믹 프로그래밍이므로 재귀적으로, 또한 합이 대칭을 만족해야 한다는 요점을 잡고 다시 보니 바로 눈에 보였다. 어떤 수 x가 있는데 이를 어떻게 대칭적이고 재귀적으로 풀 수 있을까?바로 x에서 2, 4, 6을 빼고 반을 나눠 양쪽에 이어서 붙이면 된다.ex) x => 1 + (x-2) + 1, 2 + (x-4) + 2, 3 + (x-6) + 3 이렇게 빼면 된다. 근데 여기서 궁금증을 가지는 사람이 있을 수 있다.ex) 4를 1 + 1 + 1 + 1로 만들 수 있는데 이는 어떻게 만들어지지.....

문제 : 1,2,3 더하기 5문제 유형 : 다이나믹 프로그래밍 일단 정수 4인 경우, 1,2,3의 합으로 나타내는 방법이 왜 3개인지 알아보자. 처음엔 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수를 구해보면 아래와 같다. 3 + 11 + 32 + 22 + 1 + 11 + 2 + 11 + 1 + 21 + 1 + 1 + 1 여기서 문제 조건에 만족하지 않은 것은 2 + 2와 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 1 + 2이다.이를 어떻게 풀까.......? 정수 n이 있다고 가정해보자. n은 아래와 같이 쓸 수 있을 것이다. 1. 3 + (n - 3)2. 2 + (n - 2)3. 1 + (n - 1) 1번에서 n - 3이 3이 아닌 1과 2로 식을 전개하면 된다.3 + 1 + (n -..