TIL_20220927

오늘 할 일

😂 코드 스테이츠 26일차

[자료구조/알고리즘] 코딩 테스트 준비

• 연습문제 - Daily Coding
• Chapter - Introduction
• Chapter - Time Complexity
• Chapter - Greedy Algorithm / Implementation

다른거

• 1일 1커밋
• 아침 운동

오늘 배운 것

⌨️ 코딩 테스트 준비

Algorithm

문제를 해결하는 최선의 선택느낀점

 

알고리즘의 3 STEP

1. 문제 이해
2. 문제 해결 전략 세우기
3. 문제를 코드로 작성하기

의사코드(pseudocode)

프로그래밍 언어로 코드를 작성하기 전에 우리가 쓰는 일상 언어로 프로그램이 작동하는 논리를 먼저 작성하는 것이다.

 

• 의사코드를 작성하기 전, 문제를 이해하고 논리 문제를 풀듯이 풀 수 있어야 한다.
• 이후 컴퓨터가 해결할 수 있는 방식으로 의사코드를 작성하고, 개발 언어를 통해 코드를 작성한다.

 

의사코드의 장점

1. 시간 단축: 무작정 코드를 작성하게 되면 문제 풀이가 막히게 됐을 때, 복잡한 문제의 경우는 로직의 흐름을 따라가는 것이 어려울 때가 있다. 만약 의사코드를 미리 작성해두고 코드를 작성한다면 각 코드에 대한 의미를 바로 파악할 수 있기 때문에 문제 해결에 놓친 부분이나 잘못 작성한 부분을 금방 캐치할 수 있다.
2. 디버깅에 용이하다: 보통 알고리즘 문제를 풀면 곧바로 맞는 경우가 많지는 않다. 테스트를 하고 오류가 발생하면 디버깅을 하게 된다. 이 때 어느 부분에 오류가 났는지 확인하는 과정에서 의사코드를 코드와 함께 확인하면 로직에 더 신경쓸 수 있어 원인 파악에 도움이 된다.
3. 프로그래밍 언어를 모르는 사람과 소통이 가능하다: 프로그래밍 언어에 익숙하지 않은 사람도 나의 수도 코드를 보며 로직을 이해하는 데 도움이 될 수 있다. 우리가 쓰는 일상 언어로 쓰여있기 때문에 현업에서 비개발자와도 소통하기 용이하다.

 

의사코드가 구체적이어야 하는 이유

컴퓨터는 사람과 달리 상상력이 없다. 그저 주어진대로 작업을 수행할 뿐이다. 그래서 작업을 수행할 수 있도록 사람이 로직을 기초적인 부분부터 구체적으로 작성하여 명령해주어야 한다.

- 샌드위치 코딩 유튜브 영상

https://www.youtube.com/watch?v=cDA3_5982h8

 

• 샌드위치 코딩이라는 영상인데, 아이들에게 샌드위치를 만드는 과정을 적어달라고 하여 컴퓨터의 동작방식을 보여주고 있다.
• 의사코드를 한번씩 작성해보자!

 

의사코드 양식

• 다른 사람도 이해할 수 있는 자연어(영어나 한국어처럼 일상에서 사용되는 언어)만 사용한다.
• 자연어와 프로그램 언어의 조합을 사용한다.

시간복잡도(Time Complexity)

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가에 대한 내용이다.

 

• 알고리즘 문제를 푸는 데에서 중요한 점은 문제를 해결하는 것이다. 하지만 그에 못지 않게 중요한 것이 얼만큼 효율적인 방법으로 문제를 해결했는지다.
• 효율적인 방법을 고민한다는 것은 시간복잡도를 고민한다는 것과 같은 의미이다.
• 효율적인 알고리즘을 구현한다는 것은 “입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다”는 이야기이다. 그리고 이 시간 복잡도는 주로 빅-오 표기법을 사용해 나타낸다.

 

Big-O 표기법

“입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가”를 표기하는 방법이다. 빅오 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다. 최악의 경우를 대비하면 그보다 나은 상황은 저절로 해결된다.

최악의 경우가 발생하면 문제를 파악하는 데에 많은 시간이 필요해진다. 그렇기 때문에 최악의 경우를 대비하는 것이 중요하다.

 

순위	명칭
O(1)	상수 시간
O(logN)	로그 시간
O(N)	선형 시간
O(NlogN)	로그 선형 시간
O(N^2)	이차 시간
O(N^3)	삼차 시간
O(2^n)	지수 시간

아래로 갈수록 속도는 느려진다.

 

데이터 크기에 따른 시간 복잡도

데이터 크기 제한	예상되는 시간 복잡도
n ≤ 1,000,000	O(n) or O(logn)
n ≤ 10,000	O(n^2)
n ≤ 500	O(n^3)

 

입력 데이터가 클 때는 O(n) 혹은 O(log n)의 시간 복잡도를 만족할 수 있도록 예측해서 문제를 풀어야 한다. 그리고 주어진 데이터가 작을 때는 시간 복잡도가 크더라도 문제를 풀어내는 것에 집중하는 것이 좋다.

Greedy

탐욕스러운, 욕심 많은이라는 뜻인 Greedy는 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니다.

 

Greedy 문제의 조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

Greedy의 문제 해결법

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

구현(implementation)

프로그래밍 언어의 문법을 정확히 알고 있어야 하며, 문제의 조건에 전부 부합하는 코드를 실수 없이 빠르게 작성하는 것을 목표로 두는 것이 구현 문제의 의도이다.

 

구현 능력을 보는 대표적인 사례

• 완전 탐색: 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식
• 시뮬레이션: 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습을 그린다.

시뮬레이션(Simulation)

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다. 보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.

완전 탐색 알고리즘(Brute-Force Algorithm)

Brute Force Algorithm은 무차별 대입 방법을 나타내는 알고리즘이다. 순수한 컴퓨팅 성능에 의존하여 모든 가능성을 시도하여 문제를 해결한다. 공간복잡도와 시간복잡도의 요소를 고려하지 않고 최악의 시나리오를 취할 것까지 고려하기 때문에 최적의 알고리즘은 아니지만 솔루션을 찾으려고 하는 방법을 의미한다.

암호학에서는 공격 방식 중 하나로 소개되는데, 0-9까지의 숫자를 대입할 수 있는 4자리 숫자로 된 자물쇠는 최악의 경우 10^4 = 10,000회만 시도하면 비밀번호를 알아낼 수 있다. 0000 ~ 9999까지 하나씩 대입하여 시도하는 방법이 Brute Force Attack이다.

 

Brute Force를 사용하는 경우

• 프로세스 속도를 높이는데 사용할 수 있는 다른 알고리즘이 없을 때
• 문제를 해결하는 여러 솔루션이 있고 각 솔루션을 확인해야 할 때

 

Brute Force Algorithm의 한계

• Brute Force Algorithm은 문제의 복잡도에 매우 민감한 단점을 가지고 있다. 문제가 복잡해질수록 기하급수적으로 많은 자원을 필요로 하는 비효율적인 알고리즘이 될 수 있다. 여기서 자원은 시간이 될 수도 있고 컴퓨팅 자원이 될 수도 있다.
• 일반적으로 문제의 규모가 현재 자원으로 충분히 커버가 가능한 경우에 Brute Force Algorithm을 사용한다. 만약 이를 벗어난 경우는 정확도를 조금 희생하고 더 효율적인 알고리즘을 사용한다.

 

Brute Force Algorithm의 종류

• 순차 검색 알고리즘 (Sequential Search): 배열 안에 특정 값이 존재하는지 검색할 때 인덱스 0부터 마지막 인덱스까지 차례대로 검색
• 문자열 매칭 알고리즘 (Brute-Force String Matching): 길이가 n인 전체 문자열과 길이가 m인 문자열 패턴을 포함하는지를 검색
• 선택 정렬 알고리즘 (Selection Sort): 전체 배열을 검색하여 현재 요소와 비교하고 컬렉션이 완전히 정렬될 때까지 현재 요소보다 더 작거나 큰 요소(오름차순 또는 내림차순에 따라)를 교환하는 정렬 알고리즘
• 버블 정렬 알고리즘 - Bubble Sort
• Tree 자료 구조의 완전탐색 알고리즘 - Exhausive Search (BFS, DFS)
• 동적 프로그래밍 - DP(Dynamic Programing)

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

데이터가 정렬된 상태에서 절반씩 범위를 나눠 분할 정복기법으로 특정한 값을 찾아내는 알고리즘이다. 탐색을 반복할 때마다 탐색 범위가 절반으로 줄어들게 되는 이 알고리즘은 데이터 양이 많을수록 더 높은 효율을 가진다. 시간복잡도는 O(log n)로, 빠른 편이지만 항상 효율이 좋은 것은 아니다.

 

이진 탐색 알고리즘의 동작 방법

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

 

이진 탐색 알고리즘을 사용하는 경우

• 정렬된 배열에서 요소값을 더 효율적으로 검색할 때 사용
• 데이터의 양이 많으면 많을수록 효율이 높아서 정렬된 데이터의 양이 많을 때 사용

 

이진 탐색 알고리즘의 한계

• 배열에만 구현할 수 있다.
• 정렬되어 있어야만 구현할 수 있다. 규모가 작은 배열이라도 정렬이 되어 있지 않다면 정렬을 한 후 Binary Search Algorithm을 사용해도 효율이 높지 않다.
• 한 예로 데이터양이 적고 앞쪽에 위치한 데이터를 탐색할 때는 Linear Search Algorithm이 이진 탐색 알고리즘보다 빠른 구간이 존재한다.

 

- 1일 1커밋

프로그래머스 사이트에서 Lv.2 영어 끝말잇기라는 문제를 풀었다. 스택으로 문제를 풀다가 조건문 작성에 코드가 너무 더러워보여서 List로 바꿨다. 

 

GitHub - chaning49/algorithm: 코딩테스트를 위한 알고리즘 공부

 

- 아침 운동

9일차

느낀점

• 수업에서 배운대로 수도코드를 먼저 작성해놓은 후에 코드를 작성해봤습니다. 가이드가 잡혀있는 것 같아서 익숙해지면 좋을 것 같다는 생각이 들었습니다.
• 오늘은 간만에 페어 프로그래밍 없이 혼자서 공부하는 시간이었습니다. 그리디 알고리즘은 예전에 공부했던 내용이라 읽는 데에 수월하게 느껴졌습니다. 이외에 구현 알고리즘이나 이진 탐색 알고리즘을 직접 그림으로 보면서 학습했습니다. 아직 코드로는 감이 잘 오지 않지만 하나씩 하면서 나아질거라 믿습니다.
• 오늘 커밋했던 알고리즘 문제는 제가 요즘 스택과 큐를 자주 사용하다보니 갇힌 사고를 하고 있음을 일깨워줬습니다. 리스트로 짜면 더 보기 좋은 코드를 스택으로 짜보려다 안되는 것이 더 많았습니다. ㅎㅎㅎ...
• 오늘은 유산소 운동을 했는데, 헬스장에 사람이 꽤 많더라구요! 내일은 꼭 일찍 일어나서 루틴대로 근력운동을 하겠습니다.

내일 할 일

😐 코드 스테이츠 27일차

[자료구조/알고리즘] 코딩 테스트 준비

• 연습문제 - Daily Coding
• 연습문제 / Greedy Algorithm / Implementation

다른거

• 1일 1커밋
• 아침 운동