B_log

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

- 가장 가까운 수 찾기 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 # 정렬된 n개의 숫자 중 정수 m과 가장 가까운 값 찾기 # 재귀 없이 풀이 def findNum(n, m): # 시작 인덱스와 끝 인덱스 start = 0 end = len(n)-1 while True: mid = (start+end)//2 # 중간 값이 타겟과 같을 때 출력 if n[mid] == m : return n[mid] # 종료 조건, 요소가 2개만 남았을 때 차이가 작은 것 출력 elif end - start ..

분할 정복 - 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산한다. 분할 정복이 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다. - 분할 정복의 세가지 구성 요소 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번 이상 반복되면 코드를 모듈화하는 것이 좋다. - 표준 라이브러리 공부하기 표준 라이브러리 활용을 최대화 하지만 기본적인 배열, 스택, 큐, 리스트, 사전 등의 자료구조 그리고 정렬 등의 표준 알고리즘 구현법은 잘 알아둬야 한다. - 일관적이고 명료한 명명법 사용하기 모호한 명명법을 사용하지 말자. 의미를 이해할 수 있는 명명법을 사용하자 - 자료를 정규화해서 저장하기 시간대, 각도 등 여러가지 방식으로 표현 가능한 변수들의 정의를 한가지로 통일하여 정규화한다. -..

- 문제 상황 : 주어진 리스트를 O(N)으로 순회하며 그 안에서 target - nums[i]의 꼴로 검색할 경우 O(N^2)의 순회가 되어 시간이 초과된다. - 해결책 : 먼저 O(NlogN)의 sort 함수를 사용해 nums를 정렬한 후, 인덱스의 시작점과 끝점을 주어 찾는 값이 target보다 작으면 앞쪽 인덱스를 증가시키고 더 크면 뒷쪽 인덱스를 감소시키는 방향으로 찾는다. - Check Point : 문제에서 주어진 상황이 답이 항상 존재하기 때문에 가능한 방식이다.

😅 문제 문제 이미지 넣기 🤔 문제 상황 - 리스트에 존재하는 수를 제외한 자연수 중 최소값 찾기 🧐 해결 전략 - 1부터 시작해서 배열에 존재하면 1 증가시키고 없으면 반환하는 함수를 만들었다. ==> O(N**2) 의 시간이라 시간 초과가 뜬다. 66% - 다시 생각해서 만든 코드는 중복을 제거하며 정렬한 후에 조건에 맞게 구현하였다. ==> O(N) or O(N*(logN)) 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 def solution(A): setA = sorted(list(set(A))) idx = 0 for i in range(len(setA)): if setA[i] > 0: idx = i break setA = setA[idx:] start = 1 for ..

😅 문제 https://app.codility.com/programmers/lessons/4-counting_elements/max_counters/ 🤔 문제 상황 - 조건에 따라 연산이 다르다. 🧐 해결 전략 - 🎰 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 def solution(N, A): ck = [0]*N mx = 0 for i in range(len(A)): if A[i] mx: mx = ck[A[i]-1] else : ck = [mx]*N # for j in range(N): # ck[j] = mx return ck cs https://colorscripter.com/ 🧙‍♂️ 해설 손글씨로 이미지 넣기 📈 새로 학습한 것 & 실수 - N+1 조건이 나올 때 else 조건 안..