목차

---

1.의사코드(Pseudo Code)

1. 그리디
2. 브루트포스
3. 이진 탐색 알고리즘
4. 순열과 조합

배운 내용

---

알고리즘

• 문제를 해결하는 최선의 선택

풀이전략

• 연습장, 화이트보드에 전체적인 그림을 그려보자
• 인간의 사고로 문제를 해결할 수 있어야한다.
• 알고리즘 전략은 잘 짜여진 수도코드에서부터 시작한다. 코드작성전에 수도코드 먼저 작성하는 습관을 들이자.

**의사코드(pseudocode) 작성법**

• 프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것
• 의사코드를 작성하기 전, 문제를 이해하고 논리 문제를 풀듯이 풀 수 있어야 한다.

시간 복잡도

• 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성하는 것이중요

**Big-O 표기법**

• 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가? 를 표기

O(1)

• 입력값이 증가하더라도 시간이 늘어나지 않는다.

**O(n)**

• 입력값이 증가함에 따라 시간 또한 같은 비율로 증가

**O(log n)**

• O(1) 다음으로 빠른 시간 복잡도
• 숫자를 제시할 때마다 경우의 수가 절반이 줄어든다.

**O(n^2)**

• 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가
• 2n, 5n 을 모두 O(n)이라고 표현하고, n^3과 n^5 도 모두 O(n^2)로 표기
• n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문

**O(2^n)**

• 가장 느린 시간 복잡도

**탐욕 알고리즘(Greedy)**

• 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
• 최적에 근사한 값에 빠르게 도출할 수잇는 근사 알고리즘으로 사용

문제 해결 과정

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합니다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사합니다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

실사용 예시

• 동전 거스름돈

  1. 선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택

  2. 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사,

     초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택

  3. 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사

조건

• 탐욕적 선택 속성 - 앞의 선택이 이후의 선택에 영향을주지 않아야한다.
• 최적 부분 구조 - 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성

**구현(implementation)**

• 알고리즘 문제 푼다는 것 → 내가 생각한 문제 해결 과정을 컴퓨팅 사고로 변환하여 코드로 구현하는것

완전 탐색(brute force)

• 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식(시행착오 방법론)
• 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취하더라도 솔루션을 찾으려고 하는 방법

• 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때

• 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

활용 알고리즘

• 순차 검색 알고리즘 (Sequential Search)

배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색

• 문열 매칭 알고리즘 (Brute-Force String Matching)

길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색

• 선택 정렬 알고리즘 (Selection Sort)

전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘

• 버블 정렬 알고리즘 - Bubble Sort
• Tree 자료 구조의 완전탐색 알고리즘
• 동적 프로그래밍 - DP

**이진 탐색 알고리즘(Binary Search Algorithm)**

• 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘

1. 정렬된 배열의 가장 중간 인덱스를 지정
2. 찾으려고 하는 값이 지정한 중간 인덱스의 값이라면 탐색을 종료, 아니라면 3단계로
3. 찾으려고 하는 값이 중간 인덱스의 값보다 큰 값인지, 작은 값인지 확인
4. 값이 있는 부분과 값이 없는 부분으로 분리
5. 값이 있는 부분에서 다시 1단계부터 반복

특징

• 정렬된 배열에서 요솟값을 더 효율적으로 검색할 때 사용
• 탐색을 반복할 때마다 탐색 범위가 절반으로 줄어 데이터 양이 많을수록 더 높은 효율을 가짐
• 시간복잡도는 O(logn)
• 데이터양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm이 빠를때도있다.

조건

• 배열에만 구현 가능
• 정렬되어 있어야만 구현 가능

활용예시

• 사전 검색
• 대규모 시스템에 대한 리소스 사항 파악

**순열(permutation)과 조합(Combination)**

• 순열과 조합은 재귀를 사용하여 풀이하는 경우가 많다.

순열

• 요소 n개 중에 m개를 선택하여 순서에 상관 있게 뽑는 경우의 수
• 일반식 : nPr = n! / (n - r)!
• 순열은 중복된 요소를 허용하지않는다.

조합

• 순서에 상관없이 요소 n개 중에 m개를 뽑는 경우의 수
• 순서를 생각하느라 중복된 부분이 발생한 순열의 모든 가짓수를, 중복된 n가지로 나누어 주면 조합의 모든 경우의 수를 얻을 수 있습니다.
• 일반식: nCr = n! / (r! * (n - r)!)
• .하나의 요소로 만들 수 있는 모든 경우의 수를 다 구한 다음, 그 요소를 반복에 포함하지 않고 다음 요소부터 시작

팩토리얼(factorial)

• n!은 n에서부터 1씩 감소하여 1까지의 모든 정수의 곱

**정규 표현식**

• 문자열에서 특정한 규칙에 따른 문자열 집합을 표현하기 위해 사용되는 형식 언어

// 정규표현식 사용
public boolean solution(String str) {
	String regExp = "\\d{5}$|\\d{7}$"
	return Pattern.matches(regExp, str)
}

어려운 내용(에러)

---

Arrays.sort(stuff);

for(int i = 0; i < stuff.length -1 ; i++){

            int max = i;
            for(int j = i+1; j < stuff.length; j++ ) {
                if (stuff[j] > stuff[max])
                    max = j;
            }
                int temp = stuff[i];
                stuff[i] = stuff[max];
                stuff[max] =temp;
        }