[코드스테이츠] 05_17_TIL : 알고리즘/자료구조 _ Greedy/Algorithm
Today I Lean
리눅스 맛보기 & 개념정리
너무 어렵다.
학습목표 및 개념정리
# Algorithm
-
# 의사코드 (Pseudocode)
-
# 시간 복잡도 (Time Complexity)
-
# Greedy
-
# Implementatrion - Simulation
-
# Brute-Force Algorithm
-
# __ Search Algorithm
-
배운 것
# 탐욕 알고리즘(Greedy)
1. Greedy 란?
: 탐욕스러운, 욕심많은
→ 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법
→ 항상 최적의 결과를 도출하진 않지만, 어느정도 최적에 근사한 값을 빠르게 도출할 수 있음 (근사알고리즘 이라고도 함)
2. 탐욕알고리즘으로 문제를 해결하는 방법
선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
적절성 검사 (Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
해답 검사 (Solution Check) : 원래의 문제가 해결되었는지 검사, 해결되지 않았다면 선택절차로 돌아가 위의 과정 반복
3. 탐욕 알고리즘이 성립하기 위한 조건
탐욕적 선택 속성 (Greedy Choice Property) : 앞의 선택이 이후의 선태겡 영향을 주지 않을 때
최적 부분 구조 (Optimal Suvstructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨
# 구현 (Implementation) - 시뮬레이션 (simulation)
1. 알고리즘 문제를 푼다는 것은?
: 내가 생각한 문제 해결 과정을 컴퓨터의 사고로 변환하여 코드로 구현한 것
2. 시뮬레이션 (Simulation)
: 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형
- 조건
- 캐릭터는 아이디, 닉네임, 소속이 영문으로 담긴 배열로 구분
- 소속 : ture, false, null
- 소속이 셋중 하나가 아니라면 아이디, 닉네임, 소속, 대화 내용의 문자열을 전부 X로 바꿈
- 아이디와 닉네임의 길이는 2진수로 변환
- 캐릭터와 대화내용을 구문할 땐 "공백 : 공백" 으로 구분 ex) 'Blue', 'Green', 'null' : hello
- 띄어쓰기 포함, 대화 내용 < 10 일 때 내용에 ". , +" 가 있다면 삭제
- 띄어쓰기 포함, 대화내용 > 10 일 때 내용에 ". , - + @ # $ % ^ & * ? !" 가 있다면 삭제
- 띄어쓰기를 기준으로 문자열 반전 ex) 'abc -> 'cba'
- 띄어쓰기를 기준으로 소문자와 대문자를 반전 ex) 'Abc' -> 'aBC'
- 같은 캐릭터가 두 번 말했다면, 공백을 한 칸 두고 대화 내용에 추가
- 대화는 문자열로 제공, 하이픈 - 으로 구분 됨
- 문자열은 모두 싱글쿼터(')로 제공, 전체를 감싸는 문자열은 더블쿼터(")로 제공
- 작성 예시
"['Blue', 'Green', 'null'] : 'hello. im G.' - ['Black', 'red', 'true']: '? what? who are you?'" 입력값으로 받은 문자열을 각 캐릭터와 대화에 맞게 문자열로 파싱을 하고, 파싱한 문자열을 상대로 캐릭터와 대화를 구분합니다.
- 첫 번째 파싱은 을 기준으로 ['Blue', 'Green', 'null'] : 'hello. im G.', ['Black', 'red', 'true']: '? what? who are you?' 두 부분으로 나눕니다.
- 두 번째 파싱은 : 을 기준으로 ['Blue', 'Green', 'null'] 배열과 'hello. im G.' 문자열로 나눕니다.
배열과 문자열을 사용해, 조건에 맞게 변형합니다.
- 소속이 셋 중 하나인가 판별합니다.
- {"Blue", "Green", "null"} 아이디와 닉네임의 길이를 2진수로 바꾼 뒤, 숫자를 더합니다: {"100", "101", "null"}
- 'hello. im G.' 10 글자가 넘기 때문에, .,-+@#$%^&* 를 삭제합니다: "hello im G"
- "hello im G" 띄어쓰기를 기준으로 문자열을 반전합니다: "olleh mi G"
- "olleh mi G" 소문자와 대문자를 반전합니다: "OLLEH MI g"
변형한 배열과 문자열을 키와 값으로 받아 Map에 넣습니다.
- { "[100, 101, 'null']": 'OLLEH MI g' }
3. 완전 탐색 알고리즘 (Brute-Force Algorithm)
: Brute-Force (시행착오 방법론)
→ 모든 값을 대입하는 방법
→ 지능형 전략을 사용하지 않음
- Brute-Force Algorithm (BFA) 란?
: 무차별 대입 방법을 나타내는 알고리즘
: 모든 가능성을 시도하여 문제를 해결
: 어떻게든 솔루션을 찾으려고 하는 방법을 의미
- 사용되는 경우
: 프로세스 속도를 높이고 싶은데, 사용할 수 있는 다른 알고리즘이 없을 때
: 문제를 해결하느느 여로 솔루션이 있고, 각 솔루션을 확인해야 할 때
→ 문제에 더 적절한 해결 방법을 찾기 전에 먼저 시도하는 방법
- 순차 검색 알고리즘 (Sequential Search) : 배열 안에 특정 값이 존재하는지 검색할 때, [0]~배열의[-1] 까지 차례로 검색
public boolean SequentialSearch2(int[] arr, int K) {
// 검색 키 K를 사용하여 순차 검색을 구현
// 입력: n개의 요소를 갖는 배열 A와 검색 키 K
// 결과를 저장할 boolean result선언, 초기값은 false
// 출력: K값과 같은 요소 인덱스 또는 요소가 없을 때 false
int n = arr.length; // 현재의 배열 개수를 n에 할당합니다.
boolean result = false;
for(int i = 0; i < n; i++) {
if(arr[i] == K) {
result = true;
}
}
return result;
}
//배열을 순회하는 도중에, 해당하는 값이 발견되더라도 배열을 모두 순회한 이후에 결과값을 리턴- 문열 매칭 알고리즘 (Brute-Force String Matching) : 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지 검색
문자열 : ABCDBDBCCDBDA
패턴 : CDBD
ABCDBDBCCDBDA
CDBD CDBD
------------------------------------------------------------------------------------------
public boolean BruteForceStringMatch(String[] arr, String[] patternArr) {
// Brute Force 문자열 매칭을 구현합니다.
// 입력: n개의 문자 텍스트를 나타내는 배열 T, m개의 문자 패턴을 나타내는 배열P
// 출력: 일치하는 문자열이 있으면 첫번째 인덱스를 반환합니다. 검색에 실패한 경우 -1을 반환합니다.
int n = arr.length;
int m = patternArr.length;
for (int i = 0; i <= n - m; i++) {
// 전체 요소개수에서 패턴개수를 뺀 만큼만 반복합니다. 그 수가 마지막 비교요소이기 때문입니다.
// i 반복문은 패턴과 비교의 위치를 잡는 반복문입니다.
int j = 0;
// j는 전체와 패턴의 요소 하나하나를 비교하는 반복문입니다.
while (j < m && patternArr[j].equals(arr[i + j])) {
// j가 패턴의 개수보다 커지면 안되기때문에 개수만큼만 반복합니다.
// 패턴에서는 j인덱스와 전체에서는 i + j 인덱스의 값이 같은지 판단합니다.
// 같을때 j에 +1 합니다.
j = j + 1;
}
if (j == m) {
// j와 패턴 수가 같다는 것은 패턴의 문자열과 완전히 같은 부분이 존재한다는 의미입니다.
// 이 때의 비교했던 위치를 반환합니다.
return true;
}
}
return false;
}- 선택 정렬 알고리즘 (Selection Sort) : 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 || 내림차순)를 교환
public int[] SelectionSort(int[] arr) {
// 주어진 배열을 Selection Sort로 오름차순 정렬합니다.
// 입력: 정렬 가능한 요소의 배열 A
// 출력: 오름차순으로 정렬된 배열
for (int i = 0; i < arr.length - 1; i++) {
// 배열의 0번째 인덱스부터 마지막인덱스까지 반복합니다.
// 현재 값 위치에 가장 작은 값을 넣을 것입니다.
int min = i;
// 현재 인덱스를 최소값의 인덱스를 나타내는 변수에 할당합니다.
for (int j = i + 1; j < arr.length; j++) {
// 현재 i에 +1을 j로 반복문을 초기화하고 i 이후의 배열요소과 비교하는 반복문을 구성합니다.
if (arr[j] < arr[min]) {
// j인덱스의 배열 값이 현재 인덱스의 배열 값보다 작다면
min = j;
// j 인덱스를 최소를 나타내는 인덱스로 할당합니다.
}
}
// 반복문이 끝났을 때(모든 비교가 끝났을때)
// min에는 최소값의 인덱스가 들어있습니다.
// i값과 최소값을 바꿔서 할당합니다.
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
// 모든 반복문이 끝나면 정렬된 배열을 반환합니다.
return arr;
}- 버블 정렬 알고리즘 (Bubble Sort)
- Tree 자료 구조의 완전탐색 알고리즘 (Exhausive Search (BFS, DFS)
- 동적 프로그래밍 (Dynamic Programing)
- Brute Force vs Dynamic Programing
- Closet-Pair Problems by Brute Force
- Convex-Hull Problems by Brute Force
- 한계
문제의 복잡도에 매우 민감
→ 정확하지만, 문제가 복잡해 질 수록 기하급수적으로 많은 자원이 필요한 비효율 적인 알고리즘이 될 수 있음
4. 이진 탐색 알고리즘 (Binary Search Algorithm)
: 데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘 (==업다운 게임)
- 동작 원리
정렬된 배열의 가장 중간 인덱스 지정
찾는 값이 지정한 중간 인덱스의 값이라면 탐색 종료, 아니라면 다음 단계
찾는 값이 중간 인덱스 보다 큰 값인지 작은값인지 확인
값이 있는 부분과 없는 부분으로 분리
값이 있는 부분에서 다시 처음부터 반복
- 사용되는 경우
: 정렬된 배열에서 요소 값을 더 효율적으로 검색할 때 사용
: 데이터의 양이 많을수록 효율이 높음 (데이터의 양이 많을 때 사용)
: 시간복잡도은 O(log n)으로 빠른편이지만, 항상 효율이 좋지는 않음
→ 데이터의 양이 적고, 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm이 빠른 구간이 존재함
→ 대규모의 데이터 검색에 주로 사용
사전검색 : 사전에서 단어를 찾을 때 사용
도서관 도서 검색 : 도서관에서 사용하는 도서 코드로 도서를 검색할 때 사용
대규모 시스템에 대한 리소스 사항 파악 : 시스템 부하 테스트에서 예측된 부하를 처리하는데 필요한 CPU양에 대해서 파악할 때 사용
반도체 테스트 프로그램 : 디지털, 아날로그 레벨으르측정하는데 사용
- Binary Search Tree(BST) vs Binary Search Algorithm(BSA)
| Binary Search Tree(BST) | Binary Search Algorithm(BSA) | |
| 차이점 | 자료구조 | 해결 방법 |
| 하나의 노드가 두개의 하위 트리를 가지는 이진트리로 이루어진 자료구조 | ||
| 공통점 |
차이점과 공통점 더 알아보기
- 한계
배열에만 구현 가능
정렬되어 있어야지만 구현 가능 (규모가 작은 배열도 정렬되어 있지 않다면, 정렬 후 Binary Search Algorithm을 사용해도 효율이 떨어짐)
6. 선형 탐색 알고리즘 (Linear Search Algorithm)
5. 해시 탐색 알고리즘 (Hash Search Algorithm)
7. 그 외
- Divide-and-conquer algorithm
- Binary Tree vs Binary Search Tree
- Binary Search Algorithm vs Binary Search Tree
*****
1. Read, Write, Execute 권한
- 처음 보는 개념이라 이해하기가 힘들었다. 한번봐서는 어려워서 읽고 쉬고 읽고 쉬고 세번쯤 반복했더니 그래도 머리에 들어왔다. 물론 완벽히 알진 못하지만 다음에 또 보면 더 잘 알 수 있을 듯 하다.
2. 인자 : 프로그래밍 언어에서 함수 호출 시 함수에 전달되는 값. 인수나 전달인자라고도 부른다.
함수 값? 호출값?
3. CLI 명령어 더 알아보기
Tomorrow Chapter
# 버전 관리 시스템 - Git
# Git 설치
# Git Workflow
# Pair - Simple Git Workflow
# Checkpoint - Git Command
↓ 이전 글 ↓
[코드스테이츠] 04_12_TIL : 프론트엔드 이해하기
Today I Lean 프론트엔드 이해하기 아침에 일어나서 바로 공부를 시작하는게 습과이 안돼있어서 그런지 쉽지 않았다. 그래도 최대한 준비시간을 줄여보고자 커피도 미리 타놓고 긴장하고 잠들었던
theflower01.tistory.com
↓ 코트스테이츠 부트캠프 관련 글 한번에 보기 ↓
'IT/코드스테이츠 부트캠프' 카테고리의 글 목록
Flower, Plant, Study
theflower01.tistory.com
tag
국비지원
내일채움
백엔드
백엔드부트캠프
부트캠프
코드스테이츠
코드스테이츠코딩교육
코드스테이츠후기
코드스테이츠부트캠프
코딩부트캠프
'Study > 코드스테이츠 부트캠프' 카테고리의 다른 글
| [코드스테이츠] 05_22_TIL : 네트워크 _ 웹 애플리케이션의 작동원리 (0) | 2023.05.23 |
|---|---|
| [코드스테이츠] 05_19_TIL : 알고리즘/자료구조 _ Algorithm with Math (순열/조합) (0) | 2023.05.19 |
| [코드스테이츠] 05_16_TIL : 알고리즘/자료구조 _ Tree, Graph Search Algorithm (1) | 2023.05.16 |
| [코드스테이츠] 05_15_TIL : 알고리즘/자료구조 _ Tree / Graph (2) | 2023.05.16 |
| [코드스테이츠] 05_12_TIL : 알고리즘/자료구조 _ Stack/Queue (0) | 2023.05.13 |
