본문 바로가기

전체 글571

알고리즘 문제 해결 8장 그리디(Greedy) 현재의 상태에서 특정한 값을 기준으로 가장 좋은 것을 선택해 나가는 방법 그리디 알고리즘으로 문제를 해결하기 위해서는 어떠한 반례도 없이 항상 최적의 결과를 얻을 수 있음이 입증되어야 함 1. 현재의 상태에서 가장 좋은 것을 선택하는 것이므로 그 선택의 기준이 되는 것을 정해야 한다. 따라서 여러 가지 선택 기준 중에서 반례가 없는 기준을 찾아야 함 2. 어떤 값을 기준으로 했을 때 반례가 없다는 것이 입증이 되면 그 기준값을 기준으로 정렬하는 것이 필수임 3. 정렬이 되었다면 처음부터 차례대로 선택이 가능한 것을 모두 선택해 나가면 됨 2021. 5. 14.
알고리즘 문제 해결 전략 1권 4.6 수행 시간 어림짐작하기 프로그램의 동작 속도에 영향을 끼치는 요소는 입력의 크기와 시간 복잡도를 제외하고도 엄청나게 많음. 1억이라는 기준은 가능한 한 보수적으로 정한 것임 4.7 계산 복잡도 클래스 : P, NP, NP-완비 일반적으로 다항 시간 알고리즘이나 그보다 빠른 알고리즘들을 빠르다고 말합니다 P문제처럼 같은 성질을 갖는 문제들을 모아놓은 집합을 계산 복잡도 클래스라고 부릅니다. 다항 시간 알고리즘이 존재하는 문제와 존재하지 않는 문제로 문제들을 구분하기란 어렵습니다. 주어진 배열을 비교 정렬하는 문제와 최소치를 찾는 문제의 난이도를 비교하면, 정렬 문제는 최소치 문제 이상으로 어렵다고 말할 수 있습니다. NP문제란 답이 주어졌을 때 이것이 정답인지를 다항 시간 내에 확인할 수 있는 문제를 의미합니다. 이런 속성을 갖.. 2021. 5. 14.
Radix Sort - Radix sort는 데이터의 크기가 커서 Counting Sort가 불가능한 경우 몇 번에 나누어서 처리하는 방법 - data = {254, 535, 892, 250, 862, 891, 155, 367, 445} - 물론 counting sort도 가능한 범위이지만, radix sort는 한자리씩 나누어서 3번에 정렬하는 방법을 사용해 봄 1. 1의 자리를 기준으로 정렬을 함 2. 10의 자리를 기준으로 정렬을 함. 10의 자리가 같은 경우에 기존의 순서를 유지함 3. 100의 자리를 기준으로 정렬을 하되 같은 경우에 기존의 순서를 유지하면 최종 정렬이 완성됨 결국 radix sort는 counting sort를 몇 번 나누어서 실행하는 것임 키 값의 크기를 정하는 방법에 따라 성능의 차이가 있는데.. 2021. 5. 14.
Counting Sort - Counting, Radix sort 시간복잡도 O(N) - 데이터를 키값으로 분류할 수 있는 경우에 한해 적용이 가능 Counting Sort - 데이터 값의 범위가 배열로 나타낼 수 있을 때 가능한 방법 - count arr 에서 누적합이 11 이라면, 5이하인 수들이 모두 11개이라는 것. 따라서 5는 배열의 11번쨰에 들어가면 됨 - 그리고 이제 남은 수들중 5이하인 개수는 10개가 됨. 1. 각 데이터의 개수를 나타내는 배열을 채움 2. 작은 수부터 누적합을 구함 N은 데이터의 개수이고, M은 데이터의 최대값. #include #define N 10 // arr Max #define M 10 // arr var range 0~10 void CountingSort(int a[]) { int i.. 2021. 5. 14.
Clean Code를 위한 Code Refactoring "Code Refactoring의 개념" - 티끌 모아 태산 - 특별한 활동이 아님 - 단위테스트까지 ㄱㄱ "Code Bad Smell" - 중복 코드 - 긴 메소드 - 큰 클래스 - 파라미터가 너무 많음 - Divergent change 관련 없어 보이는 메소드 같이 수정됨 => Extract Class - Shotgun Surgery : 단일 기능 변경 요구사항에 대해 다수의 클래스를 수정 해야 함 => extract method - Refused Bequest : 상속 받은 부모 클래스의 기능을 사용하지 않음 - Primitive Obsession : 클래스를 활용하지 않고, 원시 데이터 타입만 고집하여 사용 - Message Chains : 긴 메소드 연쇄 호출이 있음 "Code Refactori.. 2021. 5. 14.
Clean Control Structure "Clean Control Structures" - 조건, 루프, 흐름을 제어하는 선언문 - Cyclomatic Complexity : 소스 코드의 복잡도를 나타내는 지표 - V(G) = edge의 수 - node의수 + 2 - V(G) = 분기문의 수 + 1 - 10, 25 이하 권고, 50은 넘어가면 테스트 불가능임 "읽기 쉬운 조건문" - 왼쪽에 궁금한 대상. - 왼쪽 항 : 값이 변경될 가능성이 높은 표현/주로 변수의 이름 - 오른쪽 항 : 값이 주로 고정 - 매직 넘버 그 의미를 알 수 없는 임의의 수 "Fail Fast, Early Return" - 가독성이 좋도록 중첩if 문을 개별 if 문으로 변경하는 것 - 빨리 실패하는 검증로직을 다시 method로 분리하고 예외를 사용함 - if(a=.. 2021. 5. 14.
Clean Formatting "Clean Formatting" - 코드는 사람이 읽도록 만들어지는 것이 우선 - 어떤 동작을 원하는지 사람에게 설명하는 것임 - 코드 라인 간의 간격/코드 그룹화 - 들여쓰기, 간격, 넓이 - 정적 분석을 통해서 가능함 "수직 Formatting 원칙" - Enter 사용 - 추상화의 수준 순서 - 서로 다른 개념은 분리 - 유사한 개념은 모아 놓음 - 관계 있는 내용은 가까운 행에 작성 - 코드를 읽기 위해 여러 번의 Jump를 하는 것을 방지 "수평 Formatting 원칙" - 약 80자 -> 최근에는 모니터가 크기가 커져 100자도 괜찮음 - 들여쓰기 - 한 줄의 긴 코드는 두 줄로 - 수평 정렬은 크기 중요하지 않음 google guide : never required "Summary" - .. 2021. 5. 14.
Clean Comment "Clean Comment의 원칙" - Comment는 필요악 - Comment보다 Code 그 자체가 의미가 있어야 함 "Bad Comment" - Code 자체를 개선해야 함. 코멘트로 이해 시키려고 하면 안됨. - 중복된 정보를 제공 하는 커멘트 - git 형상 관리로 안쓰는 code는 관리 해야 함. - 수정 이력을 남겨놓는 것들 또한 git에서 관리 하도록 해야 함 - Comment 자체가 bad smell임 "Clean Comment" - 저작권 명시 - 불가피하게 이름만으로 충분히 의미를 전달하기 어려운 경우 - TODO comment "Summary" 2021. 5. 14.
Clean Code chapter4.3~ (method) "작고 역할이 명확한 method" - 기본적인 라인수를 20라인을 넘기지 않도록 할 것 - 크기 만으로 함수의 품질을 판단 할 수 없다 - 중요한 것은 지속적인 개선 - Method 동작을 설명하기 위해 내부에 주석을 달아야 하면 Bad smell 임 "한 가지의 명확한 역할" - 한 가지의 일을 한다는 것이 정확히 어떠한 의미인가? - 하나의 method는 동일한 추상화의 수준만 가져야 한다. - Higher level code -> what - Lower level code -> how - Method의 이름이 책임지는 범위의 일만 해야 한다 "중복 코드" - 다수의 method의 구현부가 100% 일치하는 경우 - 불필요하게 코드 베이스를 크게 만듦 - 정적 분석 : 중복 코드를 찾아내는 정적 분.. 2021. 5. 14.

티스토리툴바