Algorithm/Algorithm Theory

📚 다이나믹 프로그래밍(Dynamic Programming, DP) 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함 다이나믹 프로그래밍 구현은 일반적으로 두 가지 방식(탑다운(top-down)과 보텀업(bottom-up))으로 구성 🟦 일반적인 프로그래밍 분야에서의 동적(Dynamic)이란? 자료구조에서 동적 할당은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미 반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어 ▼ 다음의 조건을 만족할 때 사용 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며..

📁정규표현식정규표현식(RE)은 특정한 규칙을 가진 문자열의 집합을 표현하는데 사용하는 형식 언어복잡한 문자열의 검색과 치환을 위해 사용됨re 모듈 사용import re 정규식 검사 함수1. compile 정규표현식 컴파일re.compile() 명령을 통해 정규표현식을 컴파일하여 변수에 저장한 후 사용 가능변수명 = re.compile('정규표현식') 컴파일 옵션DOTALL(S) : `.`(dot)이 줄바꿈 문자를 포함해 모든 문자와 매치될 수 있게 함IGNORECASE(I) : 대소문자에 관계없이 매치될 수 있게 함MULTILINE(M) : 여러 줄과 매치될 수 있게 함  `^`, `$` 메타 문자 사용과 관계 있는 옵션VERBOSE(X) : verbose 모드를 사용할 수 있게 한다. 정규식을 보기 ..

2차원 배열 1차원 List를 묶어놓은 List 2차원 이상의 다차원 List는 차원에 따라 Index를 선언 2차원 List의 선언 : 세로길이(행의 개수), 가로길이(열의 개수)를 필요로 함 Python에서는 데이터 초기화를 통해 변수선언과 초기화가 가능함 - 배열 순회 n X m 배열의 n*m 개의 모든 원소를 빠짐없이 조사하는 방법 1. 행 우선 순회 # i행의 좌표 # j열의 좌표 for i int range(n): for j int range(m): Array[i][j] # 필요한 연산 수행 2. 열 우선 순회 # i행의 좌표 # j열의 좌표 for j int range(n): for i int range(m): Array[i][j] # 필요한 연산 수행 3. 지그재그 순회 # i행의 좌표 #..

Baby-gin Game 설명 0~9 사이의 숫자 카드에서 임의의 카드 6장 뽑았을 때, 3장의 카드가 연속적인 번호를 갖는 경우를 run이라 하고, 3장의 카드가 동일한 번호를 갖고 있는 경우를 triplet이라 함 6장의 카드가 run과 triplet로만 구성된 경우를 baby-gin 6자리의 숫자를 입력 받아 baby-gin 여부를 판단하는 프로그램 작성 1. 완전 검색(Exaustive Search) 완전 검색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 Brute-force 혹은 generate-and-test 기법 모든 경우의 수를 테스트한 후, 최종 해법 도출 - 경우의 수가 상대적으로 작을 때 유용 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작..