CS/알고리즘23 [알고리즘] 재귀(Recursion), 재귀 호출(Recursive call) 🟡 재귀(Recursion) - 자신을 정의할 때, 자기 자신을 재참조하는 방법 - 재귀함수란 자기 자신을 다시 호출하는 함수 🟡 재귀 함수의 특징 - 재귀함수는 스택 메모리에 쌓이는 형태로 동작 - 종료조건을 명시해 주어야 함 - 스택 메모리에 함수를 계속 쌓았다가, 종료조건을 만나면 위에서부터 하나씩 처리 🟡 재귀함수 사용 예시 - 피보나치 수열 계산 https://seohyun0916.tistory.com/78 [Baekjoon] 10870 - 피보나치 수 5 📝 문제 🔑 풀이 과정 ① 배열을 이용한 방법 n의 최대값이 20이니깐 크기가 21인 배열을 선언해준뒤, for문을 사용하여 값을 넣어준다. 다만 이 경우, n이 아무리 작아도 결국 20까지 전부 다 구해 seohyun0916.tistory... 2023. 1. 2. [알고리즘] 투 포인터, 슬라이딩 윈도우(two pointers, sliding window) 🟡 투 포인터(two pointers) - 1차원 배열에서 2개의 포인터를 사용하여 알고리즘의 시간 복잡도를 최적화하는 알고리즘 - 완전 탐색을 사용하고 시간 초과가 날 때 사용할 수 있는 알고리즘 - 투 포인터를 활용한 문제풀이(알고리즘이 너무 간단하므로 문제로 이해) https://seohyun0916.tistory.com/50 [Baekjoon] 2018 - 수들의 합 5 📝 문제 🔑 풀이 과정 - 내가 풀어놓고 한 번에 맞아서 놀란 문제ㅎ_ㅎ - 문제에서 "연속된 자연수의 합" 이라 명시되어 있으니, 투 포인터 개념을 사용했다. - 조건만 잘 생각해주면 코드 자체는 seohyun0916.tistory.com 🟡 슬라이딩 윈도우(sliding window) - 위에서 설명한 투 포인터를 활용한 알고.. 2022. 12. 14. [알고리즘] 정렬 - 버블 정렬(bubble sort) 🟡 버블 정렬(bubble sort) - 두 인접한 데이터의 크기를 비교하고, swap 연산을 수행하며 정렬하는 방식 - 장점: 간단하게 구현 가능 - 단점: 시간 복잡도가 O(n^2)으로 다른 정렬 알고리즘에 비해 속도가 느린 편 🟡 버블 정렬 과정 ① 비교 연산이 필요한 루프 범위를 설정한다. ② 인접한 데이터 값을 비교한다. ③ swap 조건에 부합하면 swap 연산을 수행한다. ④ 루프 범위가 끝날 때 까지 ②~③을 반복한다. ⑤ 정렬 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다. ⑥ 비교 대상이 없을 때 까지 ①~⑤를 반복한다. + 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다. 2022. 11. 28. [알고리즘] 구간 합 알고리즘(Prefix Sum) 구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다. 🟡 합 배열 정의 S[i]는 A[0]부터 A[i]까지의 합 S[i] = A[0] + A[1] + ... A[i-1] + A[i] S[i] = S[i-1] + A[i] 합 배열을 미리 정의해 놓으면 일정 구간의 합을 구하는 것의 시간복잡도를 줄여준다. +) 합 배열 없이 일정 구간의 합을 구하는것은 시간 복잡도가 O(N)이고, 합 배열이 있으면 시간 복잡도가 O(1)이다. 🟡 구간 합 공식 i부터 j까지의 구간 합은 S[j] - S[i - 1] 2022. 11. 10. [알고리즘] 시간 복잡도(Time Complexity) 알고리즘에서 시간 복잡도는주어진 문제를 해결하기 위한 연산 횟수 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주 🟡 시간 복잡도 유형 빅-오메가: 최선일 때(best case)의 연산 횟수를 나타낸 표기법 빅-세타: 보통일 때(average case)의 연산 횟수를 나타낸 표기법 빅-오: 최악일 때(worst case)의 연산 횟수를 나타낸 표기법 * 코딩 테스트에서는 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음 🟡 시간 복잡도 도출 기준 상수는 시간 복잡도 계산에서 제외한다. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다. 🟡 시간 복잡도 그래프 2022. 10. 20. 이전 1 2 3 4 다음
