알고리즘

백준과 프로그래머스

백준 vs 프로그래머스 https://sophuu.tistory.com/89 코딩테스트 플랫폼 전격 비교: 백준 vs 프로그래머스 vs Leetcode vs SWEA 그 외 알고리즘 공부, 어디서 어떻게 시작해야할까? 작년 이맘때쯤에 처음 알고리즘 공부를 시작했었는데, 어떤 플랫폼을 써야하는지 엄청 고민했던 기억이 나서 1년동안 직접 사용해 본 다양한 코딩 sophuu.tistory.com https://velog.io/@duboo/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-vs-%EB%B0%B1%EC%A4%80-%EB%AD%90%EB%B6%80%ED%84%B0-%ED%92%80%EC%96%B4%EC%95%BC%ED%95%A0%EA%B9%8C-js ..

1. 재귀(순환)

Reference: C언어로 쉽게 풀어쓴 자료구조 / 생능출판사 / 천인국 1. 순환의 소개 - 순환(recusrion) : 어떤 알고리즘이나 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법 순환의 예 순환은 본질적으로 순환적인 문제나 그러한 자료구조를 다루는 프로그램에 적합하다 순환적인 팩토리얼 계산 프로그램 int factorial(int n) { if (n 복귀 주소가 시스템 스택 (stack) 에 저장되고 호출되는 함수를 위한 매개변수(parameter)와 지역 변수를 스택으로부터 할당받는다. 이러한 함수를 위한 시스템 스택에서의 공간을 활성 레코드(activation record) 라 한다 *호출된 함수가 자기 자신이라면 자기 자신의 시작 위치로 점프하게 되는 것이다 main()에서..

6. 병합(합병) 정렬 (Merge Sort)

Reference : 건국대학교 컴퓨터공학과 자료구조 수업 / 김성열 교수님 합병 정렬의 개념 : 하나의 리스트를 2 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것이다. ==> 합병 정렬은 분할 정복 (divide and conquer) 기법에 바탕을 두고 있다 분할 정복 (divide and conquer) 기법 : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 ==> 분리된 문제가 아직도 해결하기 어렵다면 (충분히 작지 않다면) 분할 정복 방법을 연속하여 다시 적용 ==> 분할 정복 기법은 대개 순환 호출을 이용하여 구현 분할(Divide) : 입력 배열..

3. 선택 정렬(Selection Sort)

Reference : 건국대학교 컴퓨터공학과 자료구조 수업 / 김성열 교수님 C언어로 쉽게 풀어쓴 자료구조 / 천인국 / 생능출판사 선택 정렬의 원리 선택 정렬은 가장 이해하기 쉬운 정렬 방법이다 숫자들은 1차원 배열에 들어 있다고 가정 왼쪽 리스트 : 정렬이 완료된 숫자들 오른쪽 리스트 : 정렬되지 않은 숫자들 선택 정렬 : 오른쪽 리스트에서 가장 작은 숫자를 선택하여 왼쪽 리스트로 이동하는 작업을 되풀이 해서 오른쪽 리스트가 공백 상태가 될 때까지 이 과정을 되풀이하는 정렬 기법 위의 방법은 배열로 구현하기로 하였다면, 위의 방법을 구현하기 위해서는 입력 배열과는 별도로 똑같은 크기의 배열이 하나 더 필요하다. ==> 따라서 메모리를 절약하기 위하여 입력 배열 외에 추가적인 공간을 사용하지 않는 선택..

1. 정렬 알고리즘의 개요

Reference : 이것이 자료구조+알고리즘이다 with C언어 정렬 (Sorting) 정해진 기준에 따라 데이터를 순서대로, 그리고 체계적으로 정리하는 알고리즘 정렬의 목적은 '탐색' 궁극적인 목적은 물건이나 데이터를 쉽게 찾고자 하는 데 있다 고전 알고리즘 버블 정렬, 삽입 정렬, 퀵 정렬

1. 문자열 탐색 알고리즘의 개요

Reference: 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 문자열 탐색 알고리즘 : 특정 문자열에서 특정 문자열을 찾는 알고리즘 => 많은 종류의 문자열 탐색 알고리즘이 개발되었다 ex) Naive, DFA, KMP 문자열 탐색 알고리즘에 쓰이는 용어들 본문 (Text) : 탐색 대상이 되는 문자열을 의미 패턴 (Pattern) : 탐색어를 의미 이동 (Shift) : 본문에서 탐색 위치를 옮기는 일

5. KMP 알고리즘

Reference: - 이것이 자료구조+알고리즘이다 with C언어 / 박상현 / 한빛미디어 - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 KMP 알고리즘 KMP (Knuth-Morris-Pratt) 알고리즘 : '고지식한 탐색' 처럼 탐색 위치를 본문 왼쪽부터 시작해서 오른쪽으로 옮겨가며 문자를 직접 비교하는 방식으로 동작 ==> 하지만 요령을 눈곱만큼도 부리지 않는 고지식한 탐색과 달리, KMP 알고리즘은 비교할 필요 없는 부분은 지나치고 비교가 필요한 부분만 비교를 수행하는 똑똑한 알고리즘 ==> '어떤 정보'가 무엇인지와 이 정보를 '어떻게 활용하는가'에 대한 것 KMP 알고리즘의 동작 방식 어느 문자..

4. DFA 알고리즘

Reference : - 건국대학교 컴퓨터공학과 자료구조 수업 / 김성렬 교수님 - https://inuplace.tistory.com/314 / 이누의 개발성장기 DFA 알고리즘 Naive 알고리즘에서 각 숫자에 대한 표기를 좀 더 하는 방식이다. 첫 글자와 일치하는 곳이 발견되면 그곳에 1을 표기하고, 그 이후로도 일치할 경우 1씩 더 증가시키면서 표기한다. 만약 표기하려는 수가 이미 표기된 수보다 작다면 표기할 수 없다. abcabcd에서 abcd를 찾는다면 abcabcd에는 1231234가 표기될 것이다. 찾으려는 글자의 길이 값이 표기된 갯수가 정답의 갯수가 될 것이다. 이에 대한 경우의 수를 표로 만들어 저장하고, 이를 활용한다. 다음은 abcabcd를 찾을 때 경우의 수 표이다. 위 숫자의 ..