전체 글 (6) 썸네일형 리스트형 백준 알고리즘 #5 - 유클리드 호제법 이번 포스트에서는 유클리드 호제법(Euclidean algorithm)에 대해 알아보겠습니다. 여러분들은 지금까지 살아오면서 최대공약수에 관해 한 번 이상은 들어봤을 것입니다. 최대 공약수는 두 수의 공약수 중 최대인 수를 이야기 합니다. 아마, PS 혹은 다른 쪽을 희망한다고 하더라도, 알아 두면 좋은 알고리즘 이라고 생각을 합니다. 또한, 이산수학에서도 배우게 될 내용이니 미리 학습하시는걸 추천드립니다! 🏳️ 왜 유클리드 호제법을 써야하는가? 유클리드 호제법의 개념을 이용하지 않고, 7과 28의 최대 공약수를 코드를 통해 도출해보죠. #define _CRT_SECURE_NO_WARNINGS #include int Max(int num1, int num2) { return (num1 > num2) ? .. 백준 알고리즘 #4.2 - 원형 연결리스트, 이중 연결리스트 저번 포스트에서는 단순 연결리스트를 알아봤습니다. 이번에는 원형 연결리스트의 구현과 이중 연결리스트의 구현에 대해 포스팅하겠습니다. 🏳️ 원형 연결리스트의 구현 - 원형 연결리스트는 단순 연결리스트와 다르게, 마지막 요소 -> link가 NULL이 아닌 head를 가리키게 하는 형식입니다. 이때 head포인터는 마지막 노드를 가리키게 됩니다. head 포인터를 만들어줍니다. (연결리스트를 순회하기 위해서 필요한 포인터, 여기서는 마지막 원소를 head로 가지게 해야합니다.) 이때 head 포인터는 아무것도 가리키지 않는 상태로 생성합니다. (NULL을 가리키게 함.) Case #1 ) 원소를 동적 할당하고 , 만약 첫 원소라면 head포인터를 연결 시켜준후, head->link = head형식으로 만들어.. 백준 알고리즘 #4.1 - 단순 연결 리스트 이번 포스트에서는 단순 연결 리스트( Linked List )에 대해 알아보겠습니다. 연결리스트는 배열(노드)을 하나씩 동적할당 한 후, 다른 배열(노드)와 연결해주는 방식의 자료구조입니다. 트리, 힙, 그래프 등등도 연결 리스트를 충분히 숙지해야 학습하는데 무리가 없기때문에 꼭 알아둬야 한다고 생각합니다. 🏳️ 연결 리스트와 배열 - 연결 리스트와 배열은 형태가 비슷하지만 각자 장단점을 지닙니다. 연결 리스트의 장점) 수정과 삭제가 자유롭다. 카드게임을 한다고 가정해 봅시다.처음 제 손에는 A, B, C 카드가 있습니다. 이것을 각각 그림으로 표현하면 다음과 같습니다. 여기서 D카드를 추가 하려면 어떻게 해야할까요? 이때 배열 크기는 3으로 고정해놨다고 가정해봅시다. 연결 리스트에선 새로운 노드(배열).. 백준 알고리즘 #3 - 누적합 이번 포스트에서는 누적합(Prefix sum)에 대해 알아보겠습니다. 누적합은 말 그대로 '누적'된 합입니다. 또한, 누적된 합만을 구하는것 뿐만 아니라 그 결과물로 구간 사이의 합을 구할 수 있는 강력한 알고리즘입니다. 🏳️ 누적합을 구하는 방법 - ary라는 배열안에 요소 {1, 2, 3, 4, 5}가 있다고 가정해 봅시다. STEP 1) 배열을 정의합니다. STEP 2) 새로운 배열을 만들어서, ary 배열의 인덱스까지의 값들을 모두 더해줍니다. 우리는 이미 중학교, 고등학교때 시그마라는 개념을 배웠습니다. 그렇다면 ary[2]부터 ary[4]까지 합은 어떻게 구할 수 있을까요? 4항까지의 원소를 모두 더한것에서, 1항까지 원소를 모두 더한값을 빼주면 됩니다. 이를 코드로 나타내면 다음과 같습니다... 백준 알고리즘 #2 - 이진 탐색 이번 포스트에서는 이진탐색(Binary search)에 대해 알아보겠습니다. 이진탐색은 빠른 탐색 알고리즘에 속합니다. for문을 돌려 순회하는 방식은 배열 전체를 돌아야 하기 때문에 시간복잡도 O(N)을 가지지만, 탐색 구간을 계속 반으로 줄여나가는 이진탐색은 시간복잡도 O(logN)을 가집니다. 🏳️ 이진 탐색을 위해 준비해야 할 것은? - 먼저 이진탐색을 하기 위해서는 정렬이 먼저 되어있어야 합니다. (알고리즘 #1 - qsort를 참고해 주세요) 🏳️ 이진 탐색의 원리 - 이진 탐색은 배열 안에서 원하는 값을 찾기 위해 탐색 구간을 계속 반으로 줄여 나갑니다. ex) 배열의 원소가 {4, 2, 5, 1, 13, 8, 7}이고 찾으려는 원소가 '2' 일 때 STEP1) 배열을 정렬합니다. STEP2.. 백준 알고리즘 #1 - qsort 이번 포스트에서는 qsort에 대해 알아보겠습니다. qsort, 즉 퀵 정렬은 C언어에서 제공하는 '정렬' 라이브러리 함수입니다. 백준을 풀다 보면 여러 가지 알고리즘이 필요하지만, 정렬을 해야만 취할 수 있는 알고리즘이 다수 있습니다. 그러기에 qsort는 선택이 아닌 필수적으로 알아둬야하는 함수입니다. 🏳️ qsort를 사용하기 위해 필요한 헤더 파일? - qsort는 헤더 파일을 불러서 사용할 수 있습니다. 🏳️ qsort의 인자는? - qsort는 4개의 인자를 가집니다. 아래의 형식을 따라서 사용합니다. #include qsort(정렬할 배열의 주소, 배열 요소 갯수, 배열 요소 크기, 사용할 함수); ex) qsort(ary,num,sizeof(char),compare; 🏳️ qsort의 기준.. 이전 1 다음
