✔️ Divide and Conquer? 1) 전략 - 주어진 문제의 입력을 분할하여 문제를 해결하는 방식 - 분할한 입력에 대해 동일 알고리즘을 적용하여 해 계산, 이들의 해를 취합하여 원래 문제의 해 얻음 - 부분문제(subproblem): 분할된 입력에 대한 문제, 부분해: 부분문제의 해 - 부분문제는 더이상 분할할 수 없을 때까지 계속 분할 2) 과정 - 분할(divide): 해결되기 쉽도록 문제를 여러 개의 작은 부분으로 나눔 - 정복(conquer): 나눈 작은 문제를 반복하여 각각 해결 (Top-Down) - 통합(combine): 해결된 작은 답들을 모아 원래 문제의 해답 구함 (Bottom-Up) 3) 종류 - Sorting: merge sort, quick sort - Binary tr..

✔️ Brute Force Algorithm - 가장 간단하고 직접적인 방식으로 문제를 해결 - 효율적이고 정교한 알고리즘보다 많은 작업을 할 가능성이 높음 - 그렇지만 구현하기가 쉬우며 이로 인해 더 효율적일 수도 있음 - Exhaustively enumerate all the possibilities. 1) Selection Sort - 현재 idx 값 ↔ 배열에서의 최솟값 for i ← 0 ~ n-2 min ← i for j ← i+1 ~ n-1 if A[j] < A[min] min ← j swap A[i] and A[min] - Time efficiency: O(n^2) 2) Bubble Sort - 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환 for j = 1 to n for i = 0 ..

✔️ Searching Algorithm 1) 자료 탐색? - 수많은 자료 중 원하는 자료 찾는 작업 - 컴퓨터에서 처리되는 핵심 알고리즘 중 하나 - Search Key (탐색 키): 탐색할 때 기준이 되는 값 (항목과 항목을 구별하는 값) - 사용되는 자료구조: 배열, 연결 리스트, 트리, 그래프 등 - ex) 컴퓨터에서 저장된 파일 찾기: 파일 탐색기, 위치 모르면 완전 탐색 (exhaustive search) 2) 자료 탐색 과정 1) 탐색 기준 정하기: 탐색 키 선정 2) 자료 비교하기: 탐색 키와 자료 리스트에 포함된 자료들의 비교 ⭐️ 3) 자료 찾기: 탐색의 성공, 실패에 대한 판가름 3) 자료 탐색 결과 - 존재하는 경우: 탐색 키에 해당하는 인덱스 번호 반환 - 존재하지 않는 경우: 일..

자료구조와 알고리즘 - 프로그램이란 데이터를 표현하고 (자료구조) 그렇게 표현된 데이터를 처리하는 것 (알고리즘) - Input → [Process] → Output 자료구조의 분류 - 선형 구조: 1 : n / 비선형 구조: n : m - 배열, 연결리스트: 물리적으로 어떻게 저장되어 있는지로 구분 - 스택, 큐: 접근 방식에 따라 구분 ADT (Abstract Data Type) - 데이터 타입을 추상적으로 정의한 것 - 데이터나 연산이 무엇(what)인가를 정의함 (Set of operations) - 데이터나 연산을 어떻게(how) 컴퓨터 상에서 구현할 것인지는 정의하지 않음 - ADT가 설명해야 하는 것: - 자료구조를 어떻게 생성하고 제거하는지 - 어떻게 item을 추가하고 삭제하는지 - 어떻..

소프트웨어 개발 - 프로그램: 소프트웨어를 만드는 것 - 요구사항 분석 (What, 논리적 사고력, 추상화) → Design (How, 알고리즘) → Implement (Do it!, 프로그래밍 언어) → Test (Check) → Maintenance (Getting Better) 알고리즘이란? - 전산학의 핵심 기술 - 컴퓨터를 사용하여 문제 해결하는 절차를 체계적으로 제시 - 특정한 일을 수행하는 명령어들의 유한 집합 (절차적 처리, 효율적 실행, 전략적 접근, 정확한 결과) - 입력으로부터 출력을 생성해내는 과정 - A plan of solution for a problem (strategy) - Find algorithms that are fast for very large inputs - An..

What is Big-O? - Mathematical notation that describes algorithm efficiency - Time & Space complexity - Describes the growth rate of algorithms - Big-O에서 상수는 버림 (ex. O(2n) → O(n), O(n^2 + n^2) → O(n^2)) ∵ 알고리즘의 running time을 재기 위함이 아니라 데이터의 증가에 따른 처리시간 증가율을 예측하기 위함 O(1) : constant time - 입력 데이터의 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘 // 배열의 길이와 관계없이 언제나 일정한 속도로 결과 반환 F(int[] n) { return (n[0] == 0) ? true..