AI Platform / Web

0. 들어가면면서 메모이제이션을 찾는다는 것은 기본적인 재귀가 익숙하다는 전제로 설명하겠다. 1. Memoization 메모이제이션(memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법(DP)의 핵심이 되는 기술이라 할 수 있다. 메모이제이션의 장점인 실행속도를 높이기 위한 설명으로 우선은 재귀로 피보나치수열을 구하는 코드를 확인해 보자. def fibo(n): if n > 3: # 이 부분이 있어야 무한정으로 n값이 낮아지지 않는다. return 1 else: return fibo(n-1) + fibo(n-2) 여기서의 가장 큰 문제는 호출을 계속하면 같은 수에 대해 엄청난 호출..

0. 들어가면서 일단, 개념위주가 아니라 실전 문제 푸는 스킬위주로 적을예정이다. 그리고 백트래킹에 대해 가능한 모든 내용을 담을 예정이다. 즉, 계속 업데이트가 될 것이며, 쭉 이해만 하면 관련문제는 풀 수 있을 것이다. 따라서 python 을 활용한 코드뿐만아니라 알고리즘과 관련된 모든 유형의 문제에 관련된 풀이들도 추가할 예정이다. 일단, 기본적으로 재귀를 쓰기 때문에 DFS와 BFS를 구현하지 못한다면 이부분이 어려울 수 있다. 시작해보도록 하자. 1. 백트래킹 백트래킹 기법은 해를 찾는 도중에 '막히면' 되돌아가서 다시 해를 찾아 가는 기법이다. 일명 가지치기라고도 한다. => 재귀를 이용한 완전 검색을 하고 가지치기를 추가하는 기법 백트래킹으로 최적화문제(optimization)와 결정문제(d..

nPr n! 서로 다른 것들 중 몇개를 뽑아서 한 줄로 나열하는 것이다. 보통 대부분의 문제는 n! 으로 풀린다. n! 에서 n이 10정도면.. C기준으로 10초정도면 계산한다. python은 약 30초 정도 걸린다.(가지치기를 안한 기준) n이 12 이상이면 시간 복잡도는 폭팔적으로 늘어난다. n이 10~15정도면 가지치기 잘하면 순열로 풀 수 도 있겠구나라고 생각하고 접근하고 만약 15가 넘는다면 순열로 푸는거 아니다. 바로 코드보자. 크게 visited를 이용한 풀이와 swap를 이용한 풀이가 있다. nPr # visited def perm(n, r, k): if r == k: print(t) else: for i in range(0, n): if visited[i] : continue t[k] =..

10진수를 타진수로 변환하기 원하는 타진법의 수로 나눈 뒤 나머지를 거꾸로 읽는다. 2진수를 8진수로 바꾸기 3개씩 묶어서 계산한다 2진수를 16진수로 바꾸기 4개씩 묶어서 계산한다 ex) (149)10 = (10010101)2 = (225)8 = (95)16 10진수 외의 다른 진수는 접두어가 붙는다 2진수: 0b 8진수: 0o 16진수: 0x 내장함수를 이용해서 10진수를 변환하기 val = 40 b = bin(val) o = oct(val) h = hex(val) 이때 결과는 문자열이고 접두어가 추가되어 출력된다. format 내장함수 사용해서 10진수를 다른 진수로 변환하기 val = 40 b = format(val, '#b') o = format(val, '#o') h = format(val, ..

컴퓨터의 메모리와 같은 1차원의 공간에 여러 ㄱ의 연속된 대상을 배열하는 방법을 의미하며 HW 아키텍처마다 다르다. 주의: 속도 향상을 위해 바이트 단위와 워드 단위를 변환하여 연산 할 때 올바로 이해하지 않으면 오류를 발생 시킬 수 있다. 워드 : 컴퓨터가 한번에 처리하는 단위 ex) 32비트는 32개를 한번에 처리 (32bit=4byte) 빅 엔디안(Big-endian) 큰 단위가 앞에 나옴.(왼쪽부터 표현) 네트워트(internet protocel)에서 사용 리틀 엔디안(Little-endian) 작은 단위가 앞에 나옴.(오른쪽 부터 표현) 대부분 데스크탑에서 사용 종류 0x1234의 표현 0x12345678의 표현 빅 엔디언 12 34 12 34 56 78 리틀 엔디안 34 12 78 56 34 12

num1 = 2 -> 0010 num2 = 3 -> 0011 & AND num1&num2 0010 | OR num1|num2 0011 ^ XOR(다를 때 1/같을 때 0) num1^num2 0001 ~ not 연산자 ~num1 1101 2 0000 - 범위를 벗어나면 없어진다고 생각하자.(시스템에 따라 다르게 처리. 앞으로 돌아가진 않음) - 내부적으로 비트로 연산을 하고 결과는 정수로 보여준다. 자주 사용하는 모음 N&1 양의 정수의 짝수 홀수 판별 N%2(나머지 연산) 보다 효율이 좋다 연산 후에 마지막을 비트 값이 1인지 0인지로 판단한다. 1

1부터 100까지의 합을 구해보자 1+2+3+...+99+100 을 하면 100번 연산을 해야한다. (100*(1+100))/2 을 하면 갯수에 상관없이 3번만 연산을 하면된다. 당연히 아래 부분이 효율성이 높다고 할 수 있다. 효율성에는 공간적 효율성과 시간적 효율성이 있다. 공간적 효율성은 얼마나 많은 메모리 공간을 요구하는지를 나타내고 시간적 효육성은 얼마나 많은 시간을 요구하는지를 나타낸다 이 때 복잡도(complexity)가 높을 수록 효율성이 저하된다. 시간 볻잡도 분석이 하드웨어와 소프트웨어의 환경에 따라 달라진다. 따라서 객관적인 분석법이 필요하게 된다. 이때 나온 것이 복잡도의 점근적 표현이다 복잡도의 점근적 표현에는 Big-oh, big-omega, big-theta가 있다. O(Big..

정렬(Sort)이란 정렬(Sorting)알고리즘에 대해 배워보자 정렬(Sorting)이란 리스트의 원소들을 특정 순서로 정리하는 것으로 크게 아래의 세 가지로 나누기가 가능하다. 1. 오름차순 정렬(갈수록 커짐) 2. 내림차순 정렬 3. 알파벳순 정렬 파이썬에는 sorted 내장함수와 리스트에 있는 sort() method도 있다. 파이썬에도 정렬을하는 내장함수와 메서드가 있다. 내장함수 sorted list의 method인 sort() # 사용법 data = [12, 6, 4, 17, 11, 15, 1, 30] sorted(data) data.sort() # [1, 4, 6, 11, 12, 15, 17, 30] #숫자 뿐만 아니라 영어도 정렬 된다. Q. 그냥 sorted나 sort()를 쓰면 되는데 ..