B_log

정규 표현식 - 메타 문자 : 원래 그 문자가 가진 뜻이 아닌 특별한 용도로 사용하는 문자 - 문자 클래스 [ ] 정규 표현식이 [abc]라면 이 표현식의 의미는 "a, b, c 중 한 개의 문자와 매치"를 뜻한다. ex) "a"는 정규식과 일치하는 문자인 "a"가 있으므로 매치 "before"는 정규식과 일치하는 문자인 "b"가 있으므로 매치 "dude"는 정규식과 일치하는 문자인 a, b, c 중 어느 하나도 포함하고 있지 않으므로 매치되지 않음 cf) [ ] 안의 두 문자 사이에 하이픈(-)을 사용하면 두 문자 사이의 범위(From - To)를 의미한다. 예를 들어 [a-c]라는 정규 표현 식은 [abc]와 동일하고 [0-5]는 [012345]와 동일하다. - Dot( . ) 정규 표현식의 Dot(..

동적 계획법( dynamic programming) - 문제를 잘게 쪼개 해결해 나가는 과정에서 반복되는 부분을 캐시에 저장하여 재사용하는 기법 - 분할정복과 문제를 작게 쪼깬다는 측면에서 공통점이 있지만 분할정복의 경우 부분문제들이 겹치지 않아 부분문제를 합병해 나가는 과정을 거치고 동적계획법은 반복되는 부분문제의 재연산을 피하기위해 캐시에 저장하는 메모이제이션(memoization)기법을 사용한다. - 참조적 투명성(referential transparency) : 함수의 반환 값이 그 입력 값만으로 결정되는지의 여부(전역변수, 입력 파일 등 함수 외부 요인에 의해 영향을 받지 않는 함수) - 메모이제이션은 참조적 투명 함수의 경우에만 적용할 수 있다. 입력이 같은데 외부 요소에 따라 다른 갑싱 반환..

분할 정복 - 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. - 분할 정복의 세가지 구성 요소 1. 문제를 더 작은 문제로 분할하는 과정 (divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정 (merge) 3. 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제 (base case) - sum(range(n)) 을 구할 경우 1+2+3+..+n을 구하는 연산은 O(N)의 시간 복잡도를 가진다. 분할 정복으로 해당 문제를 분..

6.2 재귀 호출과 완전 탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 # 6.2 재귀 호출과 완전 탐색 # 조건 : n>=1 # 1부터 n까지의 합을 반환 def sum(n) : ret = 0 for i in range(1, n): ret += i return ret # 재귀를 사용 def recursiveSum(n): # 기저조건을 생성 if n == 1 : return 1 return n + recursive(n-1) cs - 코드 6.2 n개의 원소 중 m개를 고르는 모든 조합을 찾는 알고리즘 책에 있는 C++ 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 void pick(int n, vector &picked, int topick)..

3.2 좋은 코드를 짜기 위한 원칙 - 간결한 코드 작성하기 전역변수는 실제 프로그래밍에서는 프로그램의 흐름을 파악하기 어려워 대개 사용하지 않는 것이 좋지만 코테에서는 광범위하게 사용해도 된다. - 적극적으로 코드 재사용하기 같은 코드가 3번 이상 반복되면 코드를 모듈화하는 것이 좋다. - 표준 라이브러리 공부하기 표준 라이브러리 활용을 최대화 하지만 기본적인 배열, 스택, 큐, 리스트, 사전 등의 자료구조 그리고 정렬 등의 표준 알고리즘 구현법은 잘 알아둬야 한다. - 일관적이고 명료한 명명법 사용하기 모호한 명명법을 사용하지 말자. 의미를 이해할 수 있는 명명법을 사용하자 - 자료를 정규화해서 저장하기 시간대, 각도 등 여러가지 방식으로 표현 가능한 변수들의 정의를 한가지로 통일하여 정규화한다. -..